I Birindelli

F Demengel

PROBLEMS ASSOCIATED TO FULLY NONLINEAR DEGENERATE ELLIPTIC EQUATIONS

Keywords: 1991 Mathematics Subject Classification. 35J25, 35J60, 35P30. Regularity, fully nonlinear equations, simplicity of the first nonlinear eigenvalue

We prove Hölder regularity of the gradient, up to the boundary for solutions of some fully-nonlinear, degenerate elliptic equations, with degeneracy coming from the gradient.

Introduction

In a recent paper Imbert and Silvestre [?] have proved that the solutions of |∇u| α F (D 2 u) = f (x) in Ω ⊂ IR N (1.1) have first derivative which are Hölder continuous in the interior of Ω when α ≥ 0, F is uniformly elliptic and f is continuous.

Results concerning regularity of solutions have an intrinsic interest which doesn't need to be explained. When α = 0, it is known (see e.g. Evans [?], Cabré, Caffarelli [?], [?], [?]) that u is C 1,β for some β ∈ (0, 1). But for solutions of (??) with α > -1 the question of the continuity of the gradient was open and it was naturally raised, in [?]. In fact, the question raised concerned precisely regularity near the boundary. Let us recall that contest. The values µ + = sup{µ, ∃φ > 0 in Ω, |∇φ| α F (D 2 φ) + µφ 1+α ≤ 0 in Ω}, µ -= sup{µ, ∃ψ < 0 in Ω, |∇ψ| α F (D 2 ψ) + µ|ψ| α ψ ≥ 0 in Ω} are generalised principal eigenvalues in the sense that there exists a non trivial solution to the Dirichlet problem |∇φ| α F (D 2 φ) + µ ± |φ| α φ = 0 in Ω, φ = 0 on ∂Ω, with constant sign.

The main scope in [?] was to prove the simplicity of these principal eigenvalues. The main difficulty comes from the fact that the strong comparison principle holds only in open subsets of Ω where the gradient is away from zero (in the viscosity sense). It is well known that the Hopf Lemma guarantees that this is true on ∂Ω. So that the continuity of the gradient up to the boundary would imply that, in a neighbourhood of it, the strong comparison principle holds, which is exactly what is needed to prove that the eigenvalues are simple.

In that same paper, we proved that if α ∈ (-1, 0) the solutions of the Dirichlet problem associated to (??) are indeed C 1,β and we raised the problem of whether that regularity would hold also for α ≥ 0 i.e. when the operator is degenerate elliptic.

[?] was a first answer in that direction, very much inspired by that breakthrough, we wanted to complete the work. We want to point out that a difficulty specific to this type of equation is due to the fact that the difference of two solutions is not a sub-or super solution to another equation, which would provide regularity.

Recall that F is uniformly elliptic if there exists Λ ≥ λ > 0 such that for any symmetric matrices M and N

F (M ) + M - λ,Λ (N ) ≤ F (M + N ) ≤ F (M ) + M + λ,Λ (N ) (1.2)
here we have denoted the Pucci operators M - λ,Λ (N ) = λtr(N + ) + Λtr(N -) and M + λ,Λ (M ) = λtr(M -) + Λtr(M + ). In the rest of the paper we shall drop the indices λ and Λ of the Pucci operators.

We now state the main result of the paper in its generality.

Theorem 1.1. Suppose that Ω is a bounded C 2 domain of IR N and α ≥ 0. Suppose that F is uniformly elliptic and that h ∈ C(Ω). Let f ∈ C(Ω) and ϕ ∈ C 1,βo (∂Ω). For any u, viscosity solution of

|∇u| α (F (D 2 u) + h(x) • ∇u) = f in Ω u = ϕ on ∂Ω there exist β = β(λ, Λ, f ∞ , N, Ω, h ∞ , β o ) and C = C(β) such that u C 1,β (Ω) ≤ C ϕ C 1,βo (∂Ω) + u ∞ + f 1 1+α ∞ .
For radial solutions, and a more general class of operators, this was proved in [?], with the optimal Hölder's coefficient inf( The novelty with respect to the paper of Imbert and Silvestre is two folded, on one hand we have added the lower order term h(x) • ∇u|∇u| α , and on the other hand we go all the way to the boundary.

The proof follows the scheme of the one in [?], but requires new tools. In particular in section 2, we give some a priori Lipschitz and Hölder estimates in the presence of boundary conditions on one part of the boundary. These are important because the proof of Theorem ?? requires that sequence of bounded solutions do converge to a solution of a limit equation.

The main tool is an "improvement of flatness lemma". In the proof of Lemma ??, we need to use regularity estimates for a limit equation with boundary terms. The novelty is in guaranteeing that even in the presence of the lower order terms and of the boundary term the limit equations are sufficiently "good" and the new terms behave well, see in particular the Claim in the proof of Lemma ??.

Let us make a final remark : Following Caffarelli's famous technique, the results here obtained could be generalised to an operator depending on x i.e. of the form |∇u| α F (x, D 2 u); in particular by imposing conditions on

β(x) = sup M ∈S F (x, M ) -F (x, 0) |M | .
But we would further need to impose conditions that guarantee that u, a solution of

|∇u| α F (x, D 2 u) = 0 in Ω ⇒ F (x, D 2 u) = 0 in Ω.
For the sake of clarity we have chosen not to treat the case where there is a dependence on x.

After this paper was submitted for publication, Silvestre and Sirakov have posted an interesting related paper [?].

Local Hölder and Lipschitz estimates up to the boundary.

Throughout the paper, the notation B r (x) indicates the euclidian ball of radius r and centre x, we will write B r when no ambiguity arises.

It is a classical fact that in order to prove that u is C 1,β at x o , it is enough to prove that there exists some constant C such that, for all r < 1, there exists p r ∈ IR N , such that osc

Br(xo) (u(x) -p r • x) ≤ Cr 1+β .
As a consequence, u is C 1,β in some bounded open set B if there exists a constant C β such that for all x ∈ B and r < 1, there exists p r,x such that osc

Br(x) (u(y) -p r,x • y) ≤ C β r 1+β .
This will be used in the whole paper.

We begin by stating the following comparison theorem which will be needed later, proved in [?] under stronger conditions on h, later improved to h continuous and bounded in [?].

Theorem 2.1. [?, ?] In the hypothesis of Theorem ??, let u and v be respectively C(Ω)

solutions of |∇u| α (F (D 2 u) + h(x) • ∇u) ≤ f in Ω and |∇v| α (F (D 2 v) + h(x) • ∇v) ≥ g in Ω
with f and g continuous and bounded such that f < g.

If u ≥ v on ∂Ω then u ≥ v in Ω.
In order to prove Hölder and Lipschitz estimates we fix a few notations concerning Ω and F . We suppose, without loss of generality, that at 0 ∈ ∂Ω, the interior normal is e N . By the implicit function theorem, there exist a ball B = B R (0) in IR N , and

D ′ ⊂ B ′ R (0) ball of IR N -1 and a ∈ C 2 (D ′ ), such that a(0) = 0, ∇a(0) = 0 and, for y = (y ′ , y N ), Ω ∩ B ⊂ {y N > a(y ′ ), y ′ ∈ D ′ }, and ∂Ω ∩ B = {y N = a(y ′ ), y ′ ∈ D ′ }.
We shall also act as if F be positively homogeneous of degree 1 i.e. such that for any t > 0, F (tM ) = tF (M ). Observe though that, if this doesn't hold, when necessary it is enough to replace F (M ) by G t (M ) = t -1 F (tM ); this operator satisfies (??) with the same constants as F and the results are unchanged.

In the lemma below we have supposed, for simplicity, that B is the unit ball centred at the origin. Lemma 2.2. Let ϕ ∈ C 1,βo . Let a ∈ C 2 (D ′ ) such that a(0) = 0 and ∇a(0) = 0. Let d be the distance to the hyper surface {y N = a(y ′ )}.

Then, for all r < 1 and for all γ < 1, there exists δ o depending on f ∞ , λ, Λ, h ∞ , Ω, r and Lipϕ, such that for all δ < δ o , if u is a solution of

|∇u| α (F (D 2 u) + h(y) • ∇u) = f in B ∩ {y N > a(y ′ )} u = ϕ on B ∩ {y N = a(y ′ )} (2.1)
such that osc u ≤ 1 then it satisfies

|u(y ′ , y N ) -ϕ(y ′ )| ≤ 6 δ d(y) 1 + d(y) γ in B r (0) ∩ {y N > a(y ′ )}.
Proof. We write the details of the proof for ϕ = 0. Note that then u ∞ ≤ 1. The changes to bring in the case ϕ = 0 will be given at the end of the proof, the detailed calculation being left to the reader.

It is sufficient to consider the set where d(y) < δ since the assumption u ∞ ≤ 1 implies the result elsewhere.

We begin by choosing δ < δ 1 , such that on d(y) < δ 1 the distance is C 2 and satisfies |D 2 d| ≤ C 1 . We shall also later choose δ smaller depending of (λ, Λ, f ∞ , h ∞ , N ).

In order to use the comparison principle we want to construct w a super solution of

|∇w| α (M + λ,Λ (D 2 w) + h(y) • ∇w) < -f ∞ , in B ∩ {y N > a(y ′ ), d(y) < δ} (2.2) such that w ≥ u on ∂(B ∩ {y N > a(y ′ ), d(y) < δ}).
The candidate is

w(y) = 2 δ d(y) 1+d γ (y) for |y| < r 2 δ d(y) 1+d γ (y) + 1 (1-r) 3 (|y| -r) 3 for |y| ≥ r.
In order to prove the boundary condition, let us observe that, on {d(y

) = δ}, w ≥ 2 δ δ 1+δ γ ≥ 1 ≥ u, on {|y| = 1} ∩ {d(y) < δ}, w ≥ 1 (1-r) 3 (1 -r) 3 ≥ u and finally on B ∩ {y N = a(y ′ )}, w ≥ 0 = u.
We need to check that w is a super solution. For that aim, we compute

∇w = 2 δ 1+(1-γ)d γ (1+d γ ) 2 ∇d when |y| < r 2 δ 1+(1-γ)d γ (1+d γ ) 2 ∇d + y |y| 3 (1-r) 3 (|y| -r) 2 if |y| > r.
Note that |∇w| ≥ 1 4δ as soon as δ ≤ 1-r 12 . By construction w is C 2 and

D 2 w = -( 2γd γ-1 δ ) (1 + γ) + (1 -γ)d γ (1 + d γ ) 3 ∇d ⊗ ∇d + 2 δ 1 + (1 -γ)d γ (1 + d γ ) 2 D 2 d + H(y)
where

H(y) ≤ 6 (1-r) 2 + 3(N -1)
r(1-r) . Standard computations that use (??) imply that w satisfies (??), when δ < min(δ 1 , 1-r 12 ) is small enough that the two following inequalities hold

λ(γδ γ-2 ) (1 + γ) (1 + δ γ ) 3 > 2Λ 6 (1 -r) 2 + 3(N -1) r(1 -r) + 2C 1 δ + 4 h ∞ δ , λ 2 2+2α (γδ γ-(2+α) ) (1 + γ) (1 + δ γ ) 3 > f ∞ . By the comparison principle, Theorem ??, u ≤ w in B ∩ {y N > a(y ′ )} ∩ {d(y) < δ}.
Furthermore the desired lower bound on u is easily deduced by considering -w in place of w in the previous computations and restricting to B r ∩ {y N > a(y ′ )}. This ends the case ϕ ≡ 0.

When ϕ ≡ 0, let ψ be a solution of

M + λ,Λ (D 2 ψ) = 0 in B ∩ {y N > a(y ′ )} ψ = ϕ on B ∩ {y N = a(y ′ )}. It is well known that ψ is C 1,βo (B ∩ {y N ≥ a(y ′ )}) ∩ C 2 (B ∩ {y N > a(y ′ )}). Furthermore, we can choose ψ such that ψ ∞ ≤ ϕ ∞ ≤ 1, ∇ψ ∞ ≤ c ∇ϕ ∞ , for some constant c which depends on λ, Λ, N, Ω, see [?].
We now define

