whether they are published or not. The documents may come

Shrinking and swelling clays under droughts: measurements at the Mormoiron test-site and first analyses (Vaucluse, South-East of France)

Sébastien Gourdier, Rosalie Vandromme, and Gilles Grandjean BRGM, DRP/RIG, Orléans Cedex 2, France (r.vandromme@brgm.fr)

In France, exceptional periods of rainfall deficit (1976, 1989 to 1991 and 1996 to 1997) have caused damages to houses due to their vulnerability to shrinking and swelling clays phenomenon. Between 1998 and 2010, BRGM has been producing a national hazard map related to shrinking and swelling clays, built by crossing geological data and information on density of damages for each geological formation (methodology developed since 1995).

The intense drought of summer 2003 has pointed out the necessity of a better understanding of this phenomenon. At the request of the French Ministry of Environment, BRGM has developed a new method for measuring the moisture evolution with depth in order to study its impact on the swelling capacity of clayed soil. The site of Mormoiron (Vaucluse, South-East of France) has then been instrumented for that purpose, with moisture sensors (since December 2004) and extensometers (since March 2009) at different depths. These data have been used to test and improve existing empirical models which are supposed to assess settlements and swellings, depending on the soil water content.

Compilations of different measurements have shown, after basic processing made on the data (filtering, resampling, etc.), evident correlations between rain and surface displacements. The model finally obtained gives quite good dependence between these two quantities for the uppermost soil layers (0.2m and 0.5m). More research are being undertaken to physically explain this relationship, particularly for deeper layers. These results should lead to propose a calibrated model for predicting soil deformations from climatic data.

  Shrinking and swelling clays under droughts: measurements at the Mormoiron test-site and first analyses (Vaucluse, South-East of France) Sébastien Gourdier, Rosalie Vandromme, Gilles Grandjean To cite this version: Sébastien Gourdier, Rosalie Vandromme, Gilles Grandjean. Shrinking and swelling clays under droughts: measurements at the Mormoiron test-site and first analyses (Vaucluse, South-East of France). EGU General assembly 2013, Apr 2013, Vienne, Austria. hal-00796895


Michael F Barnsley
email: michael.barnsley@maths.anu.edu.au

Nicolae Mihalache
email: nicolae.mihalache@u-pec.fr

SYMMETRIC ITINERARY SETS. 2011 Nicolae Mihalache Hal-

SYMMETRIC ITINERARY SETS

Keywords:

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

Let W 0 : [0, a] → [0, 1] and W 1 : [1-b, 1] → [0, 1] be continuous and differentiable, and such that a + b > 1, W 0 (0) = W 1 (1b) = 0, W 0 (a) = W 1 (1) = 1. Let the derivatives W ′ i (x) (i = 0, 1) be uniformly bounded below by d > 1.

For ρ ∈ [1 -b, a] we define W : [0, 1] → [0, 1] by [0, 1] ∋ x → W 0 (x) if x ∈ [0, ρ] W 1 (x) otherwise.
See Figure 1. Similarly, we define W + : [0, 1] → [0, 1] by replacing [0, ρ] by [0, ρ).

Let I = {0, 1}. Let I ∞ = {0, 1} × {0, 1} × • • • have the product topology induced from the discrete topology on I. For σ ∈ I ∞ write σ = σ 0 σ 1 σ 2 . . . , where σ k ∈ I for all k ∈ N. The product topology on I ∞ is the same as the topology induced by the metric d(ω, σ) = 2 -k where k is the least index such that ω k = σ k . It is well known that (I ∞ , d) is a compact metric space. We define a total order relation on I ∞ , and on I n for any n ∈ N, by σ ≺ ω if σ = ω and σ k < ω k where k is the least index such that σ k = ω k . For σ ∈ I ∞ and n ∈ N we write σ| n = σ 0 σ 1 σ 2 ...σ n . I ∞ is the appropriate space in which to embed and study the itineraries of the family of discontinuous dynamical systems W : [0, 1] → [0, 1].

For W (+) ∈ {W, W + } let W k (+) denote W (+) composed with itself k times, for k ∈ N, and let W -k (+) = (W k (+) ) -1 . We define a map τ : [0, 1] → I ∞ , using all of the orbits of W, by τ (x) = σ 0 σ 1 σ 2 . . .

where σ k equals 0, or 1, according as W k (x) ∈ [0, ρ], or (ρ, 1], respectively. We call τ (x) the itinerary of x under W , or an address of x, and we call Ω = τ ([0, 1]) an address space for [0, 1]. Similarly, we define τ + : [0, 1] → I ∞ so that τ + (x) k equals 0, or 1, according as W k + (x) ∈ [0, ρ), or [ρ, 1], respectively; and we define Ω + = τ + ([0, 1]). Note that W , W + , Ω, Ω + , τ , and τ + all depend on ρ.

The main goals of this paper are to characterise Ω and to show that there exists a value of ρ such that Ω is symmetric. We write E to denote the closure of a set E. But we write 0 = 000..., 1 = 111...

∈ I ∞ . For σ = σ 0 σ 1 σ 2 . . . ∈ I ∞ we write 0σ to mean 0σ 0 σ 1 σ 2 . . . ∈ I ∞ and 1σ = 0σ 0 σ 1 σ 2 . . . ∈ I ∞ .
Define a symmetry function * :

I ∞ → I ∞ by σ * = ω where ω k = 1 -σ k for all k. Theorem 2. There exists a unique ρ ∈ [1 -b, a] such that Ω * = Ω.
Theorem 1 tells us that Ω is fixed by itineraries of two inverse images of the critical point ρ, and provides the basis for a stable algorithm to determine Ω. It relates the address spaces of dynamical systems of the form of W to the beautiful theory of iterated closed relations on compact Hausdorff spaces [START_REF] Mcgehee | Conley decomposition for closed relations[END_REF], and hence to the work of Charles Conley.

Theorem 2 is interesting in its own right and also because it has applications in digital imaging, as explained and demonstrated, in the special case of affine maps, in [START_REF] Barnsley | How to filter and transform images using iterated function systems[END_REF]. It enables the construction of parameterized families of nondifferentiable homeomorphisms on [0, 1], using pairs of overlapping iterated function systems, see Proposition 4. Theorem 2 generalizes results in [START_REF] Barnsley | How to filter and transform images using iterated function systems[END_REF] to nonlinear W i 's. The proof uses symbolic dynamics in place of the geometrical construction outlined in [START_REF] Barnsley | How to filter and transform images using iterated function systems[END_REF]. The approach and results open up the mathematics underlying [START_REF] Barnsley | How to filter and transform images using iterated function systems[END_REF] and [START_REF] Igudesman | A certain family of self-similar sets[END_REF].

To tie the present work into [START_REF] Barnsley | How to filter and transform images using iterated function systems[END_REF], note that τ is a section, as defined in [START_REF] Barnsley | How to filter and transform images using iterated function systems[END_REF], for the hyperbolic iterated function system

F := ([0, 1]; W -1 0 , W -1 1
). Our observations interrelate to, but are more specialized than, the work of Parry [START_REF] Parry | Symbolic dynamics and transformations of the unit interval[END_REF]. Our point of view is topological rather than measure-theoretic, and our main results appear to be new.

Basic properties of τ

The following list of properties is relatively easy to check. Below the list we elaborate on points 1, 2, and 3.

(1) W n is piecewise differentiable and its derivative is uniformly bounded below by d n ; each, except the leftmost branch of W n , is defined on an interval of the form (r, s]. W n + is piecewise differentiable and its derivative is uniformly bounded below by d n ; each, except for the rightmost branch of W n + , is defined on an interval of the form [r, s).

5) τ (x) = τ + (x) unless x ∈ k∈N W -k (ρ) in which case τ (x) ≺ τ + (x).
(6) Both τ (x) and τ + (x) are strictly increasing functions of x ∈ [0, 1] and τ (x) τ + (x). This follows from (4) and ( 5). (7) For all x ∈ [0, 1], τ (x) is continuous from the left, τ + (x) is continuous from the right. Moreover, for all x ∈ (0, 1),

τ (x) = lim ε→0 + τ + (x -ε) and τ + (x) = lim ε→0 + τ (x + ε).
These assertions follow from (2), ( 3) and ( 4). (8) Each x ∈ W -n (ρ), such that τ (x)| n is constant, moves continuously with respect to ρ with positive velocity bounded above by d -n . This follows from (1).

(9) For x ∈ (0, 1)\

n k=0 W -k (ρ), τ (x)| n = τ + (x)
| n is locally constant with respect to ρ; moreover, this holds if x depends continuously on ρ. This follows from (2), (3) and ( 6). (10) The symmetry function * : I ∞ → I ∞ is strictly decreasing and continuous. (11) For any σ| n ∈ I n , n ∈ N, the set

I(σ| n ) := {x ∈ [0, 1] : τ (x)| n = σ| n or τ + (x)| n = σ| n },
is either empty or a non-degenerate compact interval of length at most d -n . This follows from (2), ( 3) and ( 6). (12) The projection π :

I ∞ → [0, 1] is well-defined by π(σ) = sup{x ∈ [0, 1] : τ + (x) σ} = inf{x ∈ [0, 1] : τ (x) σ}.
This follows from (6). (13) The projection π : I ∞ → [0, 1] is increasing, by (6); continuous, by (11); and, by (7),

π(τ (x)) = π(τ + (x)) = x for all x ∈ [0, 1], τ (π(σ)) σ τ + (π(σ)) for all σ ∈ I ∞ . (14) Let S : I ∞ → I ∞ denote the left-shift map σ 0 σ 1 σ 2 ... → σ 1 σ 2 σ 3 .... For all σ ∈ I ∞ such that σ τ (ρ) or σ ≥ τ + (ρ), π(S(σ)) = W (π(σ)).
Also π(τ + (ρ)) = ρ and π(S(τ + (ρ))) = W 1 (ρ). These statements follow from ( 7).

Here we elaborate on points (1), ( 2) and ( 3). Consider the piecewise continuous function W k (x), for k ∈ {1, 2, ...}. Its discontinuities are at ρ and, for k > 1, other points in (0, 1), each of which can be written in the form