w(y) = 8 δ d(y) 1+d γ (y) + ψ(y) for |y| < r 8 δ d(y) 1+d γ (y) + 1 (1-r) 3 (|y| -r) 3 + ψ(y) for |y| > r.
Computations similar to the case ϕ = 0 imply that

w ≥ u on ∂(B ∩ {y N > a(y ′ )} ∩ {d(y) < δ}).
Furthermore choosing δ small enough, we can ensure that

|∇w| α (M + λ,Λ (D 2 w) + h(x) • ∇w) < -f ∞ .
For the lower bound, we replace w by 2ψw. This ends the proof of Lemma ??.

Using this estimate together with an argument due to Ishii and Lions, [?], one finally gets the Hölder regularity of the solution, which can be stated as follows with the same hypothesis on a, and f as above : Proposition 2.3. Let ϕ be a Lipschitz continuous function. Suppose that u satisfies (??).

For all r < 1, and for all γ < 1, u is γ Hölder continuous on B r ∩ {y N > a(y ′ )}, with some Hölder's constant depending on (r, λ, Λ, a, N, f ∞ , h ∞ , Lipϕ).

Remark 2.4. In the absence of boundary conditions, the solutions are Hölder continuous inside B r for any r such that B r ⊂⊂ B. We do not give the proof which follows the lines in the proof below, it is sufficient to cancel in it the dependence on ϕ. This will be used in the proof of the interior improvement of flatness lemma with additional lower terms.

In the following proof we shall use directly the definition of viscosity solutions, so, in particular, in order to fix the notations we state the definition of semi-jets: Definition 2.5. Let S 2n denote the symmetric 2n×2n matrices. For any continuous function g we define the intrinsic semi-jets by:

J 2,+ g(x) = {(p, X) ∈ IR N × S N , g(x + h) ≤ g(x) + p • h + 1 2 Xh, h + o(h 2 ) ∀h ∈ IR N }, J 2,-g(x) = {(p, X) ∈ IR N × S N , g(x + h) ≥ g(x) + p • h + 1 2 Xh, h + o(h 2 ) ∀h ∈ IR N }.
and the definition of the closed semi jets Definition 2.6.

J 2,+ g(x) = {(p, X) ∈ IR N × S N , ∃ x n , ∃(p n , X n ) ∈ J 2,+ g(x n ), g(x n ) → g(x), and (p n , X n ) → (p, X)}
and analogous definition for J 2,-g(x)

Proof of Proposition ??.

The proof relies on arguments similar to those in [?], [?], and [?]. Let 1 > r 1 > r. Without loss of generality we can suppose that osc u ≤ 1. Let x o ∈ B r ∩ {y N > a(y ′ )} and Φ be defined as

Φ(x, y) = u(x) -u(y) -M |x -y| γ -L|x -x o | 2 -L|y -x o | 2 .
The scope is to prove that for L and M independent of x o , chosen large enough,

Φ(x, y) ≤ 0 on (B r1 ∩ {y N > a(y ′ )}) 2 .
(

This will imply that u is γ-Hölder continuous on B r ∩ {y N > a(y ′ )} by taking x = x o , and letting x o vary.

To prove (??), we begin by observing that the inequality holds on the boundary. First we treat the points where y N = a(y ′ ). According to Lemma ?? there exists M o such that for

x ∈ B r1 ∩ {y N > a(y ′ )}, |u(x) -ϕ(x ′ )| ≤ M o d(x, ∂Ω).
Then, using |x ′y ′ | ≤ |x -y|, one has

|u(x ′ , x N ) -u(y ′ , a(y ′ ))| ≤ |u(x ′ , x N ) -u(x ′ , a(x ′ ))| + |u(x ′ , a(x ′ )) -u(y ′ , a(y ′ ))| ≤ M o d(x, ∂Ω) + Lip ϕ |x ′ -y ′ | ≤ M o |x -(y ′ , a(y ′ ))| + Lip ϕ |x -(y ′ , a(y ′ ))|.
So, if M is chosen greater than M o + Lipϕ, then we have obtained that Φ(x, y) ≤ 0 on (B r1 ∩ {y N = a(y ′ )}) [START_REF] Barles | Hölder continuity of solutions of second-order non-linear elliptic integro-differential equations[END_REF] .

In order to satisfy the required estimate on the rest of the boundary, it is enough to choose L > 4 (r1-r) 2 and to recall that the oscillation of u is bounded by 1.

In the sequel we will choose L large and M > 4L 2 N γ(1-γ) . Suppose by contradiction that Φ(x, y) > 0 for some (x, y) ∈ B r1 ∩ {y N > a(y ′ )}. Then there exists (x, ȳ) such that Φ(x, ȳ) = sup Then, as in [?], for all small ǫ > 0 depending on the norm of Q := D 2 (M |x -y| γ ), using Ishii's Lemma [?], there exist X and Y such that

(γM (x -ȳ)|x -ȳ| γ-2 + 2L(x -x o ), X) ∈ J 2,+ u(x) (γM (x -ȳ)|x -ȳ| γ-2 -2L(y -x o ), -Y ) ∈ J 2,-u(ȳ) with X 0 0 Y ≤ Q -Q -Q Q + (2L + ǫ) I 0 0 I .
In the sequel, since we assumed that L M ≤ C L one also has L+ǫ M ≤ C L and then we drop ǫ for simplicity.

Let us denote q x = γM (x-ȳ)|x-ȳ| γ-2 +2L(x-x o ), and

q y = γM (x-ȳ)|x-ȳ| γ-2 -2L(ȳ- x o ). Since γ < 1, as soon as 2L(r + r 1 ) ≤ γ 2 M r γ-1 1 , we get that 2L|x -x o | ≤ γM 2 |x -ȳ| γ-1 i.e. 2γM |x -ȳ| γ-1 ≥ (|q x |, |q y |) ≥ 1 2 γM |x -ȳ| γ-1 .
Since |q xq y | ≤ 4L, by the mean value theorem and using a constant κ < α if α < 1 and κ = 1 if α ≥ 1:

||q x | α -|q y | α | ≤ α|q x -q y | κ 2 |α-1| |γM |x -ȳ| γ-1 | 1-κ |γM |x -ȳ| γ-1 | α-1 ≤ C(M γ|x -ȳ| γ-1 ) α-κ L κ = o((M |x -ȳ| (γ-1) ) α ).
We now treat the terms concerning the second order derivative. The previous inequalities can also be written as

X -2LI 0 0 Y -2LI ≤ Q -Q -Q Q .
We Indeed, let

P := (x -ȳ ⊗ x -ȳ) |x -ȳ| 2 ≤ I.
Using 4L -(X + Y ) ≥ 0, (I -P ) ≥ 0 and the properties of the symmetric matrices, one has

tr(X + Y -4L) ≤ tr(P (X + Y -4L)).
Remarking in addition that

X + Y -4L ≤ 4Q, one sees that tr(X + Y -4L) ≤ 4tr(P Q). But tr(P Q) = γM (γ -1)|x -ȳ| γ-2 < 0, hence |tr(X + Y -4L)| ≥ 4γM (1 -γ)|x -ȳ| γ-2 .
(2.4) Furthermore, by Lemma III.1 of [?], there exists a universal constant C such that For some positive constants c 2 , c 3 , since u is both a sub-and a super-solution of (??), using the uniform ellipticity of F and the assumptions on h:

|X|, |Y |, |X -2L|, |Y -2L| ≤ C(|tr(X + Y -4L)| + |Q| 1 2 |tr(X + Y -4L)| 1 2 ) ≤ C|tr(X + Y -4L)| ≤ C|tr(X + Y )|,
f (x) ≤ |q x | α (F (X) + h(x) • q x ) ≤ |q y | α (F (X) + h(x) • q x ) +o(M γ|x -ȳ| γ-1 ) α (Λ|X| + h ∞ (γM |x -ȳ| γ-1 + 2L)) ≤ |q y | α (F (-Y ) + h(ȳ) • q x + 4 h ∞ L) + +|q y | α tr(X + Y )Λ + o(M 1+α |x -ȳ| (γ-1)α+γ-2 ) ≤ M α c 2 |x -ȳ| (γ-1)α tr(X + Y ) + o(M 1+α |x -ȳ| (γ-1)α+γ-2 ) + f (ȳ) ≤ -c 3 M 1+α |x -ȳ| (γ-1)α+γ-2 + f (ȳ).
This is clearly false as soon as L (and then M ) is large enough and it ends the proof.

Compactness near the boundary is a natural consequence of Proposition ??.

Corollary 2.7. Suppose that (u n ) is a bounded sequence of continuous functions which satisfy

|∇u n | α (F (D 2 u n ) + h(y) • ∇u n ) = f n in B ∩ {y N > a(y ′ )} u n = ϕ on B ∩ {y N = a(y ′ )}
and suppose that (f n ) converges simply to some continuous function f . Then for all r < 1, one can extract from (u n ) a subsequence which converges uniformly, on B r ∩ {y N > a(y ′ )}, to a solution of

|∇u| α (F (D 2 u) + h(y) • ∇u) = f in B ∩ {y N > a(y ′ )} u = ϕ on B ∩ {y N = a(y ′ )}.
Remark 2.8. In the absence of boundary conditions, the analogous result holds, in the sense that one can extract from (u n ) n a subsequence which converges uniformly on every B r ⊂⊂ B to u a solution of

|∇u| α (F (D 2 u) + h(y) • ∇u) = f in B.
When we shall treat, in the improvement of flatness lemma up to the boundary, the case where the boundary is locally straight, we shall need the following Lipschitz estimate's near the boundary for some different but related equation. Proposition 2.9. (Lipschitz estimates for large p ′ s) Let ϕ be a Lipschitz continuous function. Suppose that h N ≡ 0. Assume that u solves

|pe N + ∇u| α (F (D 2 u) + h(y) • ∇u) = f in B 1 (x) ∩ {y N > 0} u = ϕ on B 1 (x) ∩ {y N = 0} with osc B1(x)∩{y N >0} u ≤ 1 and f L ∞ (B1(x)∩{y N >0}) ≤ ǫ o < 1.
Then, for all r < 1, there exists b o depending on (λ, Λ, N, α, r, ǫ o , Lipϕ), such that if |p| > 1 bo , u is Lipschitz continuous in B r (x) ∩ {y N > 0} with some Lipschitz constant depending on (λ, Λ, N, α, r, ǫ o , Lipϕ).

Remark 2.10. In the absence of boundary conditions, the solutions in some ball B are Lipschitz in B r , for any r such that B r ⊂⊂ B with Lipschitz constant independent of p.

This will be used in the proof of the interior improvement of flatness lemma with lower order terms. This Proposition is a consequence of the following Lemma 2.11. Suppose that ϕ is Lipschitz continuous and that h N ≡ 0. For all γ < 1, for all r < 1, there exists δ = δ( f ∞ , λ, Λ, r, Lipϕ), such that for b < δ 4 , any solution u of

|e N + b∇u| α (F (D 2 u) + h(y) • ∇u) = f in B 1 (x) ∩ {y N > 0} u = ϕ on B 1 (x) ∩ {y N = 0}. such that osc(u) ≤ 1, satisfies |u(y ′ , y N ) -ϕ(y ′ )| ≤ 2 δ y N 1+y γ N in B r (x) ∩ {y N > 0}.
Proof of Lemma ??. Suppose for simplicity that ϕ = 0. If b = 0 the result is known by properties of solutions of F (D 2 u) + h(x) • ∇u = f which are zero on the boundary. So we assume in what follows that b = 0.

We proceed as in Lemma ??, replacing the distance of y to the boundary by y N ; so we consider

w(y) = 2 δ y N 1+y γ N for y N < δ, |y ′ | < r 2 δ y N 1+y γ N + 1 (1-r) 3 (|y ′ | -r) 3 for y N < δ, |y ′ | > r.
Similarly to the proof of Lemma ??, it is sufficient to consider the set where y N < δ, since the assumption osc u ≤ 1 implies u ∞ ≤ 1, so the result holds elsewhere. Furthermore we only prove that u ≤ w, the desired lower bound can be obtained by considering -w in place of w.

In order for w to satisfy

|e N + b∇w| α (M + λ,Λ (D 2 w) + h(y) • ∇w) ≤ -f ∞ , in B,
it is sufficient to choose δ such that 1 2

α λγδ γ-2 (1 -γ) 1 (1 + δ γ ) 3 > f ∞ + 2Λ 6 (1 -r) 2 + 3(N -1) r(1 -r) + 4 h ∞ δ , b < δ 4
, and recall that |∇w| ≤ 2 δ . Furthermore w ≥ u on ∂(B ∩ {0 < y N < δ}). Hence we can use the comparison principle in Theorem ??, for w(x) = x N + bw(x) and ũ(x) = x N +bu(x), with b = 0, ( recall that h N ≡ 0 )which implies that u ≤ w in B∩{y N > 0}. Finally the desired estimate is obtained in {|y ′ | < r, y N > 0}.

In the case ϕ ≡ 0, we take the function w as in the proof of Lemma ??, with d replaced by y N . Requiring sufficient restriction on the smallness of δ give the result.

We are now ready to give the Proof of Proposition ??. The proof proceeds as in [?] so we just detail the differences. Recall that u is a solution of

|e N + bDu| α (F (D 2 u) + h(y) • ∇u) = f with b = 1 p and f = |p| -α f . Let r < r 1 < 1 and let x o ∈ B r1 (x) ∩ {y N > 0}, L 2 = 4 (r1-r) 2 , ψ(z, y) = u(z) -u(y) -L 1 ω(|z -y|) -L 2 |z -x o | 2 -L 2 |y -x o | 2 where ω(s) = s -ω o s 3 2 if s ≤ s o = 2 3ωo 2 and ω(s) = ω(s o ) if s ≥ s o . We also require L 1 > 3( 2 δ + Lip ϕ ).
If we prove that ψ(z, y) ≤ 0 in B r1 (x) , since L 1 is independent of x o , by choosing z = x o one gets

u(x o ) -u(y) ≤ L 1 |x o -y| + L 2 |x o -y| 2 ; next choosing y = x o for all z ∈ B r1 , u(z) -u(x o ) ≤ L 1 |x o -z| + L 2 |x o -z| 2 .
Finally we get, for (x, y)

∈ B r (x), |u(x) -u(y)| ≤ L 1 |x -y| + L 2 |x -y| 2 ,
which implies the desired result.

We begin to observe that if the supremum is achieved in (x, ȳ) ∈ B r (x) then, with our choice of L 1 , neither x nor ȳ can belong to the part {z N = 0} according to Lemma ??.

The rest of the proof is as in [?] and [?], (see also the proof of Proposition ??) as long as we choose δ small enough in order that

1 2 α λ(γδ γ-2 ) (1 + γ) 2(1 + δ γ ) 3 > f ∞ + 2Λ( 6 (1 -r) 2 + 3(N -1) r(1 -r) + 4 h ∞ δ ) > f ∞ + 2Λ( 6 (1 -r) 2 + 3(N -1) r(1 -r) + 4 h ∞ δ ).
and such that b < δ 4 . Let us note that this implies that b is small enough depending on (λ, Λ, N, α, r, ǫ o , h ∞ , Lipϕ).

As a corollary of this Lemma one has the following compactness result Corollary 2.12. Let ϕ be a Lipschitz continuous function. Suppose that (u n ) is a sequence of uniformly bounded continuous viscosity solutions of

|e N + b n ∇u n | α F (D 2 u n ) + h • ∇u n = f n in B ∩ {y N > a(y ′ )}, u n = ϕ on B ∩ {y N = a(y ′ )}.
where b n ≤ b o , b o is given above in Proposition ??. Suppose that f n converges simply to some function f in Ω. Then for all r < 1, one can extract from (u n , b n ) a subsequence which converges uniformly on B r ∩ {y N > a(y ′ )} × IR, and the limit (u, b) satisfies

|e N + b∇u| α F (D 2 u) + h • ∇u = f in B ∩ {y N > a(y ′ )}, u = ϕ on B ∩ {y N = a(y ′ )}.
Remark 2.13. In the absence of boundary conditions, the conclusion is that the sequence (u n ) contains a subsequence which converges locally uniformly and up to a constant toward a solution of

|e N + b∇u| α F (D 2 u) + h • ∇u = f in B.
3. Proof of Theorem ??.

In fact Theorem ?? is an immediate consequence of the following local result up to the boundary together with some argument of finite covering: Theorem 3.1. Suppose that F , h and f are as in Theorem ?? and ϕ is a function in C 1,βo . Let B be a ball in IR N and let a be a C 2 function defined on IR N -1 with a(0) = 0, ∇a(0) = 0. There exists β such that for any u solution of

|∇u| α (F (D 2 u) + h(x) • ∇u) = f in B ∩ {x N > a(x ′ )} u = ϕ on B ∩ {x N = a(x ′ )}, u is C 1,β ( B ∩ {x N > a(x ′ )}) for any B ⊂⊂ B.
Theorem ?? is proved via the following two "improvement of flatness" lemma and their consequences.

Lemma 3.2. There exist ǫ o ∈]0, 1[ and ρ ∈]0, 1[ depending on (α, h ∞ , λ, Λ, N ) such that for any p ∈ IR N and for any viscosity solution u of Then for all x ∈ B such that B 1 (x) ⊂ B, osc B1(x)∩{y N >a(y ′ )} u ≤ 1, and f L ∞ (B1(x)∩{y N >a(y ′ )}) ≤ ǫ o , there exists q x,ρ ∈ IR N such that

|p + ∇u| α F (D 2 u) + h(y) • (∇u + p) = f in B 1 such that osc B1 u ≤ 1 and f L ∞ (B1) ≤ ǫ o , there exists p ′ ∈ IR N such that osc Bρ (u -p ′ • x) ≤ 1 2 ρ.
osc Bρ(x)∩{y N >a(y ′ )} (u(y) -q x,ρ • y) ≤ ρ 2 .
Suppose that these Lemmata have been proved and let us derive the following one. with osc u ≤ 1 and f ∞ ≤ ǫ o , then there exists β ∈]0, 1[ such that for all k there exists p k ∈ IR N such that osc

B r k (u(x) -p k • x) ≤ r 1+β k .
Proof of Lemma ??. As in [?] we use a recursive argument.

We first remark that one can assume that ϕ(x

′ ) = ∂ i ϕ(x ′ ) = 0 for i = 1, • • • , N -1.
Indeed, let u be a solution of (??). Then v(y)

:= u(y) -u(x) -∇ϕ(x ′ ) • (y ′ -x ′ ) satisfies |∇v + q| α (F (D 2 v) + h(y) • (∇v + q)) = f in B 1 (x) ∩ {y N > a(y ′ )} v(y ′ , a(y ′ )) = φ(y ′ ) on B 1 (x) ∩ {y N = a(y ′ )}
where q = (∇ϕ(x ′ ), 0) and φ(y

′ ) = ϕ(y ′ ) -ϕ(x ′ ) -∇ϕ(x ′ ) • (y ′ -x ′ ) which satisfies φ(x ′ ) = ∂ i φ(x ′ ) = 0 for i = 1, • • • , N -1.
So the result obtained for v would easily transfer to u.

Choose β small enough in order that ρ β > 1 2 , and define r k = ρ k . We can start the recursive argument. For k = 0, taking p o = 0 yields the desired inequality. Suppose that p k exists we now construct p k+1 .

Let

ϕ k (y ′ ) = r -1-β k ϕ(x ′ + r k (y ′ -x ′ )), which satisfies, for β < β o , with the above choice of ϕ, ϕ k C 1,β (B1(x ′ )) ≤ ϕ C 1,β .
We consider

u k (y) = r -1-β k (u(r k (y -x) + x) -p k • (r k (y -x) + x)) .
u k is well defined on B 1 (x) ∩ {y N > a k (y ′ )}, where a k (y

′ ) = x N (1 -1 r k ) + a(r k (y ′ -x ′ )+x ′ ) r k . It is immediate to see that u k is a solution of |p k r -β k + ∇u k | α (F (D 2 u k ) + h k • (p k r -β k + ∇u k )) = f k in B 1 (x) ∩ {y N > a k (y ′ )} u k + r -β k p k • y = r -β k (r k -1)p k • x + ϕ k (y ′ ) on B 1 (x) ∩ {y N = a k (y ′ )} with f k (y) = r 1-β(1+α) k f (r k (y -x) + x) and h k (y) = r k h(r k (y -x) + x). Observe that if y ∈ B 1 (x) ∩ {y N = a k (y ′ )}, then a(r k (y ′ -x ′ ) + x ′ ) -x N r k ≤ 1
but this implies, using the mean value's theorem and |y

′ -x ′ | < 1, that |x N -a(x ′ )| ≤ r k (1 + |∇a|).
So if x is not on the boundary i.e. {x N > a(x ′ )} then, for k sufficiently large, B 1 (x) ⊂ {y N > a k (y ′ )}, and in that case we don't have to worry about the boundary terms.

A direct computation gives that, |∇a k (y

′ )| = |∇a(r k (y ′ -x ′ ) + x ′ )|, while, D 2 a k (y ′ ) = r k D 2 a(r k (y ′ -x ′ ) + x ′ ), and hence D 2 a k ∞ = r k D 2 a ∞ ≤ D 2 a ∞ . Furthermore, as long as β < 1 1+α , osc B1(x)∩{y N >a k (y ′ )} u k ≤ 1, f k L ∞ (B1(x)∩{y N >a k (y ′ )}) ≤ ǫ o and h k ∞ ≤ h ∞ .
Hence, using Lemma ?? with obvious changes, there exists q k+1 ∈ IR N such that osc

Bρ(x)∩{y N >a k (y ′ )} (u k (y) -q k+1 • y) ≤ ρ 2 .
Defining p k+1 = p k + q k+1 r β k , with the assumptions on β and ρ, one gets:

osc Br k+1 (x)∩{y N >a(y ′ )} (u(y) -p k+1 • y) ≤ ρ 2 r 1+β k ≤ r 1+β k+1 ,
since the oscillation is invariant by translation. This is the desired conclusion.

There remains to prove the improvement of flatness lemmata. We start by the interior case with lower order terms.

Proof of Lemma ??. Suppose by contradiction that there exist a sequence of functions (f n ) n whose norm goes to zero, a sequence of (p n ) n ∈ IR N and a sequence of functions (u n ) n with osc u n ≤ 1, solutions of

|p n + ∇u n | α F (D 2 u n ) + h(y) • (∇u n + p n ) = f n , (3.2)
such that, for all q ∈ IR N , and any ρ ∈ (0, 1), osc

Bρ (u n (y) -q • y) > ρ 2 . ( 3.3)
Let us suppose first that (p n ) n is bounded then, up to subsequences, it converges to p ∞ . Considering v n (y) = u n (y) + p n • y and using the compactness Remark ??, we can extract form (v n ) n a subsequence converging to a limit v ∞ , which satisfies

|∇v ∞ | α (F (D 2 v ∞ ) + h(x) • ∇v ∞ ) = 0.
Remark next that the solutions of such an equation are solutions of

F (D 2 v ∞ ) + h(x) • ∇v ∞ = 0 (3.4)
as it is the case for h = 0 (see [?]). But, passing to the limit in (??) gives that osc

Bρ (v ∞ - (q -p ∞ ) • x) > ρ 2 .
This contradicts the regularity results known for solutions of equation (??), (see [?]) and it ends the case where the sequence (p n ) n is bounded.

In the case where (p n ) n is unbounded, take a subsequence such that pn |pn| converges to some p ∞ .

Claim: There exist q ∞ ∈ IR N and a subsequence σ(n) such that for any r < 1,

lim n→∞ h(y) • p σ(n) = h(y) • q ∞
uniformly in B r . We postpone the proof of that claim and we end the proof of Lemma ??.

We now divide the equation (??) by |p n | α and get, with e n = pn |pn| and a n = 1 |pn| ,

|a n ∇u n + e n | α F (D 2 u n ) + h(y) • (∇u n + p n ) = f n |p n | α .
Using Remark ?? and the claim, a subsequence of u σ(n) converges to u ∞ a solution of the limit equation F (D 2 u ∞ ) + h(y) • (∇u ∞ + q ∞ ) = 0. On the other hand, osc(u ∞q ′ • x) > [START_REF] Araujo | Optimal gradient continuity for degenerate elliptic equations[END_REF] 2 ρ, which contradicts the regularity of solutions of such equations.

Proof of the Claim. Let V ⊂ IR N be the space generated by h(B r ). Let q n = Π V p n be the projection of p n on V , hence h(x) • p n = h(x) • q n .

Let p be such that for a subsequence pn |pn| → p, and let

v n := u n + p n • x |p n | .
Clearly v n converges to v ∞ = p • x and it is a solution of

|∇v n | α (F (D 2 v n ) + h(x) • ∇v n ) = f n |p n | 1+α
Using compactness of bounded sequences one obtain by passing to the limit in the equation that v ∞ must be a solution of

|∇v ∞ | α (F (D 2 v ∞ ) + h(x) • ∇v ∞ ) = 0,
hence we have obtained h(x) • p = 0

Let us note that this implies that |qn| |pn| → 0. Indeed suppose that h(x i ) 1≤i≤k generate V , let E j be an orthonormal basis such that

[E 1 , • • • E k ] = [h(x 1 ), • • • h(x k )]
then there exist A i j such that E j = i A i j h(x i ) and q n = (q n • E i )E i = ij (q n • h(x i ))A i j and then

|q n | |p n | ≤ C 1≤i≤k |(q n • h(x i ))| |p n | = C 1≤i≤k p n |p n | • h(x i )) → 0.
Suppose by contradiction that the sequence (q n ) n goes to infinity in norm. Define w n = un+qn•x |qn| . Divide the equation by |p nq n | α |q n |, then w n is a solution of