W -1 σ0 • W -1 σ2 • ...W -1 σ l-1 (ρ) for some σ 0 σ 1 ...σ l-1 ∈ {0, 1} l for some l ∈ {1, 2, ...k -1}.
We denote these discontinuities, together with the points 0 and 1, by

D k,0 := 0 < D k,1 < D k,2 < .... < D k,D(k)-1 < 1 =: D k,D(k) , where D(1) = 3, D(2) = 5 < D(3) < D(4)... . For each k ≥ 1, one of the D k,j 's is equal to ρ. For k ≥ 1 we have W k (x) = W k 0 (x) for x ∈ [D k,0 , D k,1 ] and W k + (x) = W k 0 (x) for x ∈ [D k,0 , D k,1 ). Similarly W k (x) = W k 1 (x) for all x ∈ (D k,D(k)-1 , D k,D(k) ] and W k + (x) = W k 1 (x) for x ∈ [D D(k)-1 , D D(k) ]. For all x ∈ (D k,l , D k,l+1 ) (l = 0, 1, ..., D(k)-1), W k (x) = W k + (x) = W θ k •W θ k-1 • ...W θ1 (x) for some fixed θ 1 θ 2 ...θ k ∈ {0, 1} k . We refer to θ 1 θ 2 ...θ k as the address of the interval (D k,l , D k,l+1 ), we say (D k,l , D k,l+1
) that "has address θ 1 θ 2 ...θ k ", and we write, by slight abuse of notation, τ

((D k,l , D k,l+1 )) = θ 1 θ 2 ...θ k . Let k > 1. Consider two adjacent intervals,(D k,m-1 , D k,m ] and (D k,m , D k,m+1 ] for m ∈ {1, 2, ..., D(k) -1} and k > 1.
Let the one on the right have address θ 0 θ 1 ...θ k-1 and the one on the left have address In this section we characterize Ω and Ω + as certain inverse limits, and we characterize Ω as an attractor of an iterated closed relation on I ∞ . These inverse limits are natural and they clarify the structures of Ω and Ω + . They are implied by the shift invariance of Ω and Ω + . Recall that S :

η 0 η 1 ... η k-1 . Then η 0 η 1 ... η k-1 ≺ θ 0 θ 1 ...θ k-1 and we have τ (x)| k-1 = η 0 η 1 ...η k-1 for all x ∈ (D k,m-1 , D k,m ], τ + (x)| k-1 = η 0 η 1 ...η k-1 for all x ∈ [D k,m-1 , D k,m ), τ (x)| k-1 = θ 0 θ 1 ...θ k-1 for all x ∈ (D k,m , D k,m+1 ], τ + (x)| k-1 = θ 0 θ 1 ...θ k-1 for all x ∈ [D k,m , D k,m+1 ).
I ∞ → I ∞ denotes the left-shift map σ 0 σ 1 σ 2 ... → σ 1 σ 2 σ 3 .... Proposition 1. (i) τ (W (x)) = S(τ (x)) and τ + (W + (x)) = S(τ + (x)) for all x ∈ [0, 1].
(ii) S(Ω) = Ω and S(Ω + ) = Ω + .

Proof. (i) This follows at once from the definitions of τ and τ + . (ii) This follows from (i) together with

W ([0, 1]) = W + ([0, 1]) = [0, 1].
We say that Λ ⊂ I ∞ is closed from the left if, whenever {x n } ∞ n=0 is an nondecreasing sequence of points in Λ, lim x n ∈ Λ. We say that Λ ⊂ I ∞ is closed from the right if, whenever {x n } ∞ n=0 is non-increasing sequence in Λ, lim x n ∈ Λ. For S ⊂ X, where X = I ∞ or [0, 1], we write L(S) = {σ ∈ X : there is a non-decreasing sequence {z n } ∞ n=0 ⊂ S with σ = lim z n } to denote the closure of S from the left. Analogously, we define R(S) for the closure of S from the right. Proposition 2. (i) Ω is closed from the left and Ω + is closed from the right;

(ii) . Also, by [START_REF] Parry | Symbolic dynamics and transformations of the unit interval[END_REF],

Ω = Ω + = Ω ∪ Ω + = Ω ∩ Ω + Proof. Proof of (i): By (6) τ : [0, 1] → I ∞ is
Ω ∩ Ω + = τ ([0, 1]) ∩ τ + ([0, 1]) = τ (Q) = τ + (Q). Hence Ω ∩ Ω + = τ (Q) = τ + (Q) = Ω = Ω + . Finally, Ω ∪ Ω + = L(τ (Q)) ∪ R(τ + (Q)) = L(τ (Q)) ∪ R(τ (Q)) = τ (Q) = Ω.
We define s i : I ∞ → I ∞ by s i (σ) = iσ (i = 0, 1). Note that both s 0 , and s 1 , are contractions with contractivity 1/2. We write 2 I ∞ to denote the set of all subsets of I ∞ . For σ, ω ∈ I ∞ we define

[σ, ω] := {ζ ∈ I ∞ : σ ζ ω}, (σ, ω) := {ζ ∈ I ∞ : σ ≺ ζ ≺ ω}, (σ, ω] := {ζ ∈ I ∞ : σ ≺ ζ ω}, [σ, ω) := {ζ ∈ I ∞ : σ ζ ≺ ω}. Proposition 3. Let α = S(τ (ρ)) and β = S(τ + (ρ)). (i) Ω = k∈N Ψ k ([0, 1]) where Ψ : 2 I ∞ → 2 I ∞ is defined by 2 I ∞ ∋ Λ → s 0 (Λ ∩ [0, α]) ∪ s 1 (Λ ∩ (β, 1]). (ii) Ω + = k∈N Ψ k + ([0, 1]) where Ψ + : 2 I ∞ → 2 I ∞ is defined by 2 I ∞ ∋ Λ → s 0 (Λ ∩ [0, α)) ∪ s 1 (Λ ∩ [β, 1]). (iii) Ω = Ω + = k∈N Ψ k ([0, 1]) where Ψ : 2 I ∞ → 2 I ∞ is defined by 2 I ∞ ∋ Λ → s 0 (Λ ∩ [0, α]) ∪ s 1 (Λ ∩ [β, 1]).
Proof. Proof of (i): Let S| Ω : Ω → Ω denote the domain and range restricted shift map. It is readily found that the branches of S| -1

Ω : Ω → Ω are s 0 | Ω : [0, α] ∩ Ω → Ω where s 0 | Ω (σ) = s 0 (σ) = 0σ for all σ ∈ [0, α] ∩ Ω, and s 1 | Ω : (β, 1] ∩ Ω → Ω where s 1 | Ω (σ) = s 1 (σ) = 1σ for all σ ∈ (β, 1] ∩ Ω.
(Note that α 0 = 1, β 0 = 0 and β ≺ α.) It follows that

S| -1 Ω (Λ) = s 0 (Λ ∩ [0, α]) ∪ s 1 (Λ ∩ (β, 1]) = Ψ(Λ) for all Λ ⊂ Ω. Since Ω ⊂ [0, 1] it follows that Ω = S| -1 Ω (Ω) = Ψ(Ω) ⊂ Ψ([0, 1]). Also, since Ψ([0, 1]) ⊂ [0, 1] it follows that {Ψ k ([0, 1])} is a decreasing (nested) sequence of sets, each of which contains Ω; hence Ω ⊂ k∈N Ψ k ([0, 1]).
It remains to prove that Ω ⊃ k∈N Ψ k ([0, 1]). We note that s 0 ([0, α]) = [0, τ (ρ)] and s 1 ((β, 1]) = (τ + (ρ), 1], from which it follows that

(3.1) k∈N Ψ k ([0, 1]) = k∈N {σ ∈ I ∞ : S k (σ) ∈ [0, τ (ρ)] ∪ (τ + (ρ), 1]}. Let ω ∈ k∈N Ψ k ([0, 1]). Suppose ω / ∈ Ω. Let ω -= sup{σ ∈ Ω : σ ω} and ω + = inf{σ ∈ Ω : ω σ}, so that ω -ω ω + . But ω -∈ Ω (since Ω is closed from the left), so ω -≺ ω ω + .
Note that, since inf{σ ∈ Ω : ω σ} = inf{σ ∈ Ω + : ω σ}, and Ω + is closed from the right, we have

ω + ∈ Ω + . Let K = min{k ∈ N : (ω -) k = (ω + ) k }. Then S K (ω -) ≺ S K (ω)
S K (ω + ) and we must have S K (ω -) = τ (ρ) and S K (ω

+ ) = τ + (ρ). So τ (ρ) ≺ S K (ω) τ + (ρ), therefore ω / ∈ {σ ∈ I ∞ : S K (σ) ∈ [0, τ (ρ)] ∪ (τ + (ρ), 1]
} which, because of (3.1), contradicts our assumption that ω ∈ k∈N Ψ k ([0, 1]). Hence ω ∈ Ω and we have

Ω ⊃ k∈N Ψ k ([0, 1]).
This completes the proof of (i). Proof of (ii): similar to the proof of (i), with the role of [0, τ (ρ)] played by [0, τ (ρ)) and the role of (τ + (ρ), 1] played by [τ + (ρ), 1].

Proof of (iii): similar to the proofs of (i) and (ii).

It is helpful to note that the addresses α and β in Proposition 3 obey

α = τ (W 0 (ρ)), β = τ (W 1 (ρ)), τ (ρ) = 0α = 01α 1 α 2 ... and τ + (ρ) = 0β = 10β 1 β 2 .... Let M > 0 be such that D k,M +1 = ρ. It follows from the discussion at the end of Section 2 that τ ((D k,M , ρ)) = τ + ((D k,M , ρ)) = 01α 1 α 2 ..α k-2 and τ ((ρ, D k,M +2 )) = τ + ((ρ, D k,M +2 )) = 10β 1 β 2 ...β k-2 . Corollary 1. Let k ≥ 1, α = τ (W 0 (ρ)), β = τ (W 1 (ρ))
, and let M > 0 be such that D k,M +1 = ρ. The set of addresses {τ

((D k,l , D k,l+1 ))} D(k)-1 l=0
is uniquely determined by α| k-1 and β| k-1 . For some n 1 , n 2 such that 0