p n -q n |p n -q n | + |q n | |p n -q n | ∇w n α F (D 2 w n ) + h(y) • ∇w n = f n |p n -q n | α |q n | .
Now, the sequence w n which is bounded converges to w ∞ (x) = q • x for some q of norm 1.

Using the compactness of (w σ(n) ) n , proceeding as above, since |p nq n | α |q n | diverges and since qn |pn-qn| → 0, we get that it converges to a solution of the limit equation

F (D 2 w ∞ ) + h(y) • ∇w ∞ = 0
which implies h(y) • q = 0 for all y ∈ B r . This means that q is both in V and V ⊥ , hence q = 0, which is a contradiction and the sequence (q n ) n is bounded. This gives the claim, indeed, up to a subsequence, q n converges to q ∞ and

Br 1 (

 1 Φ(x, y)) > 0.Clearly x = ȳ. Furthermore the hypothesis on L forces x and ȳ to be in B r 1 +r 2 ∩{y N > a(y ′ )}.

  prove in what follows that L = o(|tr(X + Y )|), that there exist constants c and C such that |X|, |Y | ≤ C|tr(X + Y )| and cM |x -ȳ| γ-2 ≤ |tr(X + Y )| ≤ CM |x -ȳ| γ-2 .

  since |Q| and |tr(X + Y -4L)| are of the same order, and L M = o(1). This will yield the required estimates.

and Lemma 3 . 3 .

 33 For any a ∈ C 2 , such that a(0) = 0 and ∇a(0) = 0, there exist ǫ o > 0 and ρ which depend on (α, λ, Λ, N, D 2 a ∞ , h ∞ , ϕ C 1,βo ) such that for any p ∈ IR N and u a viscosity solution of|p + ∇u| α (F (D 2 u) + h(y) • (∇u + p)) = f in B ∩ {y N > a(y ′ )} u + p • y = ϕon B ∩ {y N = a(y ′ )}.