≤ n 1 < M < n 2 ≤ D(k) -1, τ ((D k,n1 , D k,n1+1 )) = β 0 β 1 ...β k-2 β k-1 and τ ((D k,n2 , D k,n2+1 )) = α 0 α 1 ...α k-2 α k-1 . The set of addresses {τ ((D k,l , D k,l+1 )) : l ∈ {0, 1, ..., D(k) - 1}, l = n 1 , l = n} are uniquely determined by α| k-2 and β| k-2 ; for example, τ ((D k,M , ρ)) = 0α 0 α 1 ...α k-2 , and τ ((ρ, D k,M +2 )) = 1β 0 β 1 ...β k-2 .
Proof. It follows from Proposition 3 that the set of addresses at level k, namely {τ

((D k,l , D k,l+1 ))} D(k)-1 l=0
, is invariant under the following operation: put a "0" in front of each address that is less than or equal to α, then truncate back to length k; take the union of the resulting set of addresses with the set of addresses obtained by: put a "1" in front of each address that is greater than or equal to β, and drop the last digit.

Symmetry of Ω and a consequent homeomorphism of [0, 1]

Lemma 1. Ω = {σ ∈ I ∞ : for all k ∈ N, σ k = 0 ⇒ S k (σ) τ (ρ) and σ 0 = 1 ⇒ τ + (ρ) S k (σ)}.
Proof. This is an immediate consequence of Proposition 3.

Corollary 2. Ω is symmetric if and only if

α = β * (or equivalently τ (ρ) = (τ + (ρ)) * ).
Lemma 2. The maps τ (ρ) and τ + (ρ) are strictly increasing as functions of ρ ∈

[a, b] to I ∞ .
Proof. Note that τ (ρ) depends both implicitly and explicitly on

ρ. Let 1 -b ≤ ρ < ρ ′ ≤ a be such that τ (ρ) τ (ρ ′ ). Observe that τ (ρ)| 0 = τ (ρ ′ )| 0 . Assume first that there is a largest n > 0 such that τ (ρ)| n = τ (ρ ′ )| n := θ 0 θ 1 ...θ n . Then τ (ρ) = θ 0 θ 1 ...θ n 1... and τ + (ρ) = θ 0 θ 1 ...θ n 0..., which implies (4.1)
W n ρ (ρ) ≥ ρ and W n ρ ′ (ρ ′ ) ≤ ρ ′ . (We write W = W ρ when we want to note the dependence on ρ. ) We may assume that τ (ρ)| n is constant on [ρ, ρ ′ ] for otherwise we can restrict to a smaller interval with a strictly smaller value of n. As a consequence, at every iteration, we apply the same branch W 0 or W 1 to W ξ to compute compute g(ξ) := W n ξ (ξ) for all ξ ∈ [ρ, ρ ′ ]. Therefore g is continuous with derivative at least d n > 1, which contradicts (4.1).

The only remaining possibility is that τ (ρ) = τ (ρ ′ ). We may assume that τ (ρ) is constant on [ρ, ρ ′ ], otherwise we can reduce the problem to the previous case. This would mean that for arbitrarily large n, the image of the interval [ρ, ρ ′ ] under g is at an interval of size least d n (ρ ′ρ), a contradiction.

Essentially the same argument, with the role of τ played by τ + and the role of played by W + , proves that τ + (ρ) is strictly increasing as a function of ρ ∈ [1b, a] to I ∞ . Corollary 3. The map ρ → τ (ρ) is left continuous and the map ρ → τ + (ρ) is right continuous.

Proof. Fix a parameter ρ 0 and let ε > 0. Then by (7) there is x < ρ 0 which is not a preimage of ρ 0 for any order and such that

d(τ + ρ0 (x), τ ρ0 (ρ 0 )) < ε 2 .
By (9), for any n ∈ N there exists δ > 0 such that the prefix τ + ρ (x)| n is constant when ρ ∈ (ρ 0δ, ρ 0 + δ). Let n be such that 2 -n < ε, and let ρ > x and ρ ∈ (ρ 0δ, ρ 0 ). We have that τ + ρ (x) ≺ τ + ρ (ρ) and

d(τ + ρ (x), τ + ρ0 (x)) < ε 2 .
Combining the two inequalities we obtain d(τ + ρ (x), τ ρ0 (ρ 0 )) < ε, and by Lemma 2 we also have

τ + ρ (x) ≺ τ ρ (ρ) ≺ τ ρ0 (ρ 0 ). The distance d has the property that if σ ≺ ζ ≺ σ ′ then d(σ, ζ) ≤ d(σ, σ ′ ) and d(ζ, σ ′ ) ≤ d(σ, σ ′ )
. This shows that ρ → τ (ρ) is left continuous. The right continuity of ρ → τ + (ρ) admits an analagous proof.

As a consequence of Corollary 2, Lemma 2 and (10), we obtain the unicity of ρ for which Ω is symmetric.As a consequence of Corollary 2, Lemma 2 and (10), we obtain the unicity of ρ for which Ω is symmetric.

Corollary 4. There is at most one ρ ∈ [1 -b, a] such that Ω = Ω * .
Proof of Theorem 2. By Lemma 2 and (10), we may define

ρ 0 := sup{ρ ∈ [1 -b, a] : τ (ρ) τ + (ρ) * } = inf{ρ ∈ [1 -b, a] : τ (ρ) * τ + (ρ)}. Assume τ (ρ 0 ) ≺ τ + (ρ 0 ) * . It is straighfoward to check 1 -b < ρ 0 < a. There is a largest n ≥ 2 such that τ (ρ 0 )| n = τ + (ρ 0 ) * | n =: η = 01... . Observe that τ (ρ 0 ) = 0τ (W 0 (ρ 0 )) and τ + (ρ 0 ) = 1τ + (W 1 (ρ 0 )). If neither W 0 (ρ 0 ) nor W 1 (ρ 0 ) belongs to {0, 1}∪ n-1 k=0 W -k (ρ 0 ), then by (9) both τ (ρ)| n+1 and τ + (ρ)| n+1
are constant on a neighborhood of ρ 0 which contradicts the definition of ρ 0 . Let us consider the projection π(τ + (W 1 (ρ 0 )) * ). If π(τ + (W 1 (ρ 0 )) * ) > W 0 (ρ 0 ) then by the continuity of W 0 , of π by (13), of ρ → τ + ρ (ρ) (Corollary 3) there is a ρ > ρ 0 such that πρ (τ + ρ (W 1 (ρ 0 )) * ) > W 0 (ρ). By (6) and (13) this implies τ ρ (ρ) ≺ τ + ρ (ρ) * , which again contradicts the definition of ρ 0 .

As π is increasing, (13) and τ (W 0 (ρ 0 )) ≺ τ + (W 1 (ρ 0 )) * , we have π(τ + (W 1 (ρ 0 )) * ) = W 0 (ρ 0 ). Let 0 < m < n be minimal such that W m •W 0 ( ρ 0 ) = ρ 0 or W m •W 1 (ρ 0 ) = ρ 0 . We may apply (14) m times and obtain

(4.2) W m • W 0 (ρ 0 ) = π(S m (τ + (W 1 (ρ 0 )) * )) = π(τ + (W m • W 1 (ρ 0 )) * ). As τ + (ρ 0 ) = 1..., if W m • W 1 (ρ 0 ) = ρ 0 then we have τ (ρ 0 ) ≺ τ + (ρ 0 ) * = τ + (W m • W 1 (ρ 0 )) * ≺ τ + (ρ 0 ),
which by (6) and equation (4.2) implies W m • W 0 (ρ 0 ) = ρ 0 . Therefore τ (ρ 0 ) = τ + (ρ 0 ) * as both are periodic of period m + 1 and have the same prefix of length n > m, a contradiction. 13), (10) and equality (4.2) we obtain 6) and the previous inequality. By induction we get κ * ∞ ≺ σ ′ so

If W m • W 1 (ρ 0 ) = ρ 0 then W m • W 0 (ρ 0 ) = ρ 0 thus by (
τ (ρ 0 ) ≺ τ + (ρ 0 ) * τ + (W m • W 1 (ρ 0 )) := σ ′ . By (6), this means that ρ 0 ≤ W m • W 1 (ρ 0 ) so in fact ρ 0 < W m • W 1 (ρ 0 ). As W m+1 (ρ 0 ) = ρ 0 , τ (ρ 0 ) = κκκ... := κ ∞ where κ = τ (ρ 0 )| m+1 = τ + (ρ 0 ) * | m+1 , as m + 1 ≤ n. We can write τ + (ρ 0 ) = κ * σ ′ therefore κ * σ ′ ≺ σ ′ by (
τ + (ρ 0 ) * = κ(σ ′ * ) ≺ κ ∞ = τ (ρ 0 ), a contradiction.
The case τ (ρ 0 ) ≻ τ + (ρ 0 ) * is analagous by the symmetric definition of ρ 0 , therefore Ω ρ0 is symmetric. For X a compact Hausdorff space, let 2 X be the subsets of X. A relation r on X is simply a subset of X × X. A relation r on X is called a closed relation if r is a closed of X × X. For example the set r ⊂ I ∞ × I ∞ defined in Theorem 1, namely

r = {(0σ, σ) ∈ I ∞ × I ∞ : σ α} ∪ {(1σ, σ) ∈ I ∞ × I ∞ : β σ},
is a closed relation. Following [START_REF] Mcgehee | Conley decomposition for closed relations[END_REF], a relation r ∈ 2 X provides a mapping r : 2 X → 2 X defined by r(C) = {y ∈ X : (x, y) ∈ r for some x ∈ C}.

Notice that the image of a nonempty set may be empty. Iterated relations are defined by r 0 = X × X and, for all k ∈ N,

r k+1 = r • r k = {(x, z) : (x, y) ∈ r, (y, z) ∈ r k for some y ∈ X}. The omega limit set of C ⊂ X under a closed relation r ⊂ X × X is ω(C) = ∩K(C)
where

K(C) = {D is a closed subset of X : r(D) ∪ r n (C) ⊂ D for some n ∈ N}.
By definition, an attractor of a closed relation r is a closed set A such that the following two conditions hold:

(i) r(A) = A; (ii) there is a closed neighborhood N (A) of A such that ω(C) ⊂ A for all C ⊂ N (A).
The basin B(A) of an attractor A for a closed relation r on a compact Hausdorff space X is the union of all open sets O ⊂ X such that ω(C) ⊂ A for all C ⊂ O.

Given an attractor A for a closed relation r on a compact Hausdorff space X, there exists a corresponding attractor block, namely a closed set E ⊂ X such that E contains both A and r(E) in its interior, and A = ω(E). Also, there exists a unique dual repeller A * = X\B(A). This repeller is an attractor for the transpose relation r * = {(y, x) : (x, y) ∈ r}. The set of connecting orbits associated with the attractor/repeller pair A, A * is C(A) = X\(A ∪ A * ).

If r is a closed relation on a compact Hausdorff space X, then x ∈ X is called chain-recurrent for r if for every closed neighborhood f of r, x is periodic for f (i.e. there exists a finite sequence of points {x n } p-1 n=0 ⊂ X such that x 0 = x, (x p-1 , x 0 ) ∈ f and (x n-1 , x n ) ∈ f for n = 1, 2, ..., p -1). The chain recurrent set R for r is the union of all the points that are chain recurrent for r. A transitive component of R is a member of the equivalence class on R defined by x ∼ y when for every closed neighborhood f of r there is an orbit from x to y under f (i.e. there exists a finite sequence of points {x n } p-1 n=0 ⊂ R such that x 0 = x, x p-1 = y, and (x n , x n+1 ) ∈ f for all n ∈ {0, 1, ...p -1}.) where R is the chain-recurrent set and U is the set of attractors.

Proof of Theorem 1. This follows at once from Proposition 3 together with Theorem 3, but see [START_REF] Mcgehee | Conley decomposition for closed relations[END_REF].

We note the following. Ω can be embedded in [0, 1] ⊂ R using the (continuous and surjective) coding map π : I ∞ → [0, 1] associated with the iterated function system ([0, 1]; x → x/2, x → (1 + x)/2). This coding map π is defined, for all σ, by π(σ) =

Figure 1 .Theorem 1 .

 11 Figure 1. The piecewise continuous dynamical system W:[0,1]→[0,1] is defined in terms of two monotone strictly increasing differentiable functions W 0 (x) and W 1 (x), and a real parameter ρ. Theorem 1. Let an iterated closed relation r ⊂ I ∞ × I ∞ be defined by r := {(σ, 0σ) ∈ I ∞ × I ∞ : σ α} ∪ {(σ, 1σ) ∈ I ∞ × I ∞ : σ β} where α = τ (W 0 (ρ)) and β = τ + (W 1 (ρ)). The only attractors of r are {0}, {1}, {0, 1}, and Ω. The corresponding dual repellers are {σ ∈ I ∞ : β σ}, {σ ∈ I ∞ : σ α}, {σ ∈ I ∞ : β σ} ∪ {σ ∈ I ∞ : σ α}, and the empty set, respectively. The chain recurrent set for r is {0, 1} ∪ {σ ∈ Ω : β σ α}.

( 2 ) 1 k=0W

 21 If (r, s) is the interior of the definition domain of a branch of W n (and of W n + ) then τ (x)| n is constant on (r, s], τ + (x)| n is constant on [r, s), and τ (x)| n = τ + (x)| n for all x ∈ (r, s). (3) The boundary of the definition domain of a branch of W n is contained in {0, 1} ∪ n--k (ρ); by (1), the length of such a domain is at most d -n . (4) The set k∈N W -k (ρ) is dense in [0, 1]. This follows from (3).

(

. 3 .

 3 In particular, τ (x)| k-1 and τ + (x)| k-1 are constant and equal on each of the open intervals (D k,m-1 , D k,m ) and have distinct values at the discontinuity points {D k,m } D(k)-1 m=1 The structures of Ω, Ω + and Ω.

  monotone strictly increasing. By (7) τ is continuous from the left. Let {z n } ∞ n=0 be a non-decreasing sequence of points in Ω. Let y n = τ -1 (z n ). Let y = lim y n ∈ [0, 1]. Since τ is continuous from the left, Ω ∋ τ (y) = τ (lim y n ) = lim τ (y n ) = lim z n . It follows that Ω is closed from the left. Similarly, Ω + is closed from the right. Proof of (ii): Let Q = {x ∈ [0, 1] : τ (x) = τ + (x)}. Then by (4) Q = [0, 1]

Proposition 4 . 5 .

 45 If Ω = Ω * then the map h : [0, 1] → [0, 1] defined by h(x) = π(τ (x) * ) is a homeomorphism and h • π = π• * on I ∞ .Proof. First by Corollary 2, we have τ (ρ) = τ + (ρ) * and points x for which τ (x) = τ + (x) are exactly preimages of ρ. In this case, there is n ≥ 0 such that τ (x) and τ + (x) have the same initial prefix κ := τ (x)| n = τ + (x)| n , and τ (x) = κτ (ρ), τ + (x) = κτ + (ρ). Therefore, by (13), for all x ∈ [0, 1], we haveτ (h(x)) = τ + (x) * and τ + (h(x)) = τ (x) * , thus h • h(x) = x. By (6), (10) and (13), h is also decreasing. Therefore h :[0, 1] → [0, 1] is a homeomorphism.Let σ ∈ I ∞ and x = π(σ). By (13) we have τ (x) σ τ + (x). As Ω = Ω * , by Proposition 2, we obtain that there exists y ∈ [0, 1] such that τ (x) * = τ + (y). By Lemma 1 and Corollary 2 we also have that τ + (x) * = τ (y). We may computeh • π(σ) = h(x) = π(τ (x) * ) = π(τ (y)) = y,which is also equal to π(σ * ) as τ (y) σ * τ + (y). Iterated Closed Relations and Conley Decomposition for Itineraries of W Theorem 1 follows from Proposition 3, but some extra language is needed. In explaining this language we describe the Conley-McGehee-Wiandt decomposition theorem, [3, Theorem 13.1].

Theorem 3 (

 3 Conley-McGehee-Wiandt). If r is a closed relation on a compact Hausdorff space X, then R = A∈U C(A)

k∈N σ k 2

 2 k+1 . π provides a homeomorphism between Ω and π(Ω). The point σ ∈ Ω is uniquely and unambiguously represented by the binary real number 0.σ. In the representation provided by π, the map Ψ : 2I ∞ → 2 I ∞ becomes the action of the iterated closed relation r ⊂ [0, 1] × [0, 1] ⊂ R 2 defined by r := {(x, x/2) : x ∈ [0, π(α)]} ∪ {(x, (x + 1)/2) : x ∈ [π(β), 1]} on subsets of [0, 1]. It follows from Proposition 3 (iii) that π(Ω) is the maximal attractor, as defined in[START_REF] Mcgehee | Conley decomposition for closed relations[END_REF], of r. The corresponding dual repeller is the empty set. It is also easy to see that {0} and {1} are the only other attractors, with corresponding dual repellers [π(α), 1] and [0, π(β)] respectively. It follows from Theorem 3 that the chain recurrent set of r is {0, 1} ∪ (π(Ω) ∩ (π(β), π(α))).

Acknowledgement 1. We thank Konstantin Igudesman for helpful comments.


Rémi Lajugie
email: remi.lajugie@ens.fr

Sylvain Arlot
email: sylvain.arlot@ens.fr

Francis Bach
email: francis.bach@ens.fr

Large-Margin Metric Learning for Partitioning Problems

In this paper, we consider unsupervised partitioning problems, such as clustering, image segmentation, video segmentation and other change-point detection problems. We focus on partitioning problems based explicitly or implicitly on the minimization of Euclidean distortions, which include mean-based change-point detection, K-means, spectral clustering and normalized cuts. Our main goal is to learn a Mahalanobis metric for these unsupervised problems, leading to feature weighting and/or selection. This is done in a supervised way by assuming the availability of several potentially partially labelled datasets that share the same metric. We cast the metric learning problem as a large-margin structured prediction problem, with proper definition of regularizers and losses, leading to a convex optimization problem which can be solved efficiently with iterative techniques. We provide experiments where we show how learning the metric may significantly improve the partitioning performance in synthetic examples, bioinformatics, video segmentation and image segmentation problems.

Introduction

Unsupervised partitioning problems are ubiquitous in machine learning and other dataoriented fields such as computer vision, bioinformatics or signal processing. They include (a) traditional unsupervised clustering problems, with the classical K-means algorithm, hierarchical linkage methods [START_REF] Gower | Minimum spanning trees and single linkage cluster analysis[END_REF] and spectral clustering [START_REF] Ng | On spectral clustering: Analysis and an algorithm[END_REF], (b) unsupervised image segmentation problems where two neighboring pixels are encouraged to be in the same cluster, with mean-shift techniques [START_REF] Cheng | Mean shift, mode seeking, and clustering[END_REF] or normalized cuts [START_REF] Shi | Normalized cuts and image segmentation[END_REF], and (c) change-point detection problems adapted to multivariate sequences (such as video) where segments are composed of contiguous elements, with typical windowbased algorithms [START_REF] Desobry | An online kernel change detection algorithm[END_REF] and various methods looking for a change in the mean of the features (see, e.g., [START_REF] Chen | Parametric Statistical Change Point Analysis[END_REF]).

All the algorithms mentioned above rely on a specific distance (or more generally a similarity measure) on the space of configurations. A good metric is crucial to the performance of these partitioning algorithms and its choice is heavily problem-dependent. While the choice of such a metric has been originally tackled manually (often by trial and error), recent work has considered learning such metric directly from data. Without any supervision, the problem is ill-posed and methods based on generative models may learn a metric or reduce dimensionality (see, e.g., [START_REF] De La Torre | Discriminative cluster analysis[END_REF]), but typically with no guarantees that they lead to better partitions. In this paper, we follow [START_REF] Bar-Hillel | Learning a mahalanobis metric from equivalence constraints[END_REF][START_REF] Xing | Distance metric learning with applications to clustering with side-information[END_REF][START_REF] Bach | Learning spectral clustering[END_REF] and consider the goal of learning a metric for potentially several partitioning problems sharing the same metric, assuming that several fully or partially labelled partitioned datasets are available during the learning phase. While such labelled datasets are typically expensive to produce, there are several scenarios where these datasets have already been built, often for evaluation purposes. These occur in video segmentation tasks (see Section 6.1), image segmentation tasks (see Section 6.3) as well as change-point detection tasks in bioinformatics (see [START_REF] Hocking | Learning smoothing models of copy number profiles using breakpoint annotations[END_REF] and Section 5.3).

In this paper, we consider partitioning problems based explicitly or implicitly on the minimization of Euclidean distortions, which include K-means, spectral clustering and normalized cuts, and mean-based change-point detection. We make the following contributions:

-We review and unify several partitioning algorithms in Section 2, and cast them as the maximization of a linear function of a rescaled equivalence matrix, which can be solved by algorithms based on spectral relaxations or dynamic programming.

-Given fully labelled datasets, we cast in Section 4 the metric learning problem as a large-margin structured prediction problem, with proper definition of regularizers, losses and efficient loss-augmented inference.

-Given partially labelled datasets, we propose in Section 5 an algorithm, iterating between labelling the full datasets given a metric and learning a metric given the fully labelled datasets. We also consider in Section 5.3 extensions that allow changes in the full distribution of univariate time series (rather than changes only in the mean), with application to bioinformatics.

-We provide in Section 6 experiments where we show how learning the metric may significanty improve the partitioning performance in synthetic examples, video segmentation and image segmentation problems.

Related work.

The need for metric learning goes far beyond unsupervised partitionning problems. [START_REF] Weinberger | Distance metric learning for large margin nearest neighbor classification[END_REF] proposed a large margin framework for learning a metric in nearest-neighbours algorithms based on sets of must-link/must not link constraints, while [START_REF] Goldberger | Neighbourhood components analysis[END_REF] considers a probability-based non-convex formulation. For these works, a single dataset is fully labelled and the goal is to learn a metric leading to good testing performance on unseen data. Some recent work [START_REF] Jain | Metric and kernel learning using a linear transformation[END_REF] proved links between metric learning and kernel learning, permitting to kernelize any Mahalanobis distance learning problem.

Metric learning has also been considered in semi-supervised clustering of a single dataset, where some partial constraints are given. This includes the works of [START_REF] Bar-Hillel | Learning a mahalanobis metric from equivalence constraints[END_REF][START_REF] Xing | Distance metric learning with applications to clustering with side-information[END_REF], both based on efficient convex formulations. As shown in Section 6, these can be used in our settings as well by stacking several datasets into a single one. However, our discriminative large-margin approach outperforms these.

Moreover, the task of learning how to partition was tackled in [START_REF] Bach | Learning spectral clustering[END_REF] for spectral clustering. The problem set-up is the same (availability of several fully partitioned datasets), however, the formulation is non-convex and relies on the unstable optimization of eigenvectors. In Section 5.1, we propose a convex more stable large-margin approach.

Other approaches do not require any supervision [START_REF] De La Torre | Discriminative cluster analysis[END_REF], and perform dimensionality reduction and clustering at the same time, by iteratively alternating the computation of a low-rank matrix and a clustering of the data using the corresponding metric. However, they are unable to take advantage of the labelled information that we use.

Our approach can also be related to the one of [START_REF] Szummer | Learning CRFs using graph cuts[END_REF]. Given a small set of labelled instances, they use a similar large-margin framework, inspired by [START_REF] Tsochantaridis | Support vector machine learning for interdependent and structured output spaces[END_REF] to learn parameters of Markov random fields, using graph cuts for solving the "loss-augmented inference problem" of structured prediction. However, their segmentation framework does not apply to unsupervised segmentation (which is the goal of this paper). In this paper, we present a supervised learning framework aiming at learning how to perform an unsupervised task.

Our approach to learn the metric is nevertheless slightly different of the ones mentioned above. Indeed, we cast this problem as the solution of a structured SVM as in [START_REF] Tsochantaridis | Support vector machine learning for interdependent and structured output spaces[END_REF][START_REF] Taskar | Max-margin markov networks[END_REF]. This make our paper shares many conceptual steps with works like [START_REF] Caetano | Learning Graph Matching[END_REF][START_REF] Mcfee | Metric learning to rank[END_REF] where they use a structured SVM to learn in one case weights for graph matchings and a metric for ranking in the other case.

Partitioning through matrix factorization

In this section, we consider T multi-dimensional observations x 1 , . . . , x T ∈ R P , which may be represented in a matrix X ∈ R T ×P . Partitioning the T observations into K classes is equivalent to finding an assignment matrix Y ∈ {0, 1} T ×K , such that Y ij = 1 if the i-th observation is affected to cluster j and 0 otherwise. For general partitioning problems, no additional constraints are used, but for change-point detection problems, it is assumed that the segments are contiguous and with increasing labels. That is, the matrix Y is of the form

Y =       1 T1 0 . . . 0 0 . . . . . . . . . . . . . . . . . . 0 0 . . . 0 1 T K      
, where 1 D ∈ R D is the D-dimensional vector with constant components equal to one, and T j is the number of elements in cluster j. For any partition, we may re-order (non uniquely) the data points so that the assignment matrix has the same form; this is typically useful for the understanding of partitioning problems.

Distortion measure

In this paper, we consider partitioning models where each data point in cluster j is modelled by a vector (often called a centroid or a mean) c j ∈ R p , the overall goal being to find a partition and a set of means so that the distortion measure

T i=1 K j=1 Y ij x i - c j
2 is as small as possible, where • is the Euclidean norm in R P . By considering the Frobenius norm defined through

A 2 F = T i=1 P j=1 A 2 ij , this is equivalent to minimizing X -Y C 2 F ( 1
)
with respect to an assignment matrix Y and the centroid matrix C ∈ R K×P .

Representing partitions

Following [START_REF] Bach | Learning spectral clustering[END_REF][START_REF] De La Torre | Discriminative cluster analysis[END_REF], the quadratic minimization problem in Y can be solved in closed form, with solution C = (Y Y ) -1 Y X (it can be found by computing the matrix gradient and setting it to zero). Thus, the partitioning problem (with known number of clusters K) of minimizing the distortion in Eq. ( 1), is equivalent to:

min Y ∈{0,1} T ×K , Y 1 K =1 P X -Y (Y Y ) -1 Y X 2 F . (2)
Thus, the problem is naturally parameterized by the T ×T -matrix M = Y (Y Y ) -1 Y . This matrix, which we refer to as a rescaled equivalence matrix, has a specific structure. First the matrix Y Y is diagonal, with i-th diagonal element equal to the number of elements in the cluster containing the i-th data point. Thus M ij = 0 if i and j are in different clusters and otherwise equal to 1/D where D is the number of elements in the cluster containing the i-th data point. Thus, if the points are re-ordered so that the segments are composed of contiguous elements, then we have the following form

M =       11 /T 1 0 . . . 0 0 . . . . . . . . . . . . . . . . . . 0 0 . . . 0 11 /T K       .
In this paper, we use this representation of partitions. Note the difference with alternative representations Y Y which has values in {0, 1}, used in particular by [START_REF] Joulin | Discriminative clustering for image co-segmentation[END_REF]. We denote by M K the set of rescaled equivalence matrices, i.e., matrices M ∈ R T ×T such that there exists an assignment matrix

Y ∈ R T ×K such that M = Y (Y Y ) -1 Y .
For situations where the number of clusters is unspecified, we denote by M the union of all M K for K ∈ {1, . . . , N }.

Note that the number of clusters may be obtained from the trace of M , since

Tr M = Tr Y (Y Y ) -1 Y = Tr(Y Y ) -1 Y Y = K. This can also be seen by noticing that M 2 = Y (Y Y ) -1 Y Y (Y Y ) -1 Y = M , i.e.
, M is a projection matrix, with eigenvalues in {0, 1}, and the number of eigenvalues equal to one is exactly the number of clusters. Thus,

M K = M ∈ M, Tr M = K .
Learning the number of clusters K. Given the number of clusters K, we have seen from Eq. ( 2) that the partitioning problem is equivalent to

min M ∈M K X -M X 2 F = min M ∈M K Tr XX (I -M ) . (3)
In change-point detection problems, an extra constraint of contiguity of segments is added.

In the common situation when the number of clusters K is unknown, then it may be estimated directly from data by penalizing the distortion measure by a term proportional to the number of clusters, as usually done for instance in change-point detection [START_REF] Lavielle | Using penalized contrasts for the change-point problem[END_REF]. This is a classical idea that can be traced back to the AIC criterion [START_REF] Akaike | A new look at the statistical model identification[END_REF] for instance. Given that the number of clusters for a rescaled equivalence matrix M is Tr M , this leads to the following formulation:

min M ∈M Tr XX (I -M ) + λ Tr M (4)
Note that our metric learning algorithm also learns this extra parameter λ. Thus, the two types of partitioning problems (with fixed or unknown number of clusters) can be cast as the problem of maximizing a linear function of the form Tr(AM ) with respect to M ∈ M, with the potential constraint that Tr M = K. In general, such optimization problems may not be solved in polynomial time. In Section 2.3, we show how adding contiguity constraints makes it possible to obtain a solution in polynomial time through dynamic programming. For general situations, the K-means algorithm, although not exact, can be used to get good partitioning in polynomial time. In Section 2.4, we provide a spectral relaxation, which we use within our large-margin framework in Section 4.

Change-point detection by dynamic programming

The change-point detection problem is a restriction of the general partitioning problem where the segments are composed of contiguous elements. We denote by M seq the set of partition matrices for the change-point detection problem, and M seq K , its restriction to partitions with K segments.

The problem is thus of solving Eq. ( 4) (known number of clusters) or Eq. ( 3) (unknown number of clusters) with the extra constraint that M ∈ M seq . In these two situations, the contiguity constraint leads to exact polynomial-time algorithms based on dynamic programming. See, e.g., [START_REF] Rigaill | Pruned dynamic programming for optimal multiple change-point detection[END_REF]. This leads to algorithms for maximizing Tr(AM ), when A is positive semi-definite in O(T 2 ). When the number of segments K is known the running time complexity is O(KT 2 ).

We now describe a reformulation that can solve max M ∈M Tr(AM ) for any matrix A (potentially with negative eigenvalues, as from Eq. ( 4)). This algorithm is presented in Algorithm 1. It only requires some preprocessing of the input matrix A, namely computing its summed area table I (or image integral), defined to have the same size as A and with I ij = i ≤i, j ≤j A i j . In words it is the sum of the elements of A which are above and to the left of respectively i and j. A similar algorithm can be derived in the case where M ∈ M K .

Algorithm 1 Dynamic programming for maximizing Tr(AM ) such that M ∈ M Require:

T × T matrix A Compute I, image integral (summed area table) of A Initialize C(1, :) =diag(I) for t = 1 : T -1 do C(t + 1, t + 1) = max(C(1 : t, t)) + I(t + 1, t + 1) for u=t+1 . . . T do β = I(s,s)+I(t+1,t+1)-I(s,t+1)-I(t+1,s) (u-t) C(t + 1, u) = max(C(1 : t, t)) + β end for end for Backtracking steps: t c = T , Y = ∅ while t c 1 do t old c = t c , t c = argmax {C(t c , :)} s = t old c -t c + 1, Y = Y 0 0 1 s end while return Matrix M = Y (Y Y ) -1 Y .

K-means clustering and spectral relaxation

For a known number of clusters K, K-means is an iterative algorithm aiming at minimizing the distortion measure in Eq. ( 1): it iterates between (a) optimizing with respect to C, i.e., C = (Y Y ) -1 Y X, and (b) minimizing with respect to Y (by assigning points to the closest centroids). Note that this algorithm only converges to a local minimum and there is no known algorithm to perform an exact decoding in polynomial time in high dimensions P . Moreover, the K-means algorithm cannot be readily applied to approximately maximize any linear function Tr AM with respect to M ∈ M, i.e., when A is not positive-definite or the number of clusters is not known.

Following [START_REF] Shi | Normalized cuts and image segmentation[END_REF][START_REF] Ng | On spectral clustering: Analysis and an algorithm[END_REF][START_REF] Bach | Learning spectral clustering[END_REF], we now present a spectral relaxation of this problem. This is done by relaxing the set M to the set of matrices that satisfy M 2 = M (i.e., removing the constraint that M takes a finite number of distinct values). When the number of clusters is known, this leads to the classical spectral relaxation, i.e., max

M ∈M, Tr M =K Tr(AM ) max M 2 =M, Tr M =K Tr(AM ),
which is equal to the sum of the K largest eigenvalues of A; the optimal matrix M of the spectral relaxation is the orthogonal projector on the eigenvectors of A with K largest eigenvalues.

When the number of clusters is unknown, we have:

max M ∈M Tr(AM ) max M 2 =M Tr(AM ) = Tr(A) + ,
where Tr(A) + is the sum of positive eigenvalues of A. The optimal matrix M of the spectral relaxation is the orthogonal projector on the eigenvectors of A with positive eigenvalues. Note that in the formulation from Eq. ( 4), this corresponds to thresholding all eigenvalues of XX which are less than λ.

We denote by

M spec = {M ∈ R P ×P , M 2 = M } and M spec K = {M ∈ R P ×P , M 2 = M, Tr M = K}
the relaxed set of rescaled equivalence matrices.

Metric learning

In this paper, we consider learning a Mahalanobis metric, which may be parameterized by a positive definite matrix B ∈ R P ×P . This corresponds to replacing dot-products x i x j by x i Bx j , and XX by XBX . Thus, when the number of cluster is known, this corresponds to min

M ∈M K Tr XBX (I -M ) (5)
or, when the number of clusters is unknown, to:

min M ∈M Tr BX (I -M )X + λ Tr M. (6)
Note that by replacing B by Bλ and dividing the equation by λ, we may use an equivalent formulation of Eq. ( 6) with λ = 1, that is:

min M ∈M Tr XBX (I -M ) + Tr M. (7)
The key aspect of the partitioning problem is that it is formulated as optimizing with respect to M a function linearly parameterized by B. The linear parametrization in M will be useful when defining proper losses and efficient loss-augmented inference in Section 4. Note that we may allow B to be just positive semi-definite. In that case, the zeroeigenvalues of the pseudo-metric corresponds to irrelevant dimensions. That means in particular we have performed dimensionality reduction on the input data. We propose a simple way to encourage this desirable property in Section 4.3.

Loss between partitions

Before going further and apply the framework of Structured prediction [START_REF] Tsochantaridis | Support vector machine learning for interdependent and structured output spaces[END_REF] in the context of metric learning, we need to find a loss on the output space of possible partitioning which is well suited to our context. To avoid any notation conflict, we will refer in that section to P as a general set of partition (it can corresponds for instance to M seq ).

Some standard loss

The Rand index When comparing partitions [START_REF] Hubert | Comparing partitions[END_REF], a standard way to measure how different two of them are is to use the Rand [START_REF] Rand | Objective criteria for the evaluation of clustering methods[END_REF] index which is defined, for two partitions of the same set of T elements S P 1 = {P 1 1 , . . . , P K1 1 } and P 2 {P 1 2 , . . . , P K2 2 } as the sum of concordant pairs over the number of possible pairs. More precisely, if we consider all the possible pairs of elements of S, the concordant pairs are defined as the sum of the pairs of elements which both belong to the same set in P 1 and P 2 and of the pairs which are not in the same set both in P 1 and P 2 . In matricial terms, it is linked to the Frobenius distance between the equivalence matrices representing P 1 and P 2 (these matrices are binary matrices of size T × T which are 1 if and only if the element i and the element j belong to the same set of the partition). This loss is not necessarily very well suited to our problem, since intuitively one can see that it doesn't take into account the size of each subset inside the partition, whereas our concern is to optimize intra class variance which is a rescaled indicator.

Hausdorff distance In the change-point detection litterature, a very common way to measure dissimilarities between partitions is the so-called Hausdorff distance [START_REF] Boysen | Consistencies and rates of convergence of jump-penalized least squares estimators[END_REF] on the elements of the frontier of the elements of the partitions (the need for a frontier makes it inapplicable directly to the case of general clustering). Let's consider two partitions of a finite set S of T elements. We assume that the elements have a sequential order and thus elements of partitions P 1 and P 2 have to be contiguous. It is then possible to define the frontier (or set of ruptures) of P 1 as the collection of indexes ∂P 1 = {inf P 2 1 , . . . , inf P K 1 }. Then, by embedding the set S into [0, 1] (it corresponds just to normalize the time indexes so that they are in [0, 1]), we can consider a distance d on [0, 1], (typically the absolute value) and then define the associated Hausdorff distance d H (P 1 , P 2 ) = max{sup x∈∂P1 inf y∈∂P2 d(x, y), sup y∈∂P2 inf x∈∂P1 d(x, y)}

The loss considered in our context In this paper, we consider the following loss, which was originated proposed in a slightly different form by [START_REF] Hubert | Comparing partitions[END_REF] and has then been widely used in the field of clustering [START_REF] Bach | Learning spectral clustering[END_REF]. This loss is a variation of the χ 2 association in a K 1 ×K 2 contingency table (see [START_REF] Hubert | Comparing partitions[END_REF]). More precisely, if we consider the contingency table associated to P 1 (partition of a set of size T ) with K 1 elements and P 2 with K 2 elements (the contingency table being the K 1 × K 2 table C such that C i,j = n ij the number of elements in element i of P 1 and in element j of P 2 ), we have that

M -N 2 F = K 1 + K 2 -χ 2 (C)+T T . (M, N ) = 1 T M -N 2 F = 1 T Tr(M ) + Tr(N ) -2 Tr(M N ) . (8)
Moreover, if the partitions encoded by M and N have clusters P 1 1 , . . . , P K1

1 and P 1 2 , . . . , P K2 2 , then T (M, N ) = K 1 + K 2 -2 k,l |A k ∩B l | 2 |A k |•|B l | .
This loss is equal to zero if the partitions are equal, and always less than 1 T (K + L -2). Another equivalent interpretation of this index is given by, with the usual convention that for the element of S indexed by i P 1 (i) is the subset of P 1 where i belongs:

T (M, N ) = K 1 + K 2 -2 T i=1 |P 1 (i) ∩ P 2 (i)| |P 1 (i)| × |P 2 (i)| .
This index seems intuitively much more suited to the study of the problem of variance minimization since it involves the rescaled equivalence matrices which parametrize naturally these kind of problems. We examine in the Appendix more facts about these losses and their links, especially about the asymptotic behaviour of the loss we use in the paper. We also show a link between this loss and the Hausdorff in the case of change-point detection.

Structured prediction for metric learning

As shown in the previous section, our goal is to learn a positive definite matrix B, in order to improve the performance of structured output algorithm that minimizes with respect to M ∈ M, the following cost function of Eq. 7. Using the change of variable described in the table below, the partitioning problem may be cast as

max M ∈M w, ϕ(X, M ) or max M ∈M K w, ϕ(X, M ) .
where A, B is the Frobenius dot product.

Number of clusters

ϕ(X, M ) w Known X M X B (Tr M = K) Unknown 1 T X M X 0 0 M B 0 0 -I
We denote by F the vector space where the vector w defined above belongs to. Our goal is thus to estimate w ∈ F from N pairs of observations (X i , M i ) ∈ X × M. This is exactly the goal of large-margin structured prediction [START_REF] Tsochantaridis | Support vector machine learning for interdependent and structured output spaces[END_REF], which we now present. We denote by N a generic set of matrices, which may either be M, M spec , M seq , M K , M spec K , M seq K , depending on the situation (see Section 4.2 for specific cases).

Large-margin structured output learning

In the margin-rescaling framework of [START_REF] Tsochantaridis | Support vector machine learning for interdependent and structured output spaces[END_REF], using a certain loss : N × N → R + between elements of N (here partitions), the goal is to minimize with respect to w ∈ F,

1 N N i=1 argmax M ∈N w, ϕ(X i , M ) , M i + Ω(w),
where Ω is any (typically convex) regularizer. This framework is standard in machine learning in general and metric learning in particular (see e.g, [START_REF] Jain | Metric and kernel learning using a linear transformation[END_REF]). This loss function w → argmax M ∈N w, ϕ(X i , M ) , M i is not convex in M , and may be replaced by the convex surrogate

L i (w) = max M ∈N (M, M i ) + w, ϕ(X i , M ) -ϕ(X i , M i ) ,
leading to the minimization of

1 N N i=1 L i (w) + Ω(w). (9)
In order to apply this framework, several elements are needed: (a) a regularizer Ω, (b) a loss function , and (c) the associated efficient algorithms for computing L i , i.e., solving the loss-augmented inference

problem max M ∈N (M, M i )+ w, ϕ(X i , M )- ϕ(X i , M i ) .
As discussed in Section 3, a natural loss on our output space is given by the Frobenius norm of the rescaled equivalence matrices associated to partitions.

Loss-augmented inference problem

Efficient minimization is key to the applicability of large-margin structured prediction and this problem is a classical computational bottleneck. In our situation the cardinality of N is exponential, but the choice of loss between partitions lead to the problem max M ∈N Tr(A i M ) where:

-A i = 1 T (X i BX i -2M i + Id) if the number of clusters is known. -A i = 1
T (X i BX i -2M i ) otherwise. Thus, the loss-augmented problem may be performed for the change-point problems exactly (see Section 2.3) or through a spectral relaxation otherwise (see Section 2.4). Namely, for change-point detection problems, N is either M seq or M seq K , while for general partitioning problems, it is either M spec or M spec K .

Regularizer

We may consider several parametrizations/regularizers for our positive semidefinite matrix B. We may classically (see e.g, [START_REF] Jain | Metric and kernel learning using a linear transformation[END_REF]) penalize Tr B 2 = B 2 F , which is the classical squared Euclidean norm. However, two variants of our algorithm are often needed for practical problems.

Diagonal metric. To limit the number of parameters, we may be interested in only reweighting the different dimensions of the input data, i.e., we can impose the metric to be diagonal, i.e, B = Diag(b) where b ∈ R P . Then, the constraint is b 0, and we may penalize by b 1 = 1 P b or b 2 2 , depending whether we want to promote zeros in b (i.e., to do feature selection).

Low-rank metric. Another potentially desirable property is the interpretability of the obtained metric in terms of its eigenvectors. Ideally we want to have a pseudometric with a small rank. As it is classically done, we relaxed it into the sum of singular values. Here, since the matrix B is symmetric positive definite, this is simply the trace Tr(B).

Optimization

In order to optimize the objective function of Eq. ( 9), we can use several optimization techniques. This objective present the drawback of being non-smooth and thus the convergence speed that we can expect are not very fast. In the structured prediction litterature, the most common solvers are based on cuttingplane methods (see [START_REF] Tsochantaridis | Support vector machine learning for interdependent and structured output spaces[END_REF]) which can be used in our case for small dimensional-problem (i.e., low P ). Otherwise we use a projected subgradient method, which leads to more numerous but cheaper iterations. Cutting plane and Bundle methods [START_REF] Teo | Bundle methods for regularized risk minimization[END_REF] shows the best speed performances when the dimension of the feature space of the data to partition is low, but were empirically outperformed by a subgradient in the very high dimensional setting.

Extensions

We now present extensions which make our metric learning more generally applicable.

Spectral clustering and normalized cuts

Normalized cut segmentation is a graph-based formulation for clustering aiming at finding roughly balanced cuts in graphs [START_REF] Shi | Normalized cuts and image segmentation[END_REF]. The input data X is now replaced by a similarity matrix W ∈ R T ×T + and, for a known number of clusters K, as shown by [START_REF] Ng | On spectral clustering: Analysis and an algorithm[END_REF][START_REF] Bach | Learning spectral clustering[END_REF], it is exactly equivalent to

max M ∈M K Tr M W ,
where W = Diag(W 1) -1/2 W Diag(W 1) -1/2 is the normalized similarity matrix.

Parametrization of the similarity matrix W . Typically, given data points x 1 , . . . , x T ∈ R P (in image segmentation problem, these are often the concatenation of the positions in the image and local feature vectors), the similarity matrix is computed as

(W B ) ij = exp -(x i -x j ) B(x i -x j ) , ( 10
)
where B is a positive semidefinite matrix. Learning the matrix B is thus of key practical importance. However, our formulation would lead to efficiently learning (as a convex optimization problem) parameters only for a linear parametrization of W . While the linear combination is attractive computationally, we follow the experience from the supervised setting where learning linear combinations of kernels, while formulated as a convex problem, does not significantly improve on methods that learn the metric within a Gaussian kernel with non-convex approaches (see, e.g., [START_REF] Gehler | On feature combination for multiclass object classification[END_REF][START_REF] Marszałek | Learning object representations for visual object class recognition[END_REF]).

We thus stick to the parametrization of Eq. [START_REF] De La Torre | Discriminative cluster analysis[END_REF]. In order to make the problem simpler and more tractable, we consider spectral clustering directly with W and not with its normalized version, i.e., our partitioning problem becomes

max M ∈M Tr W M or max M ∈M K Tr W M.
In order to solve the previous problem, the spectral relaxation outlined in Section 2.4 may be used, and corresponds to computing the eigenvectors of W (the first K ones if K is known, and the ones corresponding to eigenvalues greater than a certain threshold otherwise).

Non-convex optimization. In our structured output prediction formulation, the loss function for the i-th observation becomes (for the case where the number of clusters is known):

max M ∈M spec K (M, M i ) + Tr W B (M -M i ) = -Tr W B M i + max M ∈M spec K (M, M i ) + Tr W B M .
It is not a convex function of B, however, it is a difference of a concave and a convex function, which can be dealt with using majorization-minimization algorithm [START_REF] Yuille | The concave-convex procedure[END_REF]. The idea of this algorithm is simply to upper-bound the concave part -Tr W B M i by its linear tangent. Then the problem becomes convex and can be optimized using one of the method proposed in Section 4. [START_REF] Bar-Hillel | Learning a mahalanobis metric from equivalence constraints[END_REF] We then iterate the process, which is known to be converging to a stationary point.

Partial labellings

The large-margin convex optimization framework relies on fully labelled datasets, i.e., pairs (X i , M i ) where X i is a dataset and M i the corresponding rescaled equivalence matrix. In many situations however, only partial information is available. In these situations, starting from the PCA metric, we propose to iterate between (a) label all datasets using the current metric and respecting the constraints imposed by the partial labels and (b) learn the metric using Section 4 from the fully labelled datasets. See an application in Section 6.1.

Detecting changes in distribution of temporal signals

In sequential problems, for now, we are just able to detect changes in the mean of the distribution of time series but not to detect change-points in the whole distribution (e.g., the mean may be constant but the variance piecewise constant). Let us consider a temporal series X in which some breakpoints occur in the distribution of the data. From this single series, we build several series permitting to detect these changes, by considering features built from X, in which the change of distribution appears as a change in mean. A naive way would be to consider the moments of the data X, X 2 , X 3 , . . . , X r but unfortunately as r grows these moments explode. A way to prevent them from exploding is to use the robust Hermite moments [START_REF] Welling | Robust higher order statistics[END_REF]. These moments are computed using the Hermite functions and permit to consider the p-dimensional series H 1 (X), H 2 (X), . . . , where H i (X) is the i-th Hermite function

H i (x) = 2 √ 2 i πi!e -x 2 2σ 2 (-1) i 2 i/2 e x 2 2 d i dx i e -x 2 2
.

Bioinformatics application. Detection of change-points in DNA sequences for cancer prognosis provides a natural testbed for this approach. Indeed, in this field, researchers face data which are linked to the number of copies of each gene along the DNA (a-CGH data as used in [START_REF] Hocking | Learning smoothing models of copy number profiles using breakpoint annotations[END_REF]). The presence of such changes are generally related to the development of certain types of cancers. On the data from the Neuroblastoma dataset [START_REF] Hocking | Learning smoothing models of copy number profiles using breakpoint annotations[END_REF], some caryotypes with changes of distribution were manually annotated. Without any metric learning, the global error rate in change-point identification is 12%. By considering the first 5 Hermite moments and learning a metric, we reach a rate of 6.9%, thus improving significantly the performance.

Experiments

We have conducted a series of experiments showing improvements of our large-margin metric learning methods over previous metric learning techniques.

Change point detection

Synthetic examples and robustness to lack of information. We consider 300dimensional time series of length T = 600 with an unknown number of breakpoints. Among these series only 10 are relevant to the problem of change-point detection, i.e., 290 series have abrupt changes which should be discarded. Since the identity of the 10 relevant time series is unknown, by learning a metric we hope to obtain high weights on the relevant series and small weights on the others. The number of segments is not assumed to be known and is learned automatically. Moreover, in this experiment we progressively remove information, in the sense that as input of the algorithm we only give a fraction of the original time series (and we measure the amount of information given through the ratio of the given temporal series compared to the original one). Results are presented in Figure 1. As expected, the performance without metric learning is bad, while it is improved with PCA. Techniques such as RCA [START_REF] Bar-Hillel | Learning a mahalanobis metric from equivalence constraints[END_REF] which use the labels improve even more (all datasets were stacked into a single one with the corresponding supervision); however, it is not directly adapted to change-point detection, it requirse dimensionality reduction to work and the performance is not robust to the choice of the number of dimensions. Note also that all methods except ours are given the exact number of change-points. Our large-margin approach outperforms the other metric, in the convex setting (i.e., extreme right of the curves), but also in partially-supervised setting where we use the alternative approach describe in Section 5.2.

Video segmentation. We applied our method to data coming from old TV shows (the length of the time series in that case is about 5400, with 60 to 120 change-points) where some speaking passages alternate with singing ones. The videos are from 1h up to 1h30 long. We aim at recovering the segmentation induced by the speaking parts and the musical ones. Following [START_REF] Arlot | Kernel change-point detection[END_REF], we use GIST features for the video part and MFCC features for the audio. The features were aggregated every second so that the temporal series we are considering are about several thousands vectors long, which is still computationally tractable using the dynamic programming of Algorithm 1. We used 4 shows for train, 3 for validation, 3 for test. The running times of our Matlab implementation were in order of a few hours.

The results are described in Table 1. We consider three different settings: using only the image stream, only the audio stream or both. In these three cases, we consider using the existing metric (no learning), PCA, or our approach. In all settings, metric learning improves performance. Note that the performance is best with only the audio stream and our metric learning, given both streams, manages to do almost as well as with only the audio stream, thus illustrating the robustness of using metric learning in this context.

K-means clustering

Using the partition induced by the classes as ground truth, we tested our algorithm on some classification datasets from the UCI machine learning repository, using the classification information as partitions, following the methodology proposed by [START_REF] Xing | Distance metric learning with applications to clustering with side-information[END_REF]. This application of our framework is a little extreme in the sense that we assume only one partitioning as training point (i.e., N = 1). The results are presented in Table 2. For the "Letters" and "Mov. Libras" datasets, there are no significant differences, while for the "Wine" dataset, RCA is the best, and for the "Iris" dataset, our largemargin approach is best: even in this extreme case, we are competitive with existing techniques.

Table 3: Performance of the metric learned in the context of image segmentation, comparing the result of a learned metric vs. the results of an exhaustive grid search (Grid). σ is the standard deviation of the difference between the loss with our metric and the grid search. To assess the significance of our results, we perform t-tests whose p-values are respectively 2.10 -9 and 4.10 -9 .

Loss used

Learned metric Grid σ Loss of Eq. ( 8)

1.54 1.77 0.3 Jaccard distance 0.45 0.53 0.11

Image Segmentation

We now consider learning metrics for normalized cuts and consider the Weizmann horses database [START_REF] Borenstein | Learning to segment[END_REF], for which groundtruth segmentation is available. Using color and position features, we learn a metric with the method presented in Section 5.1 on 10 fully labelled images. We then test on the remaining 318 images. We compare the results of this procedure to a cross-validation approach with an exhaustive search on a 2D grid adjusting one parameter for the position features and one other for color ones. The loss between groundtruth and segmentations obtained by the normalized cuts algorithm is measured either by Eq. ( 8) or the Jaccard distance. Results are summarized in Table 3, with some visual examples in Figure 2. The metric learning within the Gaussian kernel significantly improves performance. The running times of our pure Matlab implementation were in order of several hours to get convergence of the convex-concave procedure we used.

Conclusion

We have presented a large-margin framework to learn metrics for unsupervised partitioning problems, with application in particular to change-point detection in video streams and image segmentation, with a significant improvement in partitioning performance. For the applicative part, following recent trends in image segmentation (see, e.g., [START_REF] Joulin | Discriminative clustering for image co-segmentation[END_REF]), it would be interesting to extend our change-point framework so that it allows unsupervised co-segmentation of several videos: each segment could then be automatically labelled so that segments from different videos but with the same label correspond to the same action.

A Asymptotics of the loss between partitions

Note that in this section, we will denote by d 2 F the "normalized" loss between partitions. This means that, with the notations of the article when considering two matrices M and N representing some partitions P and Q in the generic set of partitions P, we have T d 2 F = M -N 2 F . Throughout this section, we will refer to the size of a partition as the number of clusters.

A.1 Hypothesis

• We assume we consider P and Q two partitions of the same size, with a common number of clusters K.

• ∀k, l ∈ {1, . . . , K}, we denote k→l = |P k ∩ Q l |, the flow which goes out from P to Q when P goes to Q.

(P, Q) = max k =l k→l min(|P k ||P l |) , then ∃δ : P 2 → R such that sup P,Q,K×M (P,Q)≤ |δ(P, Q)| → →0 0 and ∀P, Q ∈ P of the same size K, T , T d 2 F (P, Q) = 2 K k=1 k→ + →k |P k | × (1 + δ(P, Q))
Proof. From the expressions of Section 3.1, we can write :

d 2 F (P, Q) = 2K -2 k,l |P k ∩ Q l | 2 |Q l ||P k | = 2 K k=1 (1 - |P k ∩ Q k | 2 |Q k ||P k | ) + 2 k =l 2 k→l |P k |(|P l | -→ + →k )
The second term can be pretty easily bounded using M

2 k =l 2 k→l |P k |(|P l | -k→ + →l ) ≤ 2M k =l k→l |P l | -k→ .
We can go further, noticing that k→ ≤ KM |P k |, which leads eventually to, if M ≤ 1/2K (and this is the case if δ tends to 0 in the sense of the assumption of the theorem):

2 k =l 2 k→l |P k |(|P l | -→ + →k ) ≤ 2M k =l k→l |P l | -k→ ≤ 4M k =l k→l P l .
Now, let's bound the first term, which is a little more long:

1 - |P k ∩ Q k | 2 |Q k ||P k | = 1 - (|P k -k→ ) 2 |P k (|P k | -k→ + →k ) = k→ + →k |P k | × 1 1 + -k→ + →k |P k | - 2 k→ |P k |(|P k | -k→ + →k )
But, for the same reasons as when we bounded the second term

2 k→ |P k |(|P k | -k→ + →k ) ≤ 2 K k=1 2 k→ |P k | 2 .
Using the fact that ∀k, (K)M ≥ k→ |P k | , we finally get that, when M ≤ 1/2K:

2 k→ |P k |(|P k | -k→ + →k ) ≤ 4M K k=1 k→ |P k | .
Thus, putting everything together, when KM → 0, we get the statement of the theorem.

B Equivalence between the loss between partition and the Hausdorff distance for change point detection

As mentioned in the title of this , there is a deep link between the Hausdorff distance and the distance between partition we used throughout this paper in the case of changepoint detection applications. We propose here to show that the two distances are equivalent.

B.1 Hypothesis and notations

• We consider the segmentations P and Q has having been embedded in [0, 1] so that we can consider a distance d on [0, 1] to define the Hausdorff distance between the frontiers of the elements of P and Q.

• We denote l m (P ) the minimal length of a segment in a partition P ∈ P and l ma the maximal one.

• We denote by d h the Hausdorff distance between partitions as described in Section 3 |P k ||Q l | . Note that the hypothesis of the Hausdorff distane being inferior to the half of the minimal length is just here to say that the l-th segment of partition Q can only overlap with l -1-th, lth and l + 1-th elements of P . Thus :

B.2 Main result

K k,l=1 |P k ∩ Q l | 2 |P k ||Q l | = K k,=1 |P k ∩ Q k | 2 |P k ||Q k | + K-1 k,=1 |P k ∩ Q k+1 | 2 |P k ||Q k+1 | + K-1 k=0 |P k ∩ Q k-1 | 2 |P k ||Q k-1 | ≥ K k=1 (|P k | -2 ) 2 |P k | + 2 = K k=1 ((1 -2 |P k | ) 2 1 + 2 |P k | ≥ K -6 K k=1 1 |P k | ≥ K -6 K l m (P )
which gives us the majorization. Note that we used the fact that ∀x ∈ [0, 1], the inequality (1-x) 1+x ≥ 1 -3x holds.

For the minoration, note that it is true all the time, but we will just give the proof in the case where the Hausdorff distance is such that d h (P, Q) ≤ l m (P )/2 and where |P | = |Q|.

First, let's begin by some general statements : i)By definition = max{max Pi∈∂P min Qj ∈∂Q d( Pi , Qj ) max Qi∈∂Q min Pj ∈∂P d( Qi , Pj )}. ii) If the first term in the max is attained, that means there exists some (i * , j * ) such that | Pi * -Qj * | = . It also means that, if we look at the sequences, there is no elements of ∂Q is between Pi * and Qj * . Thus, by definition of the loss d 2 F (P, Q) ≥ 2 α∈Pj ∩Q j * -1 ,β∈Pj \Q j * -1

Figure 1 :

 1 Figure1: Performances on synthetic data vs. the quantity of information available in the time series. Note the small error bars. We compare ourselves against a metric learned by RCA (with 3 or 4 components), an exhaustive search for one regularization parameter, and PCA.

Figure 2 :

 2 Figure 2: From left to right: image segmented with our learned metric, image segmented by a parameter adjusted by exhaustive search, groundtruth segmentation, original image in gray.

Theorem 2 . 2 F

 22 Let P,Q denote two partitions. If |P | = |Q| and d h (P, Q) = < 1 2 l m (P ), then we have the following:l ma (P ) ≤ d 2 F (P, Q) ≤ 12K l m (P ) .Moreover, without assuming |P | = |Q|, we getd (P, Q) ≥ max(l ma (P ), l m (Q))) ≥ TProof. First, let's do the majorization part Using the expressions of Section 3.1, we have to minorateK k,l=1 |P k ∩Q l | 2

2

 2

Table 1 :

 1 Empirical performance on each of the three TV shows used for testing. Each subcolumn stands for a different TV show. The smaller the loss is, the better the segmentation is.

	Method		Audio	Video	Both
	PCA	23	41 34 40 55 25 29	53	37
	Reg. parameter 29	48 33 59 55 47 40	48	36
	Metric learning 6.1 9.3 7 10 14 11 8.7 9.6 7.8

Table 2 :

 2 Performance of the metric learning versus the Euclidean distance, and other metric learning algorithms such as RCA or[START_REF] Xing | Distance metric learning with applications to clustering with side-information[END_REF]. We use the loss from Eq. (8).

	Dataset	Ours	Euclidean	RCA	[32]
	Iris	0.18 ± 0.01	0.55 ± 10 -11	0.43 ± 0.02	0.30 ± 0.01
	Wine	1.03 ± 0.04	3.4 ± 3.10 -4 0.88 ± 0.14	3.08 ± 0.1
	Letters	34.5 ± 0.1	41.62 ± 0.2	34.8 ± 0.5	35.26 ± 0.1
	Mov. Libras	14 ± 1	15 ± 0.2	22 ± 2	15.07 ± 1

•

  We define the global outer flow as k→ = l =k k→l and the global inner flow as →l = l =k k→l

A.2 Main result

Theorem 1. Let P and Q two partitions satisfying our hypothesis. If we note M

  , and a short computation leads tod 2 F (P, Q) ≥ 2 |P * j | (1-|P j * | ) + . iii) Ifthe second term in the max is attained, the same minoration holds by permuting indices. Let's go back to our special case, we have |P * i | > 2 and |Q * i | > 2 . This leads to

	1 P * j 2 d 2 F (P, Q) ≥ max(	l ma (P )	,	l ma (Q)	)