Lemma 3 . 4 .Remark 3 . 5 .

 3435 Suppose that ρ and ǫ o ∈ [0, 1] and B are as in Lemma ?? and suppose that u is a viscosity solution of|∇u| α (F (D 2 u) + h(y) • ∇u) = f in B ∩ {y N > a(y ′ )} u = ϕ on B ∩ {y N = a(y ′ )} (3.1) with, osc u ≤ 1 and f ∞ ≤ ǫ o ,then, there exists β ∈]0, 1[, such that for all k and for all x ∈ B such that B 1 (x) ⊂ B, there exists p k ∈ IR N for which osc Br k (x)∩{y N >a(y ′ )} (u(y)p k • y) ≤ r 1+β k where r k = ρ k . Of course, in the absence of boundary condition we obtain the interior regularity: Suppose that ρ and ǫ o ∈ [0, 1] are as in Lemma ?? and suppose that u is a viscosity solution of |∇u| α (F (D 2 u) + h(•) • ∇u) = f in B 1

This ends the proof.

We now want to prove Lemma ??. In the case of a non straight boundary it requires the following technical proposition, whose proof is postponed until the end of the section. Proposition 3.6. Suppose that a is not identically zero in B ′ δ (0) and a(0) = ∇a(0) = 0. Suppose that (p n ) n is a sequence in IR N such that, for all n and for all x ∈ B ′ δ (0),

Proof of Lemma ??. We assume first that h = 0.

We argue by contradiction and suppose that for all n, there exist x n ∈ B and

n and u n with osc(u n ) ≤ 1 a solution of

such that for any q ∈ IR N osc Bρ(xn)

Extract from (x n ) n a subsequence which converges to x ∞ ∈ B ∩ {y N ≥ a(y ′ )}. We denote in the sequel

The case where T is not straight.

Observe that u nu n (x n ) satisfies the same equation as u n , it has oscillation 1 and it is bounded, we can then suppose that the sequence (u n ) is bounded. This, together with the boundary condition implies that

and, Proposition ??, gives that (p n ) is bounded.

So, up to subsequences, u n converges to some u ∞ , uniformly on B r ∩ {y N ≥ a(y ′ )} for every B r ⊂⊂ B ∞ , (due to Corollary ?? ), and

Using Lemma 6 in [?] one gets that

On the other hand, by passing to the limit in (??), one obtains osc

This contradicts the fact that, by known regularity results on uniformly elliptic operators, there exists ρ 1 and q 1 = q x,ρ1 so that any u, solution of (??) satisfies osc

The case where T = {y N = 0}. Let

Denoting by p ′ the limit of a subsequence of p ′ n , and u ∞ the limit of a subsequence of (u n ), one gets by passing to the limit and using Corollary ?? that

Passing to the limit in (??) one gets that osc Bρ(x∞) (u ∞q • y) > ρ 2 , a contradiction. This ends the proof for h = 0.

We briefly point out the differences in the case h = 0. It is sufficient to treat the case of a straight boundary, the other cases being as before. Indeed, we already know that if the boundary is not locally straight, ( p n ) n is bounded.

In the case where the boundary is locally straight, say T = {y N = 0} so that the only possibly unbounded component is

The Claim in the interior flatness Lemma ?? implies that for any open set D ⊂ B r (x) ∩ {y N > 0}, h(y) • e N = 0 for any y ∈ D. By the arbitrariness of D, this implies that h(y) • e N = 0 in B r (x) ∩ {y N > 0}. We can now apply Proposition ?? and end as in the case h = 0.

We end the paper with the proof of Proposition ??.

The thesis of the proposition is proved if there exists

Since a is not identically 0 on [-δ, δ] and a(0) = 0, ∇a(0) = 0, then there exists i such that a(te i ) is not constant for t ∈ [-δ, δ]. Hence, there exist 0 < |t 1 | < δ and |t 2 | < δ such that the vectors V i := t 1 e i + a(t 1 e i )e N and V N := t 2 e i + a(t 2 e i )e N are linearly independent. Indeed, since a is not constant there exists t 1 and e i such that a(t 1 e i ) = 0. Suppose now that for any t 2 , V i and V N are linearly dependent, this implies that a(t 1 e i ) t 1 = a(t 2 e i ) t 2 = ∂ i a(0) = 0 a contradiction Now, for j = i and j = N choose V j = t 1 e j + a(t 1 e j )e N . By constructions the V j for j = 1, . . . , N are linearly independent and by hypothesis |p n • V j | ≤ C this ends the proof.


Sébastien Destercke
email: sebastien.destercke@hds.utc.fr

Gen Yang
email: gen.yang@hds.utc.fr

Cautious Ordinal Classification by Binary Decomposition

Keywords: Ordinal regression, imprecise probabilities, Binary decomposition, Nested dichotomies

We study the problem of performing cautious inferences for an ordinal classification (a.k.a. ordinal regression) task, that is when the possible classes are totally ordered. By cautious inference, we mean that we may produce partial predictions when available information is insufficient to provide reliable precise ones. We do so by estimating probabilistic bounds instead of precise ones. These bounds induce a (convex) set of possible probabilistic models, from which we perform inferences. As the estimates or predictions for such models are usually computationally harder to obtain than for precise ones, we study the extension of two binary decomposition strategies that remain easy to obtain and computationally efficient to manipulate when shifting from precise to bounded estimates. We demonstrate the possible usefulness of such a cautious attitude on tests performed on benchmark data sets.

Introduction

We are interested in the supervised learning problem known as ordinal classification [START_REF] Frank | A simple approach to ordinal classification[END_REF] or regression [START_REF] Chu | Support vector ordinal regression[END_REF]. In this problem, the finite set of possible labels are naturally ordered. For instance, the rating of movies can be one of the following labels: Very-Bad, Bad, Average, Good, Very-Good that are ordered from the worst situation to the best. Such problems are different from multi-class classification and regression problems, since in the former there is no ordering between classes and in the latter there exists a metric on the outputs (while in ordinal classification, a 5-star movie should not be considered five times better than a 1-star movie).

A common approach to solve this problem is to associate the labels to their rank, e.g., {1, 2, 3, 4, 5} in our previous film example, and then to learn a ranking function. In the past years, several algorithms and methods [START_REF] Sousa | Multicriteria models for learning ordinal data: A literature review[END_REF] have been proposed to learn such a function, such as SVM techniques [START_REF] Shashua | Ranking with large margin principle: Two approaches[END_REF][START_REF] Herbrich | Large margin rank boundaries for ordinal regression[END_REF][START_REF] Joachims | Training linear svms in linear time[END_REF][START_REF] Li | Ordinal regression by extended binary classification[END_REF], monotone functions [START_REF] Tehrani | Preference learning using the choquet integral: The case of multipartite ranking[END_REF], binary decomposition [START_REF] Fürnkranz | Binary decomposition methods for multipartite ranking[END_REF], rule based models [START_REF] Dembczyński | Learning rule ensembles for ordinal classification with monotonicity constraints[END_REF]. This is not the approach followed in this paper, in which our goal is to estimate the probability of the label conditionally on the observed instance. In this sense, our approach is much closer to the one proposed by Frank et Hall [START_REF] Frank | A simple approach to ordinal classification[END_REF].

A common feature of all the previously cited approaches is that, no matter how reliable is the model and the amount of data it is learned from, it will always produce a unique label as prediction. In this paper, we are interested in making partial predictions when information is insufficient to provide a reliable precise one. That is, if we are unsure of the right label, we may abstain to make a precise prediction and instead predict a subset of potentially optimal labels. The goal is similar to the one pursued by the use of a reject option [START_REF] Bartlett | Classification with a reject option using a hinge loss[END_REF][START_REF] Chow | On optimum recognition error and reject tradeoff[END_REF], and in particular to methods returning subsets of possible classes [START_REF] Alonso | Learning to predict one or more ranks in ordinal regression tasks[END_REF][START_REF] Ha | The optimum class-selective rejection rule. Pattern Analysis and Machine Intelligence[END_REF]. Yet we will see in the experiments that the two approaches can provide very different results.

Besides the fact that such cautious predictions can prevent bad decisions based on wrong predictions, making such imprecise predictions in an ordinal classification setting can also be instrumental in more complex problems that can be decomposed into sets of ordinal classification problem, such as graded multi-label [7] or label ranking [START_REF] Cheng | A nearest neighbor approach to label ranking based on generalized labelwise loss minimization 7[END_REF]. Indeed, in such problems with structured outputs, obtaining fully reliable precise predictions is much more difficult, hence producing partial but more reliable predictions is even more interesting [START_REF] Cheng | Label ranking with partial abstention based on thresholded probabilistic models[END_REF].

To obtain these cautious predictions, we propose to estimate sets of probabilities [START_REF] Corani | Bayesian networks with imprecise probabilities: Theory and application to classification[END_REF] from the data in the form of probabilistic bounds over specific events, and to then derive the (possibly) partial predictions from it. As computations with generic methods using sets of probabilities (e.g., using imprecise graphical models [START_REF] Corani | Bayesian networks with imprecise probabilities: Theory and application to classification[END_REF]) can be quite complex, we propose in Section 2 to consider two well-known binary decompositions whose extension to probability sets keep computations tractable, namely Frank & Hall decomposition [START_REF] Frank | A simple approach to ordinal classification[END_REF] and nested dichotomies decompositions [START_REF] Frank | Ensembles of nested dichotomies for multi-class problems[END_REF]. In Section 3, we discuss how to perform inferences from such probability sets both with general loss functions and with the classical 0/1 loss function. We end (Section 4) by providing several experiments showing that our cautious approach can help identify hard to predict cases and provides more reliable predictions for those cases.

Probability Set Estimation Through Binary Decomposition

The goal of ordinal classification is to associate an instance x = x 1 × . . . × x p coming from an instance space X = X 1 × . . . × X p to a single label of the space Y = {y 1 , . . . , y m } of possible classes. Ordinal classification differs from multi-class classification in that labels y i are ordered, that is y i ≺ y i+1 for i = 1, . . . , m -1. An usual task is then to estimate the theoretical conditional probability measure

P x : 2 Y → [0, 1] associ- ated to an instance x from a set of n training samples (x i , ℓ x i ) ∈ X × Y , i = 1, . . . , n.
In order to derive cautious inferences, we shall explore in this paper the possibility to provide a convex set P x of probabilities as an estimate rather than a precise probability Px , with the idea that the size of P x should decrease as more data (i.e., information) become available, converging to P x .

Manipulating generic sets P x to compute expectations or make inferences can be tedious, hence it is interesting to focus on collections of assessments that are easy to obtain and induce sets P x that allow for easy computations. Here we focus on the extensions of two particularly attractive binary decomposition techniques already used to estimate a precise Px , namely Frank et Hall [START_REF] Frank | A simple approach to ordinal classification[END_REF] technique and nested dichotomies [START_REF] Frank | Ensembles of nested dichotomies for multi-class problems[END_REF].

Imprecise Cumulative Distributions

In their original paper, Frank et Hall suggest [START_REF] Frank | A simple approach to ordinal classification[END_REF] to estimate, for an instance x, the probabilities that its output ℓ x will be less or equal than y k , k = 1, . . . , m -1. That is, one should estimate the m -1 probabilities P x (A k ) := F x (y k ) where A k = {y 1 , . . . , y k }, the mapping F x : Y → [0, 1] being equivalent to a discrete cumulative distribution. The probabilities P x (ℓ x = y k ) can then be deduced through the formula

P x ({y k }) = F x (y k ) - F x (y k-1 ).
The same idea can be applied to sets of probabilities, in which case we estimate the bounds

P x (A k ) := F x (y k ) and P x (A k ) := F x (y k ),
where F x , F x : Y → [0, 1] correspond to lower and upper cumulative distributions. These bounds induce a well-studied [START_REF] Destercke | Unifying practical uncertainty representations -i: Generalized p-boxes[END_REF] probability set P x ([F, F]). For P x ([F, F]) to be properly defined, we need the two mappings F x , F x to be increasing with F x (y m ) = F x (y m ) = 1 and to satisfy the inequality F x ≤ F x . In practice, estimates F x , F x obtained from data will always satisfy the latest inequality, however when using binary classifiers on each event A k , nothing guarantees that they will be increasing, hence the potential need to correct the model. Algorithm 1 provides an easy way to obtain a well-defined probability set. In spirit, it is quite similar to the Frank et Hall estimates

P x (y k ) = max{0, F x (y k )-F x (y k-1
)}, where an implicit correction is performed to obtain well-defined probabilities in case F x is not increasing.

Algorithm 1: Correction of estimates F x , F x into proper estimates Input: estimates F x , F x obtained from data Output: corrected estimates F x , F x 1 for k=1,. . . ,m-1 do

2 if F x (y k ) > F x (y k+1 ) then F x (y k+1 ) ← F x (y k ); 3 if F x (y m-k+1 ) < F x (y m-k ) then F x (y m-k ) ← F x (y m-k+1 );

Nested Dichotomies

The principle of nested dichotomies is to form a tree structure using the class values y i ∈ Y . A nested dichotomy consists in recursively partitioning a tree node C ⊆ Y into two subsets A and B such that A ∩ B = / 0 and A ∪ B = C, until every leaf-node corresponds to a single class value (card(C) = 1). The root node is the whole set of classes Y . To each branch A and B of a node C are associated conditional probabilities P x (A|C) = 1 -P x (B|C). In the case of ordinal classifications, events C are of the kind {y i , y i+1 , . . . , y j } and their splits of the kind A = {y i , y i+1 , . . . , y k } and B = {y k+1 , . . . , y j }.

Generalizing the concept of nested dichotomies is pretty straightforward: it consists in allowing every local conditional probability to be imprecise, that is to each node C can be associated an interval [P x (A | C), P x (A | C)], precise nested dichotomies being retrieved when P x (A | C) = P x (A | C) for every node C. By duality of the imprecise probabilities [30, Sec.2.7.4.], we have P

x (A | C) = 1 -P x (B | C) and P x (A | C) = 1 - P x (B | C).
Such an imprecise nested dichotomy is then associated to a set P x of joint probabilities, obtained by considering all precise selection P 1 shows examples of a precise and an imprecise nested dichotomy tree when Y = {y 1 , y 2 , y 3 }.

x (A | C) ∈ [P x (A | C), P x (A | C)] for each node C. Figure
Y = {y 1 , y 2 , y 3 } C = {y 1 , y 2 } {y 1 } P x (y 1 | C) = 0.6 {y 2 } P x (y 2 | C) = 0.4 P x ({y 1 , y 2 }) = 0.7 {y 3 } P(y 3 ) = 0.3 Y = {y 1 , y 2 , y 3 } C = {y 1 , y 2 } {y 1 } [P x (y 1 | C), P x (y 1 | C)] = [0.6, 0.8] {y 2 } [P x (y 2 | C), P x (y 2 | C)] = [0.2, 0.4] [P x ({y 1 , y 2 }), P x ({y 1 , y 2 })] = [0.6, 0.8] {y 3 } [P x (y 3 ), P x (y 3 )] = [0.2, 0.4]

Inferences

In this section, we expose how inferences (decision making) can be done with our two decompositions, both with general costs and 0/1 costs. While other costs such as the absolute error cost are also natural in an ordinal classification setting [START_REF] Dembczyński | Learning rule ensembles for ordinal classification with monotonicity constraints[END_REF], we chose to focus on the 0/1 cost, as it is the only one for which a theoretically sound way to compare determinate and indeterminate classifiers, i.e., classifiers returning respectively precise and (potentially) imprecise classification, has been provided [START_REF] Zaffalon | Evaluating credal classifiers by utility-discounted predictive accuracy[END_REF].

We will first recall the basic of decision making with probabilities and will then present their extensions when considering sets of probabilities. Let us denote by c k : Y → R the cost (loss) function associated to y k , that is c k (y j ) is the cost of predicting y k when y j is true. In the case where precise estimates P x (y k ) are obtained from the learning algorithm, obtaining the optimal prediction is ŷ = arg min

y k ∈Y E x (c k )
with E x the expectation of c k under P x , i.e. we predict the value having the minimal expected cost.

In practice, this also comes down to build a preference relation ≻ P on elements of Y , where

y l ≻ P x y k iff E x (c k ) > E x (c l ) or equivalently E x (c k -c l ) > 0, that
is the expected cost of predicting y l is lower than the expected cost of predicting y k . When working with a set P x of probabilities, this can be extended by building a partial order

≻ E x on elements of Y such that y l ≻ E x y k iff E x (c k -c l ) > 0 with E x (c k -c l ) = inf P x ∈P x E x (c k -c l ).
That is, we are sure that the cost of exchanging y k with y l will have a positive expectation (hence y l is preferred to y k ). The final cautious prediction Ŷ is then obtained by taking the maximal elements of the partial order ≻ E x , that is

Ŷ = {y ∈ Y : ∃y ′ = y s.t. y ′ ≻ E x y}
and is known under the name maximality criterion [START_REF] Walley | Statistical reasoning with imprecise Probabilities[END_REF][START_REF] Troffaes | Decision making under uncertainty using imprecise probabilities[END_REF]. In practice, getting Ŷ requires at worst a number m(m-1) /2 of computations that is quadratic in the number of classes. A conservative approximation (in the sense that the obtained set of nondominated classes includes Ŷ ) can be obtained by using the notion of interval dominance [START_REF] Troffaes | Decision making under uncertainty using imprecise probabilities[END_REF], in which y l ≻ E x y k if E x (c k ) > -E x (-c l ), thus requiring only 2m computations at worst to compare all classes, yet as m is typically low in ordinal classification, we will only consider maximality here.

In particular, 0/1 costs are defined as c k (y j ) = 1 if j = k and 0 else. If we note 1 provides an example of the functions over which lower expectations must be computed for 0/1 losses in the case Y = {y 1 , . . . , y 5 }.

1 (A) the indicator function of A (1 (A) (x) = 1 if x ∈ A, 0 else), then (c k -c l ) = 1 (y l ) -1 (y k ) as c k (y j ) -c l (y j ) = -1 if j = k, 1 if j = l and 0 if j = k, l. Hence we have y l ≻ E x y k iff E x (1 (y l ) -1 (y k ) ) > 0. Table
y 1 y 2 y 3 y 4 y 5 c 2 1 0 1 1 1 c 4 1 1 1 0 1 c 2 -c 4 0 -1 0 1 0
E x ( f ) = m ∑ i=1 ( f (y (i) ) -f (y (i-1) )P x (A (i) ) (1)
with f (y (0) ) = 0,

A (i) = {y (i) , . . . , y (m) } and P x (A (i) ) = inf P x ∈P x ([F,F]) P(A (i) )
is the lower probability of A (i) . In the case of imprecise cumulative distributions, the lower probability of an event A can be easily obtained: 1. The elements used in the computation of the Choquet integral (1) for this case are summarized in Table 3. 1 For details, interested readers are referred to [START_REF] Destercke | Unifying practical uncertainty representations -i: Generalized p-boxes[END_REF]. Shortly speaking, this is due to the supermodularity of the induced lower probability. 2

let C = [y j , y j ] denote a discrete interval of Y such that [y j , y j ] = {y i ∈ Y : j ≤ i ≤ j}, then P x (C) = max{0, F x (y j ) -F x (y j-1 )} with F x (y 0 ) = F x (y 0 ) = 0.
i y (i) f (i) A (i) P x (A (i) ) 1 y 2 -1 Y 1 2 y 1 0 {y 1 , y 3 ,
two intervals [y j , y j ], [y k , y k ] are said disjoint if j + 1 < k
The lower probability of A (2) = {y 1 , y 3 , y 4 , y 5 } = {y 1 } ∪ {y 3 , y 4 , y 5 } is

P x (A (2) ) = P x ({y 1 }) + P x ({y 3 , y 4 , y 5 }) = max{0, F x (y 1 ) -F x (y 0 )} + max{0, F x (y 5 ) -F x (y 2 )} = 0.1 + 0.5,
and the final value of the lower expectation E x (c 2c 4 ) = -0.15, meaning that y 4 is not preferred to y 2 in this case. As we also have E x (c 4c 2 ) = -0.2, y 2 and y 4 are incomparable under a 0/1 loss and given the bounding distributions F x , F x . Actually, our cautious prediction would be Ŷ = {y 2 , y 4 }, as we have y i ≻ E y j for any i ∈ 2, 4 and j ∈ 1, 3, 5.

Inference with Nested Dichotomies

In the precise case, computations of expectations with nested dichotomies can be done by backward recursion and local computations (simply applying the law of iterated expectation). That is the global expectation E x ( f ) of a function f : Y → R can be done by computing local expectations for each node, starting from the tree leaves taking values f (y). This provides nested dichotomies with a computationally efficient method to estimate expectations.

It has been shown [START_REF] De Cooman | Imprecise probability trees: Bridging two theories of imprecise probability[END_REF] that the same recursive method can be applied to imprecise nested dichotomies. Assume we have a split {A, B} of a node C, and a real-valued (cost) function f : {A, B} → R defined on {A, B}. We can compute the (local) lower expectation associated with the node C by :

E x,C ( f ) = min P x (A | C) f (A) + P x (B | C) f (B), P x (A | C) f (A) + P x (B | C) f (B) (2)
Starting from a function such as the one given in Table 1, we can then go from the leaves to the root of the imprecise nested dichotomy to obtain the associated lower expectation.

Example 2. Consider a problem where we have Y = {y 1 , y 2 , y 3 } and the same imprecise dichotomy as in Figure 1. Figure 2 shows the local computations performed to obtain the lower expectation of c 1c 3 . For instance, using Eq. ( 2) on node C = {y 1 , y 2 }, we get

E x,{y 1 ,y 2 } (c 1 -c 3 ) = min{-1 • 0.8 + 0 • 0.2, -1 • 0.6 + 0 • 0.4}
We finally obtain E x,Y (c 1c 3 ) = -0.44, concluding that y 3 is not preferred to y 1 . As the value E x,Y (c 3c 1 ) = -0.04 is also negative, we can conclude that y 1 and y 3 are not comparable. Yet we do have E x,Y (c 2c 1 ) > 0, meaning that y 1 is preferred to y 2 , hence Ŷ = {y 1 , y 3 }.

Experimentations

This section presents the experiments we achieved to compare decomposition methods providing determinate predictions and their imprecise counterpart delivering possibly indeterminate predictions.

{y 3 } [0.2, 0.4] E x,Y = -0.8 • 0.8 + 1 • 0.2 -1 0 1 E x,{y 1 ,y 2 } = -1 • 0.8 + 0 • 0.2 = -0.8
Fig. 2. Expectation computation for c 1c 3 .

Learning method

In our experiments, we consider a base classifier which can be extended easily to output interval-valued probabilities, so that we can evaluate the impact of allowing for cautiousness in ordinal classification. For this reason, we use the Naive Bayesian Classifier (NBC) which has an extension in imprecise probabilities : the Naive Credal Classifier (NCC) [START_REF] Zaffalon | The naive credal classifier[END_REF].

The NCC preserves the main properties of NBC, such as the assumption of attribute independence conditional on the class. In binary problems where we have to differentiate between two complementary events A and B, NBC reads

P(A|x 1 , . . . , x p ) = P(A) ∏ p i=1 P(x i | A) ∏ p i=1 P(x i | A)P(A) + ∏ p i=1 P(x i | B)P(B) , (3)
where (x 1 , . . . , x p ) are the feature variables and A, B are the two events whose probability we have to estimate. The NCC consists in using probability bounds in Eq. 3, getting

P(A|x 1 , . . . , x p ) = min        P(A) ∏ p i=1 P(x i |A) ∏ p i=1 P(x i |A)P(A)+∏ p i=1 P(x i |B)P(B) , P(A) ∏ p i=1 P(x i |A) ∏ p i=1 P(x i |A)P(A)+∏ p i=1 P(x i |B)P(B)        = 1 -P(B|x 1 , . . . , x p ). ( 4
)
and P(B|x 1 , . . . , x p ) = 1 -P(A|x 1 , . . . , x p ) can be obtained in the same way. Using the Imprecise Dirichlet Model (IDM) [START_REF] Bernard | An introduction to the imprecise dirichlet model for multinomial data[END_REF], we can compute these probability estimates from the training data by simply counting occurrences :

P(x i | A) = occ i,A occ A + s , P(x i | A) = occ i,A + s occ A + s (5)
and

P(A) = occ i,A n A,B + s , P(A) = occ i,A + s n A,B + s (6)
where occ i,A is the number of instances in the training set where the attribute X i is equal to x i and the class value is in A, occ A the number of instances in the training set where the class value is in A, n A,B is the number of training sample whose class is either in A or B. The hyper-parameter s that sets the imprecision level of the IDM is usually equal to 1 or 2 [START_REF] Walley | Inferences from multinomial data: learning about a bag of marbles[END_REF].

Evaluation

Comparing classifiers that return cautious (partial) predictions in the form of multiple classes is an hard problem. Indeed, compared to the usual setting, measures of performance have to include the informativeness of the predictions in addition to the accuracy. Zaffalon et al. [START_REF] Zaffalon | Evaluating credal classifiers by utility-discounted predictive accuracy[END_REF] discuss in details the case of comparing a cautious prediction with a classical one under a 0/1 loss assumption, using a betting interpretation. They show that the discounted accuracy, which rewards a cautious prediction Y class with 1 /|Y| if the true class is in Y , and zero otherwise, is a measure satisfying a number of appealing properties. However, they also show that discounted accuracy makes no difference between a cautious classifier providing indeterminate predictions and a random classifier: for instance, in a binary setting, a cautious classifier always returning both classes would have the same value as a classifier picking the class at random, yet the determinate classifier displays a lower variance (it always receives 1 /2 as reward, while the random one would receive a reward of 1 half of the time, and 0 the other half). This is why a decision maker that wants to value cautiousness should consider modifying discounted accuracy by a risk-adverse utility function [START_REF] Zaffalon | Evaluating credal classifiers by utility-discounted predictive accuracy[END_REF]. Here, we consider the u 65 function: Let (x i , ℓ i ), i = 1, . . . , n be the set of test data and Y i our (possibly imprecise) predictions, then u 65 is

u 65 = 1 n n ∑ i=1 -0.6d 2 i + 1.6d i ,
where

d i = 1 (Y i ) (ℓ i ) /|Y i |
is the discounted accuracy. It has been shown in [START_REF] Zaffalon | Evaluating credal classifiers by utility-discounted predictive accuracy[END_REF] that this approach is consistent with the use of F 1 measures [START_REF] Del Coz | Learning nondeterministic classifiers[END_REF][START_REF] Alonso | Learning to predict one or more ranks in ordinal regression tasks[END_REF] as a way to measure the quality of indeterminate classifications. In fact, it is shown in [START_REF] Zaffalon | Evaluating credal classifiers by utility-discounted predictive accuracy[END_REF] that u 65 is less in favor of indeterminate classifiers than the use of F 1 measure.

Results

In this section, our method is tested on 19 datasets of the UCI machine learning repository [START_REF] Frank | UCI machine learning repository[END_REF], whose details are given in Table 4. As there is a general lack of benchmark data sets for ordinal classification data, we used regression problems that we turned into ordinal classification by discretizing the output variable, except for the data sets LEV that has 5 ordered classes and ESL, ERA that have 9 ordered classes. The results reported in this section are obtained with a discretization into five classes of equal Table 4. Data set details frequencies. We also performed experiments on the other data sets, using 7 and 9 discretized classes, obtaining the same conclusions. The results in this section are obtained from a 10-fold cross validation. To build the dichotomy trees, we selected at each node the split A = {y i , y i+1 , . . . , y k } and B = {y k+1 , . . . , y j } of C = {y i , y i+1 , . . . , y j } that maximised the u 65 measure on the binarized data set. We use ordinal logistic regression (logreg) as a base line classifier to compare our results. For each decomposition method, Frank & Hall (F) and nested dichotomies (N), we compared the naive Bayes classifier (B) with its indeterminate counterpart (NCC), picking an hyper-parameter s = 2 for the IDM in Eqs. ( 5)- [START_REF] Cheng | A nearest neighbor approach to label ranking based on generalized labelwise loss minimization 7[END_REF]. The naive Bayes classifier was used in a classical way to provide determinate predictions and (B/A) with the F 1 measure of Alonso et al. [START_REF] Alonso | Learning to predict one or more ranks in ordinal regression tasks[END_REF] to produce indeterminate predictions (details about this latter method can be found in [START_REF] Alonso | Learning to predict one or more ranks in ordinal regression tasks[END_REF]).

Table 5 show the obtained results in terms of u 65 (that reduces to classical accuracy for the three determinate methods) as well as the rank of each classifier. Using Demsar's approach by applying the Friedman statistic on the ranks of algorithm performance for each dataset, we obtain a value of 68.16 for the Chi Square, and a 26.8 statistic for the F-distribution. Since the statistic is 1.7 for a p-value of 0.05, we can safely reject the null hypothesis, meaning that the performances of the classifiers are significatively different. This shows that in average the introduced indeterminacy (or cautiousness) in the predictions is not too important and is compensated by more reliable predictions. We use Nemenyi test as a post-hoc test, and obtain that two classifiers are significantly Figure 3 summarises the average ranks of the different methods and shows which one are significatively different from the others. We can see that, although techniques using probability sets (C/N and C/F) have the best average rank, they are not significantly different from their determinate Bayesian counterpart (B/N and B/F) under u 65 measure. This is not surprising, since the goal of such classifiers is not to outperform Bayesian methods, but to provide more reliable predictions when not enough information is available. It should also be recalled that the u 65 measure is only slightly favourable to indeterminate classifiers, and that other measures such as F 1 and u 80 would have given better scores to indeterminate classifiers.

An interesting result is that Alonso et al. [START_REF] Alonso | Learning to predict one or more ranks in ordinal regression tasks[END_REF] method, that use a precise probabilistic models and produce indeterminate predictions through the use of specific cost functions (the F 1 measure in our case), performs quite poorly, in particular when applied with the Frank and Hall decomposition (B/F/A). This can be explained by the fact that Alonso et al. [START_REF] Alonso | Learning to predict one or more ranks in ordinal regression tasks[END_REF] method will mainly produce indeterminate classifications when the labels having the highest probabilities will have close probability values, i.e., when there will be some ambiguity as to the modal label. However, it is well known that the naive Bayes classifier tends to overestimate model probabilities, therefore acting as a good classifier for 0/1 loss functions, but as a not so good probability density estimator. This latter feature can clearly be counter-productive when using Alonso et al. [START_REF] Alonso | Learning to predict one or more ranks in ordinal regression tasks[END_REF] method, that relies on having good probability estimates. On the other hand, indeterminate classification using probability sets can identify situations where information is lacking, even if the underlying estimator is poor. Our results indicate that, while the two methods both produce indeterminate classifications, they do so in very different ways (and therefore present different interests).

Table 6 shows the mean imprecision of indeterminate predictions for all the methods producing such predictions. This sheds additional light on the bad performances of the B/F/A method, which tends to produce rather imprecise predictions without necessarily counterbalancing them with an higher reliability or accuracy. For the other methods, the mean imprecision is comparable.

Figures 4 displays the non-discounted accuracy (that is, we count 1 each time the true class is in the prediction, whether its determinate or not) on those instances where Table 6. Mean imprecision of predictions (rank) the use of NCC returned an indeterminate classification. On those instances, the accuracy of the determinate version (NBC) is on average 10 % lower than the accuracy displayed in Table 5. In contrast, the non-discounted accuracy of the indeterminate version on these instances is much higher, meaning that the indeterminacy actually concerns hard-to-classify instances.

Conclusions

In this paper, we have proposed two methods to learn cautious ordinal classifiers, in the sense that they provide indeterminate predictions when information is insufficient to provide a reliable determinate one. More precisely, these methods extend two wellknown binary decomposition methods previously used for ordinal classification, namely Frank & Hall decomposition and nested dichotomies. The extension consists in allowing one to provide interval-valued probabilistic estimates rather than precise ones for each binary problem, the width of the interval reflecting our lack of knowledge about the instances. Our experiments on different data sets show that allowing for cautiousness in ordinal classification methods can increase the reliability of the prediction, while not providing too indeterminate predictions. More specifically, indeterminacy tends to focus on those instances that are hard to classify for determinate classifiers. We could probably improve both the efficiency of inferences, e.g., by studying extensions of labelling trees to imprecise trees [START_REF] Bengio | Label embedding trees for large multi-class tasks[END_REF], or their accuracy by using more complex classifiers, e.g., [START_REF] Corani | Credal model averaging: an extension of bayesian model averaging to imprecise probabilities[END_REF]. Yet, as the number m of labels in ordinal classification is usually small, and as the advantages of using binary decompositions are usually lower when using complex estimation methods, the benefits of such extensions would be limited.

In these experiments, we have focused on the 0/1 loss and its extensions to indeterminate classification u 65 , which is more favourable to determinate classifier than the F 1 measure proposed by Alonso et al. [START_REF] Alonso | Learning to predict one or more ranks in ordinal regression tasks[END_REF].The reason for this is that 0/1 loss is the only one to which the results of Zaffalon et al. [START_REF] Zaffalon | Evaluating credal classifiers by utility-discounted predictive accuracy[END_REF] that allows to compare determinate and indeterminate classifiers apply. Yet, our approaches can easily handle generic losses (in contrast with the multi-class naive credal classifier [START_REF] Zaffalon | The naive credal classifier[END_REF]), as shows Section 3 and Eqs (1)- [START_REF] Bartlett | Classification with a reject option using a hinge loss[END_REF]. Also, there are loss functions such as the absolute error that are at least as natural to use in an ordinal classification problem as the 0/1 loss function. Our future efforts will therefore focus on determining meaningful ways to compare cost-sensitive determinate and indeterminate classifiers. Another drawback of using 0/1 loss function [START_REF] Kotlowski | On nonparametric ordinal classification with monotonicity constraints[END_REF], shown by Examples 1 and 2, is that we may obtain indeterminate predictions containing non-consecutive labels. We expect that considering other losses such as L 1 loss could solve this issue.

In addition to that, we plan to apply the methods developed in this paper to more complex problems that can be reduced as a set of ordinal classification problems, such as graded multi-label [7] or label ranking [START_REF] Cheng | A nearest neighbor approach to label ranking based on generalized labelwise loss minimization 7[END_REF].

Fig. 1 .

 1 Fig. 1. Precise (above) and imprecise (below) nested dichotomies

Fig. 4 .

 4 Fig. 4. Non-discounted accuracy of the NBC vs NCC methods for both decompositions on indeterminate instances

Table 1 .

 1 0/1 cost functions comparing y 2 and y 43.1 Inference with Imprecise Cumulative DistributionsIf the probability set P x ([F, F]) is induced by the bounding cumulative distributions [F x , F x ], then it can be shown 1 that the lower expectation of any function f over Y can be computed through the Choquet Integral: if we denote by () a reordering of elements of Y such that f (y (1) ) ≤ . . . ≤ f (y (m) ), this integral reads

Table 2 .

 2 Imprecise

		y 1	y 2	y 3	y 4	y 5
	F x	0.15	0.5	0.55	0.95	1
	F x	0.1	0.4	0.5	0.8	1

Any event A can then be expressed as a union of disjoint intervals 2 A = C 1 ∪ . . . ∪C M , and we have

[START_REF] Destercke | Unifying practical uncertainty representations -i: Generalized p-boxes[END_REF]

P x (A) = ∑ M i=1 P x (C i ). cumulative distribution

Example 1. Consider the imprecise cumulative distributions defined by Table

2

together with a 0/1 loss and the function c 2c 4 of Table

Table 3 .

 3 Choquet integral components of Example 1

  Y = {y 1 , y 2 , y 3 }

	[0.6, 0.8]
	C = {y 1 , y 2 }
	[0.6, 0.8]	[0.2, 0.4]
	{y 1 }	{y 2 }

Table 5 .

 5 u 65 Results (and method rank) obtained on the different methods. Log= logistic regression, B = Naive Bayes classifier, C = Naive credal classifier, A= Alonso et al.

		Log	B/F	B/F/A	C/F	B/N	B/N/A	C/N
	autoPrice	52.2 (5) 58.5 (3) 39.7 (7) 53.8 (4) 59.1 (1) 51.3 (6) 58.6 (2)
	bank8FM	68.2 (2) 67.4 (3) 37.3 (7) 68.3 (1) 63.9 (5) 54.9 (6) 64.8 (4)
	bank32NH	43.3 (4) 43.6 (3) 30.2 (7) 47.8 (1) 42.9 (5) 40.2 (6) 46.7 (2)
	boston hous. 55.6 (4) 55.1 (5) 34.1 (7) 55.8 (3) 56.1 (2) 43.9 (6) 57.4 (1)
	california hous. 47.6 (5) 48.2 (4) 32.9 (7) 48.6 (2) 48.3 (3) 43.5 (6) 48.7 (1)
	cpu small	58.8 (3) 57 (5) 40.9 (7) 57.1 (4) 60.8 (2) 54.1 (6) 61.1 (1)
	delta ail.	50.2 (6) 53.5 (4) 31.8 (7) 53.8 (3) 54.2 (2) 52.1 (5) 54.9 (1)
	elevators	42.7 (2) 39.0 (5) 30.5 (7) 39.2 (4) 42.6 (3) 37.9 (6) 42.9 (1)
	delta elev.	46.5 (6) 49.9 (5) 34.3 (7) 50.4 (4) 50.8 (3) 53.2 (1) 51.2 (2)
	friedman	53.2 (5) 63.8 (2) 32 (7) 64.5 (1) 62.2 (4) 47.3 (6) 63 (3)
	house 8L	39.9 (6) 49.6 (2) 34.9 (7) 49.8 (1) 49.4 (4) 43.9 (5) 49.6 (3)
	house 16H	41.4 (6) 47.5 (4) 35.3 (7) 47.6 (3) 50.0 (2) 43.9 (5) 50.2 (1)
	kinematics	37.7 (5) 44.9 (3) 28.8 (7) 46.2 (1) 44.4 (4) 37.5 (6) 45.4 (2)
	puma8NH	30.3 (6) 46.5 (4) 29.7 (7) 47.6 (3) 47.7 (2) 42.9 (5) 48.3 (1)
	puma32H	30.5 (6) 48.6 (3) 29.7 (7) 50.9 (1) 47.7 (4) 40.6 (5) 49.9 (2)
	stock	61.2 (6) 72.4 (3) 41.7 (7) 71.5 (4) 75.1 (1) 61.2 (5) 74.2 (2)
	ERA	23.2 (5) 23.2 (4) 14.1 (7) 28.5 (1) 22.5 (6) 26.8 (2) 26.6 (3)
	ESL	12.7 (7) 55.7 (4) 28.1 (6) 53.4 (5) 57 (2) 63 (1) 56.5 (3)
	LEV	46.3 (6) 60.5 (2) 44.9 (7) 60.4 (3) 59.8 (4) 61.6 (1) 59.6 (5)
	Avg. rank	5	3.6	6.9	2.6	3.1	4.7	2.1
	prediction method, F = Frank & Hall, N = Nested Dichotomies.

Acknowledgements

This work was carried out and funded by the French National Research Agency, through the project ANR-13-JS03-0007 RECIF. It was also supported by the French Government, through the LABEX MS2T and the program "Investments for the future" managed by the National Agency for Research (Reference ANR-11-IDEX-0004-02).


S Destercke
email: sebastien.destercke@hds.utc.fr

Comments on "Learning from Imprecise and Fuzzy Observations: Data Disambiguation through Generalized Loss Minimization" by Eyke Hüllermeier

Eyke Hüllermeier provides a very convincing approach to learn from fuzzy data, both about the model and about the data themselves. In the process, he links the shape of fuzzy sets with classical loss functions, therefore providing strong theoretical links between fuzzy modeling and more classical machine learning approaches. This short note discusses various aspects of his proposal as well as possible extensions. I will first discuss the opportunity to consider more general uncertainty representations, before considering various alternatives to the proposed learning procedure. Finally, I will briefly discuss the differences I perceive about a loss-based and a likelihood-based approach.

Introduction

The paper [START_REF] Hüllermeier | Learning from imprecise and fuzzy observations: Data disambiguation through generalized loss minimization[END_REF] by Eyke Hüllermeier is a crystal clear exposition of what I think are two important contributions: first, he lays bare the idea of data disambiguation, i.e., the fact that in case of data uncertainty learning about the model and about the data should go "hand in hand"; second he makes a formal connection between learning with fuzzy data and learning with specific loss functions. This latter contribution may even be more important than the first, as it provides fuzzy sets and fuzzy modeling with a clear interpretation in terms of loss functions, therefore bringing them closer to classical machine learning techniques.

The paper provides a generic method and illustrates it on simple examples, showing why it makes sense to use such a method. It opens wide area of potential research, in terms of problems to which the method can be applied to. Yet I think the view of the author as well as the idea of data disambiguation could be expanded in various ways, which I briefly discuss here. My background being mainly in uncertainty treatment, my comments will focus on that aspect rather than on aspects related to learning issues. I will address the following points:

• The extension of the proposed method to more general uncertainty models, with short examples;

• The possibility of using other "choice" rules, including non-precise ones;

• The disambiguation process and its ambiguity in the fuzzy case;

• The differences between a likelihood-based approach and a loss-based approach.

The use of more general uncertainty models

In the paper, data uncertainty is considered to be described by fuzzy sets, reduced to the case of classical sets or intervals in the first part to facilitate exposure. As fuzzy sets are known to be somehow of limited expressiveness (e.g., they do not include probabilities as particular cases), I think there may be some interest in extending the current proposal to more generic models of uncertainty. In particular, since the value L(Y, ŷ) of the fuzzy loss function can be interpreted as a lower expectation (provided the possibility measure induced by the fuzzy set is read as an upper probability [START_REF] Dubois | When upper probabilities are possibility measures[END_REF]), its extension to the case where the uncertainty of an observation Y i is described by a (convex) probability set M i would be straightforward. Namely, given a model M, an observation x i and a loss function L, the generalized loss function

L(Y i , M(x i )) would read as L(Y i , M(x i )) = inf p∈M i E(L(Y i ), M(x i )) (1)
with E the expectation of the function L of the random variable Y i having distribution p ∈ M i . As Walley's lower previsions [START_REF] Walley | Statistical reasoning with imprecise Probabilities[END_REF] provide a subjective interpretation of M i without necessitating the assumption that there exists a precise yet unknown probability inside M i , I think this kind of modeling is in line with the data uncertainty considered in the paper. I see at least two advantages in doing that:

• It would include both fuzzy and probabilistic uncertainty as particular instances;

• It would allow for more general statements of uncertainty when labeling the data, that could not be properly modeled by fuzzy sets nor probabilities. For instance, over a finite set of classes λ 1 , . . . , λ K , experts could provide lower and upper probabilistic bounds over each class [START_REF] De Campos | Probability intervals: a tool for uncertain reasoning[END_REF] (statements of the kind

ℓ i ≤ p(λ i ) ≤ u i )
or even provide comparative statements inducing a partial order over the likelihood of observing the classes [START_REF] Miranda | Extreme points of the credal sets generated by elementary comparative probabilities[END_REF] (statements of the kind p(λ i ) ≤ p(λ j )).

The obvious disadvantages of such an extension to the proposed framework would be an increased computational cost (which could be limited if chosen uncertainty models remain simple enough), and perhaps more importantly a less obvious connection with loss functions, as the uncertainty models could not be reduced to a simple function over the space Y .

The "minimin" approach vs other ones

The approach adopted in the paper can be considered as a decision problem in which an optimistic or a "minimin" approach is adopted. That is, the chosen model (and the associated data disambiguation) is the one that optimizes our decision in the best possible situation. I agree that in the case considered by Eyke Hüllermeier, that is learning a unique best possible model, the "minimin" choice made in the paper is probably the most sensible one, as other decision rules leading to a unique choice (such as minimax or minimax regret) would lead to another unique model likely to not make the best out of the situation. This is quite different from risk analysis or robust optimization problems, where the decision maker wants to prevent him/herself against uncertainty.

However, the alternative mentioned by Eyke Hüllermeier to select a set of optimal models, for instance using the partial ordering induced by the whole distributions r M (α) in the fuzzy case, or using other approaches such as stating that M 1 is preferred to M 2 when the condition min {L(y, M 1 (x)) -L(y, M 2 (x))|(x, y) ∈ X ×Y } > 0 is satisfied1 , seems to me very interesting. Such approaches would be less conservative than simply applying the extension principle, yet would provide cautious decisions allowing for abstention, as well as a kind of partial disambiguation, as not all replacements would have the same status with respect to the set of possibly optimal models. As the unique optimal model retained in the paper would still be included in this set, one could then still decide to use it in order to obtain a unique model and disambiguation if needed. Of course, the challenge of adopting such a view would be to come up with computationally efficient methods, especially in large problems.

The disambiguation process

In the interval or set-valued data case, the data disambiguation process provides a (unique) precise disambiguation or selection, which is a nice result. However, in the fuzzy data case, the disambiguation process currently ends up with a gradual element (number in the case of real-valued data), and it is not clear in the paper how one can go from this gradual element to a crisp and precise replacement (this remark extends to Equation [START_REF] De Campos | Probability intervals: a tool for uncertain reasoning[END_REF], where the disambiguation would be the selected probability distribution). I may be wrong, but in the paper there seems to be no proposed means to obtain a unique precise disambiguation from fuzzy data. Should we select a given alpha-cut? The average value of the gradual element (if such an average can be defined)? The prediction provided by the optimal model and included in the fuzzy set support?

One alternative to obtain such a disambiguation using ideas similar to those of this paper would be to search such a precise disambiguation together with an optimal model, penalizing models leading to unlikely disambiguations. For instance, if X × Y are the fuzzy data, we may define an optimal disambiguation x * , y * and model M * as

(x * , y * , M * ) = arg min x,y∈X×Y M∈M R emp (M) + λ (1 -µ X×Y (x, y))
where µ X×Y (x, y) is the membership value of the disambiguation (x, y) (obtained, e.g., through the extension principle) and where λ ≥ 0 is a parameter that determines how much choosing unlikely disambiguations is penalized. Provided µ X×Y is obtained by the extension principle, this would probably correspond to pick a suitable degree α (induced by the value of λ ) in the paper method, and then use the set-valued procedure on the α-cut to obtain the optimal model. The above idea could also be extended to more general uncertainty models, replacing µ with a corresponding uncertainty measure (i.e., plausibility measure, upper probability, . . . ).

Likelihood and loss

I think the comparison made with Denoeux's approach sheds a very interesting light on this latter approach, and shows one possible interpretation of it. However, beyond the interpretation in terms of loss functions, I think (but Eyke Hüllermeier or Thierry Denoeux may disagree on that) there is an essential philosophical difference between the two: that while Eyke Hüllermeier's approach includes a subjective decision component in its method through the loss function, Thierry Denoeux's approach tries to obtain what I would call an "objective" description of the data population.

Indeed, Thierry Denoeux's approach aims at estimating the parameters θ of a parametric distribution P θ describing the data, the distribution P θ not depending on a particular decision maker. Once this is done, any loss function can be plugged to the model P θ . On the contrary, Eyke Hüllermeier's approach will lead to an optimal predictive model that may change when the loss function is modified, hence may vary between decision makers. I think both views offer advantages and disadvantages. If one wants to separate the process of inference from the process of decision (because the loss function to be used is not yet known, or for other reasons [6, Sec. 1.5.]), then I would favor Denoeux's approach. If the loss function (or a good approximation of it) is available and one wants to provide (unique) optimal decisions, then I agree with Eyke Hüllermeier that his approach is likely to make the best out of the available information, and is more adapted in this case.

This is close to the maximal decision criterion[START_REF] Troffaes | Decision making under uncertainty using imprecise probabilities[END_REF] used in imprecise probability theory.


S Destercke

Comments on "A distance-based statistical analysis of fuzzy number-valued data" by the SMIRE research group

Keywords: fuzzy data, comments, statistic, ontic view

This paper is a fine review of various aspects related to the statistical handling of "ontic" random fuzzy sets by the means of appropriate distances. It is quite comprehensive and helpful, as it clarifies the status of fuzzy sets in such methods, explains the advantages of using a distance-based approach, specifies the pitfalls in which one should not fall when dealing with "ontic" random fuzzy sets and provides some illustration of practical computations. Not being a statistician but an occasional user of statistics, my discussion will mainly focus on this more practical aspect.

Introduction

First, I must thank Angela Blanco-Fernández, María Rosa Casals, Ana Colubi, Norberto Corral, Marta García-Bárzana, María Ángeles Gil, Gil González-Rodríguez, María Teresa López, María Asunción Lubiano, Manuel Montenegro, Ana Belén Ramos-Guajardo, Sara de la Rosa de Sáa and Beatriz Sinova (henceforth simply denominated "the SMIRE group") for this paper [START_REF] Blanco-Fernández | A distance-based statistical analysis of fuzzy number-valued data[END_REF], as it has helped me to better understand their approach and ideas.

The SMIRE group has now been working on the issue of statistical analysis of "ontic" fuzzy sets (i.e., fuzzy sets as objects of interest, and not as uncertainty models of a precise yet ill-known quantity) for a long time, and the tools they (among and with Email address: sebastien.destercke@hds.utc.fr (S. Destercke) others) develop have now reached a maturity that allows to perform the most standard (and therefore most useful) statistical analysis on fuzzy data.

From a practical standpoint, having such available tools is essential, and the research reported in this paper has allowed to make significant progress in this direction.

As a potential user of such tools, there is still some questions whose answer is not entirely clear to me, and that I will therefore discuss here. More precisely, these questions will address the following points:

• What is the advantages of using fuzzy sets as summaries of complex information

• The burden of using a quantitative model and metric

• Issues about interpretation of models and results

Fuzzy sets as complex information summary

It is my feeling that, in many case studies handling numerical fuzzy data, such fuzzy data are used as intermediate summaries of complex information (but not always, as for instance in the setting of graded multi-label [START_REF] Cheng | Graded multilabel classification: The ordinal case[END_REF], where fuzzy sets are natural descriptors of the information). For example, they can be used to summarize gradual transitions in an image, rather than using the complete pixel-wise information, or they can summarize the evolution of some variable (e.g., blood pressure [START_REF] Gil | Regression and correlation analyses of a linear relation between random intervals[END_REF]) during some period of time. In this sense, they provide more information than summaries consisting of single points (crisp edges, median or mean values, . . . ), but still provide a compact and perhaps more useful representation of the information than the complete, raw information.

However, as rightly recalled by the SMIRE group in their review, researchers have proposed over the years different ways to summarize such complex information, for instance by using functional data, by the means of histograms or through simple intervals, and have proposed adequate tools to analyze such summarized information. I think that, in most practical cases, one could model the complex information using any of these summaries and apply the corresponding techniques, with more or less difficulty. What I wonder is if there are peculiar types of situations or specific examples where using a fuzzy modeling of the information to summarize it is definitely preferable to the other alternatives, and the reasons that make it preferable?

The case where fuzzy data concerns a subjective source (observer) or a subjective concept (e.g., beauty, quality) is in my opinion quite different, as in this case it is not clear to me to which extent it is legitimate to transform such information into quantitative objects defined on a unique scale, and then draw conclusions from these objects.

For instance, in this case the assessment of a same observer over an identical object may change over time, resulting in two different quantitative fuzzy sets, whose "ontic" nature is then not obvious.

The burden of numbers

The techniques and approaches reviewed by the SMIRE group heavily rely on the definition of a proper metric (which induces, in some sense, an ordering over fuzzy sets) as well as on the availability of numerical fuzzy sets. While this is fine in a number of situations where obtaining or defining numerical aspects can be done in a satisfying way (I would say most situations involving physical measures, and probably others), I can perceive it as a possible limitation since:

• There are quite a number of statistical tools or notions (the median, rank-based correlation, non-parametric tests such as MannWhitneyWilcoxon) that only use a ranking or an ordering over elements, and that therefore only require a qualitative comparison between fuzzy sets. It is not clear to me if the techniques developed in the paper would apply well to such concepts (I know the SMIRE group has extended the concept of Median to their setting, for instance [START_REF] Sinova | The median of a random fuzzy number. the 1-norm distance approach[END_REF]), and to which extent it would be constraining with respect to a more qualitative view of ordering fuzzy sets;

• In the case of the description of subjective concepts such as beauty or quality, a qualitative notion seems to me more adapted (as suggested by my remark of the previous paragraph): while a numerical translation would, in my opinion, be dangerous to manipulate (since numbers would bear no "ontic" meaning), a more qualitative or ordinal approach would be able to model the information more faithfully (as the same observer will usually be consistent when comparing paintings, i.e., in saying that one painting is more beautiful than another). Note that, in practice, this could also be obtained by using a numerical inference technique whose conclusions only depend on the ordering of numbers (and not on their particular value), but I do not know if such a technique is available for fuzzy data. Although I agree that fuzzy numbers offer more flexibility (as suggested in Section 3 of the paper), the consequences (in terms of inferences, decision, . . . ) of manipulating numbers (even if they consist of membership values) as if they had a meaning of their own when they have not are still unclear to me.

It may be the case that the techniques presented in the paper are more adapted to numerical aspects of statistics, in which case building the fuzzy counterpart of qualitative techniques would be another area of research.

On the interpretation of inferences and models

One of the main reasons of using statistics is to give a meaning to the data and to communicate it to third-party users. While providing an intuitive interpretation is possible for most techniques of the paper (mean and variance of fuzzy random sets and their comparisons), some other defined statistical values seems to me much harder to interpret. For example:

• The joint covariance σ X ,Y is mathematically well-defined and has interesting properties, but its meaning is not clear to me. I understand how to interpret each of its parts Cov(midX α , midY α ) and Cov(sprX α , sprY α ), as they are covariances of single numbers, but not their combination into σ X ,Y . How should I interpret a low or a high value of σ X ,Y ? or should I just see it as a convenient mathematical tool without further meaning?

• Similar comments can be done on the linear model Y = aX + E , whose parameter estimation itself involves the use of σ X ,Y . For instance, it is not clear what is the meaning of a "fuzzy noise" E centered around the fuzzy value B?

Can we reduce the model to an expression where the noise is not fuzzy? Is the model equivalent to write Y = aX + B + E ′ with E ′ some noise with zeromean? Similarly, why considering a fuzzy intercept B but a crisp slope a? Again, I can understand that such definitions are mathematically attractive and lead to convenient and practical estimation formulas, however they do not necessarily facilitate the interpretation of the model.

It should be noted that the above remark does not mean that such an interpretation does not exist, merely that either more efforts need to be spent in explaining it (in laymen terms), or that the model has to be used as a black-box mapping from inputs to outputs (possibly used to perform predictions).