Tony Ribeiro
email: tonyribeiro@nii.ac.jp

Katsumi Inoue
email: inoue@nii.ac.jp

Chiaki Sakama
email: sakama@sys.wakayama-u.ac.jp

A BDD-Based Algorithm for Learning from Interpretation Transition

. However, both the run time and the memory space of this algorithm are exponential, so a better data structure and an efficient algorithm have been awaited. In this paper, we propose a new learning algorithm of this method utilizing an efficient data structure inspired from Ordered Binary Decision Diagrams. We show empirically that using this representation we can perform the same learning task faster with less memory space.

Introduction

In recent years, there has been a notable interest in the field of Inductive Logic Programming (ILP) to learn from system state transitions as part of a wider interest in learning the dynamics of systems [START_REF] Muggleton | Ilp turns 20[END_REF][START_REF] Inoue | Learning from interpretation transition[END_REF]. Learning system dynamics has many applications in multi-agent systems, robotics and bioinformatics alike. Knowledge of system dynamics can be used by agents and robots for planning and scheduling. In bioinformatics, learning the dynamics of biological systems can correspond to the identification of the influence of genes and can help to design more efficient drugs. In some previous works, state transition systems are represented with logic programs [START_REF] Inoue | Logic programming for boolean networks[END_REF][START_REF] Inoue | Oscillating behavior of logic programs[END_REF], in which the state of the world is represented by an Herbrand interpretation and the dynamics that rule the environment changes are represented by a logic program P . The rules in P specify the next state of the world as an Herbrand interpretation through the immediate consequence operator (also called the T P operator) [START_REF] Van Emden | The semantics of predicate logic as a programming language[END_REF][START_REF] Apt | Towards a theory of declarative knowledge[END_REF]. With such a bakground, Inoue et al. [START_REF] Inoue | Learning from interpretation transition[END_REF] have recently proposed a framework to learn logic programs from traces of interpretation transitions (LFIT). The learning setting of this framework is as follows.

We are given a set of pairs of Herbrand interpretations (I, J) as positive examples such that J = T P (I), and the goal is to induce a normal logic program (NLP) P that realizes the given transition relations. In [START_REF] Inoue | Learning from interpretation transition[END_REF], the authors showed one of the possible usages of LFIT: LF1T, learning from 1-step transitions. In that paper, an algorithm is proposed to iteratively learn an NLP that realizes the dynamics of the system by considering step transitions one by one. The iterative character of LF1T has applications in bioinformatics, cellular automata, multi-agent systems and robotics. We can easily imagine an agent or a robot that learns the dynamics of its environment from its observations, learning the consequences of its actions according to the state of the world step-by-step. Aggregating more and more observations, the agent becomes able to predict the evolution of the world more precisely and can use this knowledge for planning and scheduling.

In this paper, we propose a new version of the LF1T algorithm based on Binary Decision Diagrams (BDDs) [START_REF] Akers | Binary decision diagrams[END_REF][START_REF] Bryant | Graph-based algorithms for boolean function manipulation[END_REF]. A BDD is a canonical representation of a Boolean formula which has been successfully used in many research fields such as Boolean satisfiability solvers [START_REF] Aloul | Zbdd-based backtrack search sat solver[END_REF], data mining [START_REF] Minato | Frequent closed item set mining based on zero-suppressed bdds[END_REF], ILP [START_REF] De Raedt | Problog: A probabilistic prolog and its application in link discovery[END_REF] and abduction [START_REF] Simon | Efficient consequence finding[END_REF][START_REF] Inoue | Evaluating abductive hypotheses using an em algorithm on bdds[END_REF]. ProbLog [START_REF] De Raedt | Problog: A probabilistic prolog and its application in link discovery[END_REF] is a probabilistic logic programming language that computes probabilities via BDDs. A ProbLog program computes the probability of a query atom by applying sum-product computation to a BDD, but allows definite clauses only. For abduction in propositional theories, Simon and del Val [START_REF] Simon | Efficient consequence finding[END_REF] propose a consequence-finding procedure implemented on Zero-suppressed BDDs. Inoue et al. [START_REF] Inoue | Evaluating abductive hypotheses using an em algorithm on bdds[END_REF] run the EM algorithm over BDDs to evaluate abductive hypotheses.

The main concern of our LF1T algorithm is the size of NLPs learned. For the sake of memory usage and reasoning time, a small NLP could be preferred in multi-agent and robotics applications. In bioinformatics, it can be easier and faster to perform model checking on Boolean networks represented by a compact NLP than the set of all state transitions. In previous algorithms, LF1T uses resolution techniques to generalize rules and reduces the size of the output NLP. The novelty of our approach is the adaptation of these techniques to the BDD structure. Here, we develop a method to perform LF1T operations on a BDD that also realizes usual BDD merging operations as well as novel simplification operations. We represent an NLP by a set of BDD structures where each BDD encodes rules with the same head literal. Assuming that rules respect a variable ordering, our data structure is similar to an Ordered BDD (OBDD) [START_REF] Bryant | Ordered binary decision diagrams[END_REF][START_REF] Bryant | Symbolic boolean manipulation with ordered binary-decision diagrams[END_REF]. In our approach, each BDD represents a formula in disjunctive normal form that defines whether a literal is true at the next time step. Because LF1T does not learn negative rules, our structure only represents rules that imply the head literal to be true. In that sense it can also be considered a Zero-suppressed Binary Decision Diagram (ZDD) [START_REF] Minato | Zero-suppressed bdds for set manipulation in combinatorial problems[END_REF].

Using a BDD representation we can also merge the common part of rules and learn the same NLP with less memory usage than in previous versions of LF1T. One weak point of the previous LF1T algorithm is that learning becomes slower and slower as the NLP learned becomes bigger because it has to check more and more rules. In practice, the compact representation of the BDD structure reduces the sensitivity of the LF1T learning time to the NLP size. Study of the computational complexity of our new method shows that it remains equivalent to the previous version of LF1T in the worst case. Using examples from the biological literature we show through experimental re-sults that our new algorithm still outperforms the two previous versions of LF1T in practice.

The rest of this paper is organized as follows. Section 2 reviews LF1T together with two previous versions of its algorithms. Section 3 describes the new LF1T algorithm based on BDDs and discusses its computational complexity. Section 4 shows experimental results of the new algorithm compared to the two previous versions of LF1T on learning Boolean networks.

Learning from 1-Step Transitions

We consider a first-order language and denote the Herbrand base (the set of all ground atoms) as B. A (normal) logic program (NLP) is a set of rules of the form

A ← A 1 ∧ • • • ∧ A m ∧ ¬A m+1 ∧ • • • ∧ ¬A n (1)
where A and A i 's are atoms (n ≥ m ≥ 0). For any rule R of the form (1), the atom A is called the head of R and is denoted as h(R), and the conjunction to the right of ← is called the body of R. We represent the set of literals in the body of R of the form (1) as b(R) = {A 1 , . . . , A m , ¬A m+1 , . . . , ¬A n }, and the atoms appearing in the body of R positively and negatively as b

+ (R) = {A 1 , . . . , A m } and b -(R) = {A m+1 , . . . , A n },
respectively. The set of ground instances of all rules in a logic program P is denoted as ground(P ). An (Herbrand) interpretation I is a subset of B. For a logic program P and an Herbrand interpretation I, the immediate consequence operator (or T P operator) [START_REF] Apt | Towards a theory of declarative knowledge[END_REF] is the mapping T P : 2 B → 2 B :

T P (I) = { h(R) | R ∈ ground(P ), b + (R) ⊆ I, b -(R) ∩ I = ∅}.
(

) 2
Definition 1 (Subsumption).

For two rules R 1 , R 2 of the form 1 with the same head,

R 1 subsumes R 2 if there is a substitution θ such that b + (R 1 )θ ⊆ b + (R 2 ) and b -(R 1 )θ ⊆ b -(R 2 ). When R 1 subsumes R 2 and |b(R 1 )| < |b(R 2 )|, R 1 is more general than R 2 and R 2 is more specific than R 1 .
We now review the LF1T algorithm developed in [START_REF] Inoue | Learning from interpretation transition[END_REF]. LF1T is an anytime algorithm that takes a set of state transitions E ⊆ 2 B × 2 B as input. The states transitions of E can be seen as (positive) examples/observations of transition of the system. From these transitions the algorithm learns a logic program P that represents the dynamics for E. To perform this learning process we can iteratively consider one-step transitions. In LF1T, the Herbrand base B is assumed to be finite. To construct an NLP for LF1T we can use a bottom-up method, which generates hypotheses by generalization from the most specific clauses to explain positive examples that have not been covered yet. The pseudo-code of LF1T is given in Algorithm 1. The LF1T algorithm can be used with or without an initial NLP P 0 . Given only the examples E, LF1T is initially called by LF1T(E, ∅). If an initial NLP P 0 is given, LF1T(E, P 0 ) is called. LF1T first constructs the most specific rule R I A for each positive literal A appearing in J = T P (I) for Algorithm 1 LF1T(E,P )

1: INPUT: E ⊆ 2 B × 2 B : (positive)
examples/observations and an NLP P 2: OUTPUT: An NLP P such that J = T P (I) holds for any (I, J) ∈ E.

3: while E = ∅ do 4:

Pick (I, J) ∈ E; E := E \ {(I, J)}

5:

for each A ∈ J do 6:

R I A := A ← B i ∈I Bi ∧ C j ∈(B\I) ¬Cj

7:

AddRule(R I A , P )

8: end while 9: return P each (I, J) ∈ E. We do not construct any rule to make a literal false. The rule R I A is then possibly generalized when another transition from E makes A true, which is computed by several generalization methods. The two generalization methods considered in [START_REF] Inoue | Learning from interpretation transition[END_REF] are based on resolution. In [START_REF] Inoue | Learning from interpretation transition[END_REF], naïve and ground resolutions are defined between two ground rules as follows. Let R 1 , R 2 be two ground rules and l be a literal such that

h(R 1 ) = h(R 2 ), l ∈ b(R 1 ) and l ∈ b(R 2 ). If (b(R 2 ) \ {l}) ⊆ (b(R 1 ) \ {l}) then the ground resolution of R 1 and R 2 (upon l) is defined as res(R 1 , R 2 ) = h(R 1 ) ← Li∈b(R1)\{l} L i . (3)
In particular, if

(b(R 2 ) \ {l}) = (b(R 1 ) \ {l})
then the ground resolution is called the naïve resolution of R 1 and R 2 (upon l). In this particular case, the rules R 1 and R 2 are said to be complementary to each other with respect to l. Both naïve resolution and ground resolution can be used as generalization methods of ground rules. For two ground rules R 1 and R 2 , the naïve resolution res(R 1 , R 2 ) subsumes both R 1 and R 2 , but the non-naïve ground resolution subsumes R 1 only. For example, suppose the three rules: R 1 = (p ← q ∧ r), R 2 = (p ← ¬q ∧ r), R 3 = (p ← ¬q), and their resolvent:

res(R 1 , R 2 ) = res(R 1 , R 3 ) = (p ← r)
. R 1 and R 2 are complementary with respect to q. Both R 1 and R 2 can be generalized by the naïve resolution of them because res(R 1 , R 2 ) subsumes both R 1 and R 2 . On the other hand, the ground resolution res(R 1 , R 3 ) subsumes R 1 but does not subsumes R 3 . In the first implementation of LF1T in [START_REF] Inoue | Learning from interpretation transition[END_REF], naïve resolution is used as a least generalization [START_REF] Plotkin | A note on inductive generalization[END_REF] method. This method is particularly intuitive from the ILP viewpoint, since each generalization is performed based on a least generalization operator. In [START_REF] Inoue | Learning from interpretation transition[END_REF], it is shown that for two complementary ground rules R 1 and R 2 , the naïve resolution of R 1 and R 2 is the least generalization of them, that is,

lg(R 1 , R 2 ) = res(R 1 , R 2 ).
When naïve resolution is used, LF1T needs an auxiliary set P old of rules to globally store subsumed rules, which increases monotonically. Using naïve resolution, P ∪ P old possibly contains all patterns of rules constructed from the Herbrand base B in their bodies. In the second implementation of LF1T of [START_REF] Inoue | Learning from interpretation transition[END_REF], ground resolution is used as an P old alternative generalization method in AddRule. This replacement of resolution leads to a lot of computational gains, since the use of P old is not necessary any more: all generalized rules obtained from P ∪ P old by naïve resolution can be obtained using ground resolution on P . By Theorem 3 of [START_REF] Inoue | Learning from interpretation transition[END_REF], using the naïve version, the memory use of the LF1T algorithm is bounded by O(n•3 n ), Example 1. Consider the state transition in Fig. 1. By giving the state transitions stepby-step and using ground resolution the NLP {#13, #16, #19} is obtained in Table 1, where #n is the rule ID.

Table 1. Execution of LF1T with ground resolution on step transitions of figure 1 where pqr → pq represents the state transition ({p, q, r}, {p, q}) [START_REF] Inoue | Learning from interpretation transition[END_REF].

Step

I → J Operation Rule ID P 1 pqr → pq R pqr p p ← p ∧ q ∧ r 1 1 R pqr q q ← p ∧ q ∧ r 2 1,2 2 pq → p R pq p p ← p ∧ q ∧ ¬r 3 res(3, 1) p ← p ∧ q 4 2,4 6 p → 7 → r R r r ← ¬p ∧ ¬q ∧ ¬r 5 2,4,5 8 r → r R r r r ← ¬p ∧ ¬q ∧ r 6 res(6, 5) r ← ¬p ∧ ¬q 7 2,4,7 9 qr → pr R qr p p ← ¬p ∧ q ∧ r 8 res(8, 4) p ← q ∧ r 9 4,7,9 R qr r r ← ¬p ∧ q ∧ r 10 res(10, 7) r ← ¬p ∧ r 11 2,4,7,9,11 10 pr → q R pr q q ← p ∧ ¬q ∧ r 12 res(12, 2)
q ← p ∧ r 13 4,7,9,11,13 11 q → pr R q p p ← ¬p ∧ q ∧ ¬r 14 res(14, 1) p ← q ∧ ¬r 15 res [START_REF] Bryant | Symbolic boolean manipulation with ordered binary-decision diagrams[END_REF][START_REF] Inoue | Oscillating behavior of logic programs[END_REF] p ← q 16 7,11,13,16 R q r r ← ¬p ∧ q ∧ ¬r 17 res [START_REF] Plotkin | A note on inductive generalization[END_REF][START_REF] Akers | Binary decision diagrams[END_REF] r ← ¬p ∧ ¬r 18 res [START_REF] Dubrova | A sat-based algorithm for finding attractors in synchronous boolean networks[END_REF][START_REF] De Raedt | Problog: A probabilistic prolog and its application in link discovery[END_REF] r ← ¬p 19 13,16,19 Now we present a new LF1T algorithm based on an efficient data structured inspired from OBDD and Zero-suppressed BDD. The novelty of our approach is the integration of LF1T operations into a BDD structure to perform ground resolution. In this approach, one BDD represents a set of rules that have the same head. Figure 2 show the evolution of the BDD that represents rules of p in Example 1: In this figure, the last schema of step 9 represents a BDD that contains two rules p ← p∧q and p ← q∧r which both have p as their head. The internal nodes of our data structure represent literals, and outgoing edges represent their polarity. In Figure 2, the first BDD has one root node which represents the literal p and the edge between its child node q represents the fact that p is positive in the rule p ← p ∧ q. Like an OBBD, our structure respects a total variable ordering: if p, c are two nodes, c is a child of p and l p , l c their literals respectively,then l p < l c . If there is an edge between two nodes p, c that are not neighbors in the ordering, it means that all literals between them are absent from the rules encoded by paths including p and c. Like a ZDD, our BDD structure can have multiple root nodes, but only one leaf; it only represents positive rules. A root node always represents the first literal of one or multiple rules. The leaf node represents the end of all rules; it is the unique child of the last literal of every rule represented by the BDD. Usual BDD merging operations are not sufficient to perform the generalization operations of LF1T. In LF1T, these operations are equivalent to the use of naïve resolution without P old . In Figure 2, the generalization obtained in step 2 can be obtained by usual BDD merging operations: the node r has a positive and negative link to the same node (the leaf) and should be removed according to BDD merging operations. But the generalization obtained by ground resolution on step 9 cannot be obtained by usual BDD merging operations. To use ground resolution within a BDD structure we need to introduce specific merging operations. These operations have to ensure that the set of rules represented by a BDD is always minimal regarding ground resolution. In Figure 2, the last BDD of each learning step respects this notion of minimality. Algorithm 2 describes our adaptation to BDD of the addRule operation of LF1T. This algorithm is an application to BDD of the previous version of LF1T based on ground resolution. Whenever a new rule is learned, the corresponding BDD is updated as follows: 1) check if the rule is subsumed, 2) generalize the rule, 3) remove subsumed rules, 4) insert the rule and 5) generalize the BDD. The details of each step is explained as follows.

Subsumption (step 1)

To check if a rule is subsumed by a BDD, we have to check whether starting from a root and following the body of the rules allow us to reach the leaf of the BDD. If we reach the leaf then the rule is subsumed. Because we use ground resolution, if a rule is subsumed by the BDD it is useless to search for generalizations of that rule. Checking for such a generalization will only lead to generating a rule that is already in the BDD. Also, it cannot generalize any rules in the BDD: every generalization which can be triggered by this rule has already been found using the rules in the BDD that subsumes it.

Generalization of the new rule (step 2) To search for generalizations of the rules we use a similar search. However, each time we reach a node representing the current literal l of the rule, we check if the sub-BDDs Step 1

Step 2

Step 9

Step 11 Step 1: from (pqr, pq) we learn p ← p ∧ q ∧ r.

p q q r q r 1 1 1 1 1 0 0 p q q r q 1 1 1 1 1 0 q q r 1 1 1 q 1 +#
Step 2: from (pq, p) we learn p ← p ∧ q ∧ ¬r and by resolution p ← p ∧ q.

Step 9: from (qr, pr) we learn p ← ¬p ∧ q ∧ r and by resolution p ← q ∧ r.

Step 11: from (q, pr) we learn p ← ¬p ∧ q ∧ ¬r which triggers two resolutions and a subsumtion to finish with p ← q.

Algorithm 2 addRule(R,B) return subsumes(R, n + 1)

14: literal R ← n th literal of R // 4)

23:

return true 24: return false subsume the complementary rule on l. If it is the case, we generalize the rule on this literal and restart the check for generalizations with the new rule.

Removal (step 3) To delete the rules subsumed by the new rule in the BDD, this time we start from the leaf. We follow the parents according to the rule until we check all corresponding parts of the BDD. If we reach the end of the rule, it means that a rule is subsumed. If we do not encounter a node with multiple children, we just have to delete the current node and purge the linked nodes: we recursively delete all parent nodes that have no more children and all children who have no more parents (those poor orphans). Otherwise, we come back to the first node with multiple children we encountered, cut the child edge we followed, and purge the child node in the same way as before.

Insertion (step 4) All operations we use on our BDDs are based on the manner in which we insert a rule into the structure. First of all, when adding a rule R to a BDD B we assume that R does not subsumes and is not subsumed by any rules of B and cannot be generalized by a rule of B using ground resolution (insured by step 1-3). To add a rule in the BDD we start by searching the common part of the beginning and the end of the body. From the leaf of the BDD, we climb to its parents following the rule from the end. If a parent node has multiple children we do not follow it. Adding a parent to this node will generate more rules than only the one we want to represent. We stop when there is no parent that corresponds to the literal of the rule or when we reach the beginning of the rule. Let's call the last parent reached last and its literal l last ; last will be connected later to the

28:

return true 29: return false new nodes created to represent the rule. Then, we search for a root node corresponding to the first literal. If such a root node does not exist, we create a new one, and then we create and link new nodes for all literals l < l last of the rules. Then, last becomes the child of the node most recently created. If a root node corresponds to the first literal of the rule to insert, we follow its children according to the rule body. We stop the descent when no nodes correspond to the rule body, and connect the most recent one we found to last. This insertion policy allows us to compile common parts of the rule body to save memory space. It ensures that a node with multiple children have only one parent and cannot have an ancestor with multiple ancestors. In our implementation, this property is exploited to enhance the efficiency of the subsumption and generalization checks of LF1T.

Generalization of BDDs (step 5) To search the generalizations made by the new rule, we start from the root node. Let l be the current literal we are checking in the rule. When we reach a node whose literal corresponds to l or before it in the ordering, we just have to retrieve all rules subsumed by the rest of the new rules. These rules can all be generalized on the current node. We continue the search for generalizations on the children until we cannot follow the rule anymore. It is necessary to clear the BDD from subsumed rules before this operation in order to avoid a cascade of useless generalizations which lead to the rule we are inserting. In fact, let R 1 , R 2 be two rules such that R 1 subsumes R 2 on l. Then R 1 can generalize R 2 on l because R 1 subsumes the complementary of R 2 on l.

can cut ← f alse // 2)
Theorem 1. Let n be the size of the Herbrand base |B|. Using our dedicated BDD structure the memory complexity as well as the computational complexity of LF1T remain in the same order as the previous algorithm based on ground resolution: , i.e., O(2 n ) and O(4 n ), respectively. The proof is given as appendix. In this section, we evaluate our learning methods through experiments. We apply our new LF1T algorithms to learn Boolean networks. Here we run our learning program on the same benchmarks used in [START_REF] Inoue | Learning from interpretation transition[END_REF]. These benchmarks are Boolean networks taken from Dubrova and Teslenko [START_REF] Dubrova | A sat-based algorithm for finding attractors in synchronous boolean networks[END_REF], which include those networks for control of flower morphogenesis in Arabidopsis thaliana, budding yeast cell cycle regulation, fission yeast cell cycle regulation and mammalian cell cycle regulation. Like in [START_REF] Inoue | Learning from interpretation transition[END_REF], we first construct an NLP τ (N ) from the Boolean function of a Boolean network N where each Boolean function is transformed to a DNF formula. Then, we get all possible 1-step state transitions of N from all 2 |B| possible initial states I 0 's by computing all stable models of τ (N ) ∪ I 0 using the answer set solver clasp [START_REF] Gebser | Answer Set Solving in Practice[END_REF]. Finally, we use this set of state transitions to learn an NLP using our LF1T algorithm. Because a run of LF1T returns an NLP which can contain redundant rules, the original NLP P org and the output NLP P LFIT can be different, but remain equivalent with respect to state transition, that is, T Porg and T PLFIT are identical functions. Table 2 shows the memory space and time of a single LF1T run in learning a Boolean network for each problem in [START_REF] Dubrova | A sat-based algorithm for finding attractors in synchronous boolean networks[END_REF] on a processor Intel Core I7 (3610QM, 2.3GHz) with 4GB of RAM. In the naïve, ground and BDD versions of LF1T the variable ordering is alphabetical. The time limit is set to one hour for each experiment. The gain of memory for the BDD version is up to 50% for the two smaller benchmarks and around 20% for the bigger ones. The main interest of our algorithm is shown by the gain in CPU time. For the Arabidopsis thaliana benchmark the input size is quite big: 2 15 state transitions. Here, naïve version of LF1T reaches the time out (T.O.) of one hour. On this big benchmark, using BDD, we need 80% less CPU time than the previous ground resolution method. These results show that even if the BDD structure does not have a big impact on the whole memory space use, its particular structure allows it to perform LF1T operations faster than in the previous algorithms.

Table 3 show more precise experimental results on the BDD version of LF1T. This table shows the minimimum, maximum and average number of rules in the output NLP of 1000 runs of LF1T with random variable ordering. The fifth column shows the average learning time and last one is the standard deviation over the number of rules and the one of learning time.

The standard deviation shows that the impact of variable ordering does not affect learning time very much, but it has a significant influence on the rules learned by LF1T. Although those output rules are all minimal with respect to subsumption among them, some are subsumed by original rules. If we consider the original NLP as a kind of optimal NLP in terms of the number of rules, the bigger NLPs learned by our BDD version are local optima where no ground resolutions can be applied among the rules of the NLP. This is because the resolution strategy of LF1T is to perform resolution only when it produces a generalized rule, so other kinds of resolution are not allowed. For example, from R 1 = (p ← p ∧ q) and R 2 = (p ← ¬q ∧ r), R = (p ← p ∧ r) cannot be obtained in LF1T, since R subsumes neither R 1 nor R 2 . Variable ordering has the same affect on the previous versions of LF1T.

Conclusion & Future Work

We proposed a new algorithm for learning from interpretation transitions based on a BDD-like structure. Using this data structure, we can reduce the memory space to represent NLPs learned by LF1T. Analysis of the worst-case computational complexity demonstrated that learning with this method is equivalent to the previous method. However, experimental comparison with previous LF1T algorithms showed that our method outperforms them in practice. Just a few remarks on learning non-ground NLPs; LF1T first learns ground rules then we apply well-known generalization techniques like antiinstantiation and least generalization. Extension of the BDD structure in this paper to the first-order case like [START_REF] Groote | Binary decision diagrams for first-order predicate logic[END_REF] remains as a future work. Another possible outlook is an extension of LF1T algorithm to learn the dynamics of asynchronous systems.

Fig. 1 .

 1 Fig. 1. A Boolean network N1(left) and its state transition diagram (right)

  if r.generalizes(R, 0) then restart the for loop // 3) Remove rules subsumed by R 7: l := the leaf node of B 8: l.clear(R, |R|, true) // 4) Insert R into the BDD 9: insert(R, B) // 5.1) Check generalization by R 10: g ← ∅ 11: for each root node r of B do 12: r.generalizations(R, 1, g) // 5.2) Add the generalizations generated by R 13: for each rules Rg of g do 14: addRule(Rg) Algorithm 3 subsumes(R, n) member function of a LF1T-BDD node N 1: INPUT: a rule R and an integer n 2: OUTPUT: a Boolean value 3: literal N : literal of the node N 4: true children: list of child nodes linked by a true edge 5: f alse children: list of child nodes linked by a false edge 6: head: the head literal of R // 1) Terminal node 7: if is terminal() AND variable = head then 8: return true // 2) End of the rule 9: if n > |R| then 10: return false 11: literal R ← n th literal of R // 3) LF1T-BDD rules are more generals 12: if literal R > literal N then 13:

Algorithm 4

 4 generalizes(R, n) member function of a LF1T-BDD node N 1: INPUT: a rule R and an integer n 2: OUTPUT: a Boolean value 3: literal N : literal of the node N 4: true children: list of child nodes linked by a true edge 5: f alse children: list of child nodes linked by a false edge // 1) The rule is more general than all rules of the node 6: if n > |R| then return false // 2) Terminal node 7: if is terminal() then return false // 3) Check generalization on the current node 8: literal R ← n th literal of R // 3.1) The node is more general than the rule 9: while literal N > literal R do 10: if subsumes(R, n) then 11: R ← R \ literal R // 3.1.1) The node subsumes the complementary rule 12: return true 13: n ← n + 1 // 3.1.2) No more literal to generalize 14: if n > |R| then return false 15: end while // 3.2) The rule is more general 16: if literal N < literal R then return false // 3.3) The sub-bdd possibly contains the complementary 17: same ← true children 18: oposite ← f alse children 19: if literal R is positive then 20: same ← f alse children 21: oposite ← true children // 3.3.1) Search for complementary rules 22: for each child node c of oposite do 23: if c.subsumes(R, n + 1) then // Complementary rules is subsumed 24: R ← R \ literal R 25: return true // 4) Search for generalizations on next literal 26: for each child node c of same do 27: if c.generalizes(R, n + 1) then

Algorithm 5

 5 clear(R, n, can cut) member function of a LF1T-BDD node N 1: INPUT: R a rule, n an integer and can cut a Boolean 2: OUTPUT: a Boolean value 3: literal R : the n th literal of R 4: unlink ← f alse // 1) Choice node 5: if #child > 1 then 6:

Algorithm 6

 6 insert(R, BDD) 1: INPUT: a rule R and a BDD 2: starting: the set of starting nodes of BDD 3: literal: first literal of R 4: begin, end: BDD nodes 5: n ← 0 6: push ← f alse // 1) Bottom-up search for common part 7: end ← the last ancestor node reached following R from the corresponding terminal node // 2) Fact rule 8: if |R| = 0 then 9: starting ← {terminalnode} 10: begin ← N U LL // 2.1) Search common literal within the starting nodes 11: if a node r ∈ starting correspond to literal then 12: begin ← r // 2.2) New starting 13: if begin = N U LL then 14: begin ← a new node corresponding to literal 15: starting ← starting ∪ {begin} 16: push ← true 17: current: bdd node pointer 18: make current points on begin // 3) Insertion of the rest of the body 19: while n ≤ |R| do 20: n ← n + 1 // 3.1) Link node reached 21: if n > |R| OR the n th literal of R is the one of end then 22: connect current to end according to the polarity of literal 23: return 24: literal ← n th literal of R // 3.2) construct new nodes for the rest of the rule 25: if push then 26: create a new node for literal 27: connect the node to current according to the polarity of literal 28: make current points on the new node 29: CONTINUE // 3.3) Continue to follow the rule 30: next ← N U LL 31: for each child nodes c of current according to previous literal polarity do 32: if c has only one parent node AND correspond to literal then 33: 4) // Continue to follow the LF1T-BDD 39: Make current point on next 40: end while 41: Connect end to begin according to the polarity of literal

  The rule is more general 15: if literal R < literal N then 16:

		return false
		// 5) Same literal
	17: if literal R is positive then
	18:	children ← true children
	19: else
	20:

children ← f alse children 21: for each child node c of children do 22: if c.subsumes(R, n + 1) then

Table 2 .

 2 Memory use and learning time of LF1T for Boolean networks up to 15 nodes with the alphabetical variable ordering

	Name	# nodes # rules Naïve	Ground	BDD
	Arabidopsis thalania 15	28	T.O.	40.8MB/13.8s 31.6MB/2.8s
	Budding yeast	12	54 11MB/361s 4.6MB/0.82s 3.6MB/0.188s
	Fission yeast	10	23 3.3MB/5.2s 0.8MB/0.68s 0.5MB/0.24s
	Mammalian cell	10	22 4.7MB/5.7s 1MB/0.76s 0.5MB/0.24s

Table 3 .

 3 Experimental results of 1000 runs of LF1T with random variable orderings

	Name	min/max # rules Average # rules time std deviation rules/time
	Arabidopsis thalania	29/962	227	4.31s	183.03/0.538s
	Budding yeast	54/310	82	0.3s	41.91/0.019s
	Fission yeast	23/45	24	0.04s	3.08/0.003s
	Mammalian cell	22/22	22	0.03s	0/0.007s

This research was supported in part by the NII research project on "Dynamic Constraint Networks" and by the "Systems Resilience" project at Research Organization of Information and Systems, Japan. We would like to thank Earl Belinger for its help to improve the english quality of the paper.

33:

for each rule r of G do 34:

Proof Let n be the size of the Herbrand base |B|. This n is also the number of possible heads of rules. Furthermore, n is also the maximum size of a rule, i.e. the number of literals in the body; a literal can appear at most one time in the body of a rule. For each head there are 3 n possible bodies: each literal can either be positive, negative or absent of the body. From these preliminaries we conclude that the size of an NLP |P | learned by LF1T is at most n • 3 n . But thanks to ground resolution, |P | cannot exceed n • 2 n ; in the worst case, P contains only rules of size n where all literals appear and there is only n • 2 n such rules. If P contains a rule with m literals (m < n), this rule subsumes 2 n-m rules which cannot appear in P . Finally, ground resolution also ensures that P does not contain any pair of complementary rules, so that the complexity is further divided by n;

In our approach, a BDD represents all rules of P that have the same head, so that we have n BDD structures. When |P | = 2 n , each BDD represents 2 n /n rules of size n and are bound by O(2 n /n), which is the upper bound size of a BDD for any Boolean function [START_REF] Liaw | On the obdd-representation of general boolean functions[END_REF]. Because BDD merges common parts of rules, it is possible that a BDD that represents 2 n /n rules needs less than 2 n /n memory space. In the previous approach, in the worst case |P | = 2 n , whereas in our approach |P | ≤ 2 n . Our new algorithm still remains in the same order of complexity regarding memory size: O(2 n ).

Regarding learning, each operation has its own complexity. Let k be the place of a literal in the variable ordering so that for the starting node literal of a BDD k = 0. In our BDD, a node has at most 2 • ((n -k) -1) children: (n -k) -1 positive and negative links to all literals which are superior to k in the ordering. Insertion of a rule is done in polynomial time; in the worst case, we insert a rule where only one literal that differs from the BDD. Because we follow only the first common literals, we have to check at most 2 • ((n -k) -1) links on n -1 nodes, which belongs to O(n 2 ).

Subsumption as well as generalization checks require exponential time. In the case of subsumption, in the worst case the BDD contains 2 n /n rules and the rule is not subsumed by any of them.

That means that we have to check every rule, and each check belongs to O(n 2 ) so that the whole subsumption operation belongs to

To clear the BDD we have to perform the inverse operation. We always have to check the whole BDD, so if the size of the BDD is 2 n then the complexity of the whole clear check also belongs to O(2 n ).

To generalize the new rule we have to check if the BDD subsumes one of its complementary rules. Like for subsumption, in the worst case we have to check every rule. A rule can be generalized at most n times; for each generalization we have to check at most n complementary rules, so the complexity of a complete generalization belongs to O(n 2 • 2 n /n) = O(2 n ). For the complexity of generalization of BDD rules we consider the inverse problem. In the worst case, every rule of the BDD can be generalized by the new one. Because the new rule does not cover any rules of the BDD, it can generalize each rule of the BDD at most one time. Then, we have at most 2 n /n possible direct generalizations on the whole BDD. In the worst case, each of them can be generalized at most n -1 times, and like before, for each generalization we have to check at most n complementary rules. If a rule is generalized n times it means that its body becomes empty, i.e. the rule is a fact, and it will subsume and clear the whole BDD. Then, the complexity of a complete generalization of the BDD belongs to

Each time we learn a rule from a step transition we have to perform these four checks which have a complexity of O(n 2 + 2 n + 2 n + 2 n ) = O(2 n ). From 2 n state transitions, LF1T can directly infer n • 2 n rules. Learning the dynamics of the entire input implies in the worst case 2 n • 2 n operations which belong to O(4 n ). Using our dedicated BDD structure the memory complexity as well as the computational complexity of LF1T remains the same order as the previous algorithm based on ground resolution: respectively O(2 n ) and O(4 n ).


Stéphane Gaïffas

Uniform estimation of a signal based on inhomogeneous data

Keywords: nonparametric regression, adaptive estimation, minimax theory, random design

come

Uniform estimation of a signal based on inhomogeneous data

Introduction

Motivations. A problem particularly prominent in statistical literature is the adaptive reconstruction of a signal based on irregularly sampled noisy data. In several practical situations, the statistician cannot obtain "nice" regularly sampled observations, because of various constraints linked with the source of the data, or the way the data is obtained. For instance, in signal or image processing, the irregular sampling can be due to the process of motion or disparity compensation (used in advanced video processing), while in topography, measurement constraints are linked with the properties of the ground. See Feichtinger and Gröchenig (1994) for a survey on irregular sampling, [START_REF] Almansa | Irregular sampling in satellite images and reconstruction algorithms[END_REF], [START_REF] Vàzquez | Wavelet-based reconstruction of irregularly-sampled images: application to stereo imaging[END_REF] for applications concerning respectively satellite image and stereo imaging, and [START_REF] Jansen | Multivariate nonparametric regression using lifting[END_REF] for examples of geographical constraints.

Such constraints can result in a lack of data, that can be locally very strong. As a consequence, the accuracy of a procedure based on such data can become very poor locally.

The aim of the paper is to study from a theoretical point of view the consequences of the inhomogeneity of the data on the reconstruction of a univariate signal. Natural questions arise: how does the inhomogeneity impact on the accuracy of estimation? What does the optimal convergence rate become in such situations? Can the rate vary strongly from one point to another, and how?

The model. The widest spread way to model such observations is as follows. We model the available data [(X i , Y i ); 1 i n] by

Y i = f (X i ) + σξ i , (1)
where ξ i are i.i.d. Gaussian standard and independent of the X i 's and where σ > 0 is the noise level. The design variables X i are i.i.d. with density µ with respect to the Lesbesgue measure. The density µ is unknown to the statistician, and for simplicity, we assume that its suppport is [0, 1]. The more the density µ is "far" from the uniform law, the more the data drawn from (1) is inhomogeneous. A simple way to include situations with local lacks of data within the model ( 1) is to allow the density µ to be vanishing at some points. This kind of behaviour is not commonly used in literature, since most papers assume µ to be uniformly bounded away from zero. Below, we give references where this kind of design is handled.

In practice, we don't know µ, since it requires to know in a precise way the constraints making the observation irregularly sampled, neither do we know the smoothness of f . Therefore, a convenient procedure shall adapt both to the design and to the smoothness of f . Such a procedure (that is proved to be optimal) is constructed here.

Methodology. We want to reconstruct f globally with sup norm loss. The choice of sup norm for measuring the error of estimation is crucial for the study conducted here. Indeed, it appears that it allows to capture in a very simple way the consequences of inhomogeneity directly on the convergence rate: when the data is inhomogeneous, the optimal rate is deformed (in comparison with the usual rate), see Theorem 1 and 2 in Section 2.

The sup norm choice leads to a particular adaptive estimation method, that can handle "very" inhomogeneous design. This method involves an interpolation transform, where the scaling coefficients are estimated by local polynomials with a smoothing parameter selected by a Lepski type procedure, see for instance Lepski et al. (1997). The Lepski type procedure developed here is adapted to the random design setting, when the design law is unknown.

Note that the original adaptive method from Lepski, see for instance [START_REF] Lepski | On a problem of adaptive estimation in Gaussian white noise[END_REF], was developed only in the Gaussian white noise model, which is an idealized version of (1) when the design is uniform: see for instance [START_REF] Brown | Asymptotic equivalence of nonparametric regression and white noise[END_REF] and [START_REF] Brown | Asymptotic equivalence theory for nonparametric regression with random design[END_REF].

If we measure the error of estimation with L 2 -norm, which is more standard in nonparametric literature, the phenomenon of deformation of the rate does not occur: see for instance the results from [START_REF] Chesneau | Regression with random design: A minimax study[END_REF], which includes design densities that can vanish. Moreover, in L 2 estimation, more standard tools shall be used, like orthogonal series, splines, or wavelets, see for instance [START_REF] Green | Nonparametric regression and generalized linear models[END_REF], [START_REF] Efromovich | Nonparametric curve estimation[END_REF] and [START_REF] Härdle | Wavelets, approximation, and statistical applications[END_REF].

Literature. Pointwise estimation at a point where the design vanishes is studied in [START_REF] Hall | Curve estimation when the design density is low[END_REF], with the use of a local linear procedure. This design behaviour is given as an example in [START_REF] Guerre | Efficient random rates for nonparametric regression under arbitrary designs[END_REF], where a more general setting for the design is considered, with a Lipschitz regression function. In Gaïffas (2005a), pointwise minimax rates over Hölder classes are computed for several design behaviours, and an adaptive estimator for the pointwise risk is constructed in [START_REF] Gaïffas | On pointwise adaptive curve estimation based on inhomogeneous data[END_REF]. In these papers, it appears that, depending on the design behaviour at the estimation point, the range of minimax rates is very wide: from very slow (logarithmic) rates to very fast quasi-parametric rates. Many adaptive techniques have been developed in literature for handling irregularly sampled data. Among wavelet methods, see [START_REF] Hall | Curve estimation when the design density is low[END_REF] for interpolation; [START_REF] Antoniadis | Random design wavelet curve smoothing[END_REF], [START_REF] Antoniadis | Wavelet regression for random or irregular design[END_REF], [START_REF] Brown | Wavelet shrinkage for nonequispaced samples[END_REF], [START_REF] Hall | A note on design transformation and binning in nonparametric curve estimation[END_REF] and [START_REF] Wong | Wavelet threshold estimation of a regression function with random design[END_REF] for tranformation and binning; [START_REF] Antoniadis | Regularization of wavelet approximations[END_REF] for a penalization approach; [START_REF] Delouille | Nonparametric stochastic regression with designadapted wavelets[END_REF] and [START_REF] Delouille | Smooth design-adapted wavelets for nonparametric stochastic regression[END_REF] for the construction of design-adapted wavelet via lifting; [START_REF] Pensky | On non-equally spaced wavelet regression[END_REF] for projection-based techniques; [START_REF] Kerkyacharian | Regression in random design and warped wavelets[END_REF] for warped wavelets. For model selection, see [START_REF] Baraud | Model selection for regression on a random design[END_REF]. See also the PhD manuscripts from [START_REF] Maxim | Restauration de signaux bruités sur des plans d'experience aléatoires[END_REF] and [START_REF] Delouille | Nonparametric stochastic regression using design-adapted wavelets[END_REF].

Results

To measure the smoothness of f , we consider the standard Hölder class H(s, L), where s, L > 0, which is defined as the set of all the functions f :

[0, 1] → R such that |f (⌊s⌋) (x) -f (⌊s⌋) (y)| L|x -y| s-⌊s⌋ , ∀x, y ∈ [0, 1],
where ⌊s⌋ is the largest integer smaller than s. Minimax theory over such classes is standard:

we know from [START_REF] Stone | Optimal global rates of convergence for nonparametric regression[END_REF] that in model ( 1), the minimax rate is equal to (log n/n) s/(2s+1) over H(s, L) whenever µ is continuous and uniformly bounded away from zero.

We use the notation µ(I) := I µ(t)dt. We recall that µ is the common density of the X i (wrt the Lebesgue measure). If F = H(s, L) is fixed, we consider the sequence of positive

curves h n (•) = h n (•; F, µ) satisfying Lh n (x) s = σ log n nµ([x -h n (x), x + h n (x)]) 1/2
(2) for all x ∈ [0, 1], and we define

r n (x; F, µ) := Lh n (x; F, µ) s . Since h → h 2s µ([x -h, x + h]
) is increasing for any x, these curves are well-defined (for n large enough) and unique.

In Theorem 1 below, we show that r n (•) = r n (•; F, µ) is an upper bound over F . This spatially-dependent rate is achievable by an adaptive estimator, over a whole family of Hölder classes. In Theorem 2 below, we prove that, in some sense, this rate is optimal. In the next example, we give an explicit example of such a spatially-dependent rate.

Example. When s = 1, σ = L = 1 and µ(x) = 4|x-1/2|1 [0,1] (x)
, the solution to Equation ( 2) can be written as

r n (x) = (log n/n) αn(x) , where α n (x) =                    1 3 1 -log(1-2x) log(log n/n) when x ∈ 0, 1 2 -( log n 2n ) 1/4 , log ((x-1/2) 4 +4 log n/n) 1/2 -(x-1/2) 2 -log 2 2 log(log n/n) when x ∈ 1 2 -( log n 2n ) 1/4 , 1 2 + ( log n 2n ) 1/4 , 1 3 1 -log(2x-1) log(log n/n) when x ∈ 1 2 + ( log n 2n ) 1/4 , 1 .
In this example, the amount of data is low at the middle of the unit interval. The consequence is that the convergence rate has two "regimes". Indeed, r n (1/2) = (log n/n) 1/4 is slower than the rate at the boundaries r n (0) = r n (1) = (log n/n) 1/3 , which comes from the standard minimax rate (log n/n) s/(2s+1) with s = 1. Hence, in this example, r n (•) switches from one "regime" to another. In view of Theorem 2 below, we know that, in some sense, this phenomenon is unavoidable. We show the shape of this deformed rate for several sample sizes in Figure 1. Let E f µ denotes the expectation with respect to the joint law

P f µ of [(X i , Y i ); 1 i n].
Let w(•) be a loss function, namely a non-negative and non-decreasing function such that w(0) = 0 and w(x) A(1

+ |x| b ) for some A, b > 0. If Q > 0, we define H Q (s, L) := H(s, L) ∩ {f | f ∞ Q} (the constant Q needs not to be known). Let R be a fixed natural integer.
Upper bound. In this section, we show that the spatially-dependent rate r n (•) defined by ( 2) is an upper bound over Hölder classes. Let us consider the following Assumption D. We assume that µ is continuous, and that whether µ(x) > 0 for any x, or µ(x) = 0 for a finite number of x. Moreover, for any x such that µ(x) = 0, we assume that there exists β(x) 0 such that µ(y) = |y -x| β(x) for any y in a neighbourhood of x.

Theorem 1. Let us assume that the density µ satisfies Assumption D. Then, for any F = H Q (s, L) where s ∈ (0, R + 1], the estimator f n given by (11) satisfies

sup f ∈F E f µ w( sup x∈[0,1] r n (x) -1 | f n (x) -f (x)|) C (3)
as n → +∞, where r n (•) = r n (•; F, µ) is given by (2) and where C > 0 is a fixed constant, depending on the paremeters R, L, Q, w(•).

This theorem assesses the estimator f n (constructed in Section 3 below) over function sets F in a family of Hölder classes. This estimator is smoothness adaptive, since it converges with the spatially-dependent rate r n (•, F, µ) uniformly over F , which is the optimal rate in view of Theorem 2 below. Moreover, this estimator is also "design-adaptive", since it does not depend within its construction on the design density (which is unknown to the statistician).

Remark. Within Theorem 1, there are two situations:

• µ(x) > 0 for any x: we have r n (x) ≍ (log n/n) s/(2s+1) for any x, which is the standard minimax rate over H(s, L) (a n ≍ b n means a n b n and b n a n ). However, this result is new since adaptive estimators over Hölder balls in regression with random design were not previously constructed.

• µ(x) = 0 for one or several x: the rate r n (•) can vary strongly, depending on the behaviour of µ. For instance, in the example below, r n (•) changes in order from one point to another, from (log n/n) 1/4 up to (log n/n) 1/3 .

Remark. For the statement of Theorem 1, we need to assume that f ∞ Q for some Q > 0 (unknown to the statistician). This assumption is necessary, since the upper bound is uniform over Hölder classes, for the sup norm risk.

Remark. Implicitly, we assumed in Theorem 1 that s ∈ (0, R + 1], where R is a known parameter. Indeed, in the minimax framework considered here, the fact of knowing an upper bound for the smoothness s is usual in the study of adaptive methods.

Optimality of r n (•). We have seen that the rate r n (•) defined by ( 2) is an upper bound over Hölder classes, see Theorem 1. In Theorem 2 below, we prove that this rate is indeed optimal. In order to show that r n (•) is optimal in the minimax sense over some class F , the classical criterion consists in showing that for some constant

C > 0, inf b fn sup f ∈F E f µ w( sup x∈[0,1] r n (x) -1 | f n (x) -f (x)|) C, (4)
where the infimum is taken among all estimators based on the observations (1). However, this criterion does not exclude the existence of another normalisation ρ n (•) that can improve 4) roughly consists in a minoration of the uniform risk over the whole unit interval and then, only over some particular points. Therefore, we need a new criterion that strengthens the usual minimax one to prove the optimality of r n (•). The idea is simple: we localize (4) by replacing the supremum over [0, 1] by a supremum over any (small) inverval

r n (•) in some regions of [0, 1]. Indeed, (
I n ⊂ [0, 1], that is inf b fn sup f ∈F E f µ w( sup x∈In r n (x) -1 | f n (x) -f (x)|) C, ∀I n . (5)
It is noteworthy that in (5), the length of the intervals cannot be arbitrarily small. Actually, if an interval I n has a length smaller than a given limit, (5) does not hold anymore. Indeed, beyond this limit, we can improve r n (•) for the risk localized over I n : we can construct an

estimator f n such that sup f ∈F E f µ w( sup x∈In r n (x) -1 | f n (x) -f (x)|) = o(1), (6)
see Proposition 1 below. The phenomenon described in this section, which concerns the uniform risk, is related to the results from [START_REF] Cai | Nonparametric estimation over shrinking neighborhoods: superefficiency and adaptation[END_REF] for shrunk L 2 risks. In what follows, |I| stands for the length of an interval I. We recall that we use the notation

µ(I) = I µ(x)dx.
Theorem 2. Suppose that

µ(I) |I| β+1 (7)
uniformly for any interval I ⊂ [0, 1], where β 0 and let F = H(s, L). Then, for any interval

I n ⊂ [0, 1] such that |I n | ∼ n -α (8)
with α ∈ (0, (1 + 2s + β) -1 ), we have

inf b fn sup f ∈F E f µ w sup x∈In r n (x) -1 | f n (x) -f (x)| C (9) as n → +∞, where r n (•) = r n (• ; F, µ) is given by (2). Corollary 1. If v n (•) is an upper bound over F = H(s, L) in the sense of (3), we have sup x∈In v n (x)/r n (x) C
for any interval I n as in Theorem 2. Hence, r n (•) cannot be improved uniformly over an interval with length n ε-1/(1+2s+β) , for any arbitrarily small ε > 0.

Proposition 1. Let F = H Q (s, L) and ℓ n be a positive sequence satisfying log

ℓ n = o(log n). a) Let µ be such that 0 < µ(x) < +∞ for any x ∈ [0, 1]. If I n is an interval satisfying |I n | ∼ (ℓ n /n) 1/(1+2s) ,
we can contruct an estimator f n such that

sup f ∈F E f µ w n log n s/(2s+1) sup x∈In | f n (x) -f (x)| = o(1). b) Let µ(x 0 ) = 0 for some x 0 ∈ [0, 1] and µ([x 0 -h, x 0 + h]) = h β+1 where β 0 for any h in a fixed neighbourhood of 0. If I n = [x 0 -(ℓ n /n) 1/(1+2s+β) , x 0 + (ℓ n /n) 1/(1+2s+β) ],
we can contruct an estimator f n such that

sup f ∈F E f µ w( sup x∈In r n (x) -1 | f n (x) -f (x)|) = o(1).
Remark. Note that in case a), r n (x) ≍ (log n/n) s/(2s+1) for any x ∈ [0, 1] and that (7) holds with β = 0. This proposition entails that r n (•) can be improved for localized risks (6) over intervals 1+2s+β) where ℓ n can be a slow term such has (log n) γ for any γ 0.

I n with size (ℓ n /n) 1/(
A consequence is that the lower bound in Theorem 2 cannot be improved, since (9) does not hold anymore when I n has a length smaller than (8). This phenomenon is linked both to the choice of the uniform metric for measuring the error of estimation, and to the nature of the noise within the model (1). It is also a consequence of the minimax paradigm: it is well-known that the minimax risk actually concentrates on some critical functions of the considered class (that we rescale and place within I n here, hence the critical length for I n ), which is a property allowing to prove lower bounds such as the one in Theorem 2.

Construction of an adaptive estimator

The adaptive method proposed here differs from the techniques mentioned in Introduction. Indeed, it is not appropriate to apply a wavelet decomposition of the scaling coefficients at the finest scale here, since it is a L 2 -transform, while the criterion (3) considered here uses the uniform metric. This is the reason why here, the analysis is focused on a precise estimation of the scaling coefficients. Each scaling coefficient is estimated by a local polynomial estimator (LPE) of f with an adaptively selected bandwidth.

Let (V j ) j 0 be a multiresolution analysis of L 2 ([0, 1]) with a scaling function φ compactly supported and R-regular (the parameter R comes from Theorem 1), which ensures that

f -P j f ∞ 2 -js (10)
for any f ∈ H(s, L) with s ∈ (0, R + 1], where P j denotes the projection onto V j . We use P j as an interpolation transform. Interpolation transforms in the unit interval are constructed in [START_REF] Donoho | Interpolating wavelet tranforms[END_REF] and [START_REF] Cohen | Wavelets on the interval and fast wavelets transforms[END_REF]. We have

P j f = 2 j -1
k=0 α jk φ jk , where φ jk (•) = 2 j/2 φ(2 j • -k) and α jk = f φ jk . We consider the largest integer J such that

N := 2 J
n, and we estimate the scaling coefficients (α jk ) 0 k 2 j at the high resolution level j = J. If α Jk are estimators of α Jk , we simply consider

f n := 2 J -1 k=0 α Jk φ Jk . (11)
Let us denote by Pol R the set of all real polynomials with degree at most R. Suppose for the moment that we are given some accurate estimators fk ∈ Pol R of f over the support of φ Jk . Then α Jk = f φ Jk ≈ fk φ Jk . In the particular situation where the scaling function

φ has R moments, that is φ(t)t p dt = 1 p=0 , p ∈ {0, . . . , R}, (12)
and when f is s-Hölder for s ∈ (0, R + 1], accurate estimators of α Jk are given by the statistic

α Jk := 2 -J/2 fk (k2 -J ). ( 13
)
This comes from the fact that when f ∈ H(s, L), we have

f φ Jk ≈ f k φ Jk = 2 -J/2 f (k2 -J ),
where f k is the Taylor expansion of f at k2 -J up to the order ⌊s⌋. If φ does not satisfies ( 12), fk φ Jk can be computed exactly using a quadrature formula, in the same way as in [START_REF] Delyon | Estimating wavelet coefficients[END_REF]. Indeed, there is a matrix Q J (characterized by φ) with entries (q Jkm ) for (k, m) ∈ {0, . . . , 2 J -1} 2 such that

P φ Jk = 2 -J/2 m∈Γ Jk q Jkm P (m/2 J ) (14)
for any P ∈ Pol R . Within this equation, the entries of the quadrature matrix Q J satisfy

q Jkm = 0 → |k -m| L φ and m ∈ Γ Jk , (15)
where L φ > 0 is the support length of φ (the matrix Q J is band-limited). For instance, if we consider the Coiflets basis, which satisfies the moment condition (12), we have q Jkm = 1 k=m , and we can use directly ( 13). If the (φ(• -k)) k are orthogonal, then q Jkm = φ(m -k), see [START_REF] Delyon | Estimating wavelet coefficients[END_REF].

For the sake of simplicity, we assume in what follows that φ satisfies the moment condition ( 12), thus the coefficients α Jk are estimated by ( 13). Each polynomial fk in ( 13) is a local polynomial estimator computed at k2 -J with smoothing parameter ∆ k (the socalled "bandwidth", which is, here, an interval included in [0, 1] containing the point k2 -J ).

Hence, we write fk = f ( b

∆ k ) k
. The smoothing parameters ∆ k are selected via an adaptive rule. Below, we describe the computation of the local polynomial estimators and we define the selection rule for the ∆ k .

Local polynomials. The polynomials used to estimate each scaling coefficients are defined via a slightly modified version of the local polynomial estimator (LPE). This linear method of estimation is standard, see for instance Fan andGijbels (1995, 1996), among many others.

For any interval δ ⊂ [0, 1], we define the empirical sample measure μn (δ) := 1 n n i=1 1 X i ∈δ , where 1 X i ∈δ equals one if X i ∈ δ, and zero otherwise. If μn (δ) > 0, we introduce the pseudo-inner product

f , g δ := 1 μn (δ) δ f g dμ n , (16)
and g δ := g , g 1/2 δ the corresponding pseudo-norm. A local polynomial estimator is computed for each point of the regular grid {k2 -J ; 0 k 2 J }. Let δ be an interval containing k2 -J . The standard LPE at k2 -J is defined as the polynomial f (δ) k of degree R which is the closest to the data in the least square sense, with respect to the localized

empirical norm • δ . More precisely, if ϕ kp (•) := (• -k2 -J ) p , 0 p R, we look for f (δ) k ∈ Span{ϕ kp (•); 0 p R} satisfying f (δ) k , ϕ δ = Y , ϕ δ (17)
for any ϕ(•) ∈ {ϕ kp (•); 0 p R}. The coefficients vector θ(δ) k ∈ R R+1 of the polynomial f (δ) k is therefore solution, when it makes sense, to the linear system

X (δ) k θ = Y (δ)
k , where for 0 p, q R:

(X (δ) k ) p,q := ϕ kp , ϕ kq δ and (Y (δ) k ) p := Y , ϕ kp δ . ( 18
)
This is the standard definition of the LPE. Moreover, whenever μn (δ) = 0, we simply take f (δ) k = 0. We modify this linear system as follows: when the smallest eigenvalue of X (δ) k

(which is non-negative) is too small, we add a correcting term allowing to bound it from below. We introduce

X(δ) k := X (δ) k + (nμ n (δ)) -1/2 Id R+1 1 Ω k (δ) ∁ , where Id R+1 is the identity matrix in R R+1 and Ω k (δ) := λ(X (δ) k ) > (nμ n (δ)) -1/2 , (19)
where λ(M ) stands for the smallest eigenvalue of a matrix M . The quantity (nμ n (δ)) -1/2 comes from the variance of f (δ) k , and this particular choice preserves the convergence rate of the method. This modification of the classical LPE is convenient in situations with little data. Below is a precise definition of the LPE at k2 -J that we consider here.

Definition 1. When μn (δ) > 0, we consider the solution θ(δ) k of the linear system

X(δ) k θ = Y (δ) k , (20)
and we introduce

f (δ) k (x) := ( θ(δ) k ) 0 + ( θ(δ) k ) 1 (x -k2 -J ) + • • • + ( θ(δ) k ) R (x -k2 -J ) R . When μn (δ) = 0, we take simply f (δ) k := 0.
Adaptive bandwidth selection. The adaptive procedure selecting the intervals ∆ k is based on a method introduced by [START_REF] Lepski | On a problem of adaptive estimation in Gaussian white noise[END_REF], see also Lepski et al. (1997), and Lepski and Spokoiny (1997). If a family of linear estimators can be "well-sorted" by their respective variances (e.g. kernel estimators in the white noise model, see Lepski and Spokoiny (1997)), the Lepski procedure selects the largest bandwidth such that the corresponding estimator does not differ "significantly" from estimators with a smaller bandwidth. Following this principle, we construct a method which adapts to the unknown smoothness, and additionally to the original Lepski method, to the distribution of the data (the design density is unknown). Bandwidth selection procedures in local polynomial estimation can be found in [START_REF] Fan | Data-driven bandwidth selection in local polynomial fitting: variable bandwidth and spatial adaptation[END_REF], [START_REF] Goldenshluger | On spatially adaptive estimation of nonparametric regression[END_REF] or [START_REF] Spokoiny | Estimation of a function with discontinuities via local polynomial fit with an adaptive window choice[END_REF], among others.

The idea of the adaptive rule for selecting the interval δ at the point k2 -J is the following: when f (δ) k (x) is close to f (x) for x ∈ δ (that is, when δ is well-chosen), we have in view of (17):

f (δ ′ ) k - f (δ) k , ϕ δ ′ = Y - f (δ) k , ϕ δ ′ ≈ Y -f , ϕ δ ′ = ξ , ϕ δ ′
for any δ ′ ⊂ δ and ϕ(•) ∈ {ϕ kp (•); 0 p R}, where the right-hand side is a noise term.

Hence, in order to "remove" this noise, we select the largest δ such that this noise term remains smaller than an appropriate threshold, for any δ ′ ⊂ δ and ϕ(•) ∈ {ϕ kp (•); 0 p R}. At each point of the regular grid {k2 -J ; 0 k 2 J }, the bandwidth ∆ k is selected in a fixed set of intervals G k called grid (which is defined below) as follows:

∆ k := argmax δ∈G k μn (δ) | ∀δ ′ ∈G k , δ ′ ⊂ δ, ∀p ∈ {0, . . . , R}, | f (δ ′ ) k - f (δ) k , ϕ kp δ ′ | ϕ kp δ ′ T n (δ, δ ′ ) , (21)
where

T n (δ, δ ′ ) := σ log n nμ n (δ) 1/2 + DC R log(nμ n (δ)) nμ n (δ ′ ) 1/2 , (22)
with C R := 1 + (R + 1) 1/2 and D > (2(b + 1)) 1/2 , if we want to prove Theorem 1 with a loss function satisfying w(x) A(1 + |x| b ). The threshold choice ( 22) can be understood in the following way: since the variance of f (δ) k is of order (nμ n (δ)) -1/2 , we see that the two terms in T n (δ, δ ′ ) are ratios between a penalizing log term and the variance of the estimators compared by the rule (21). The penalization term is linked with the number of comparisons necessary to select the bandwidth. To prove Theorem 1, we use the grid

G k := 1 i n k2 -J -|X i -k2 -J |, k2 -J + |X i -k2 -J | , (23)
and we recall that the scaling coefficients are estimated by

α Jk := 2 -J/2 f ( b ∆ k ) k (k2 -J ).
Remark. In this form, the adaptive estimator has a complexity O(n 2 ). This can be decreased using a smaller grid. An example of such a grid is the following: first, we sort the (X i , Y i ) into (X (i) , Y (i) ) such that X (i) < X (i+1) . Then, we consider i(k) such that k2 -J ∈ [X (i(k)) , X (i(k)+1) ] (if necessary, we take X (0) = 0 and X (n+1) = 1) and for some a > 1 (to be chosen by the statistician) we introduce

G k := [log a (i(k)+1)] p=0 [log a (n-i(k))] q=0 X (i(k)+1-[a p ]) , X (i(k)+[a q ]) . ( 24
)
With this grid, the selection of the bandwidth is fast, and the complexity of the procedure is O(n(log n) 2 ). We can use this grid in practice, but we need extra assumptions on the design if we want to prove Theorem 1 with this grid choice.

Proofs

We recall that the weight function w(•) is non-negative, non-decreasing and such that w(x) A(1 + |x|) b for some A, b > 0. We denote by µ n the joint law of X 1 , . . . , X n and X n the sigma-field generated by X 1 , . . . , X n . |A| denotes both the length of an interval A and the cardinality of a finite set A. M ⊤ is the transpose of M , and ξ = (ξ 1 , . . . , ξ n ) ⊤ . We introduce x k := k2 -J for k ∈ {0, . . . , 2 J }. As previously, C stands for a generic constant that can vary from place to place.

Proof of Theorem 1. To prove the upper bound, we use the estimator defined by ( 11)

where φ is a scaling function satisfying (12) (for instance the Coiflets basis), and where the scaling coefficients are estimated by ( 13). In view of (2) and since µ is continuous on [0, 1],

we have

r n (x) (log n/n) s/(1+2s) . (25)
Together with (10), this entails sup

x∈[0,1] r n (x) -1 f -P J f ∞ n s/(2s+1) 2 -Js = o(1), since 2 J ≍ n -1 . Hence, sup x∈[0,1] r n (x) -1 | f n (x) -f (x)| sup x∈[0,1] r n (x) -1 2 J -1 k=0 ( α Jk -α Jk )φ Jk (x) max 0 k 2 J -1 sup x∈S k r n (x) -1 2 J/2 | α Jk -α Jk |,
where S k denotes the support of φ Jk . Let f k be the Taylor polynomial of f at x k up to the order ⌊s⌋. Using (12), we have f k φ Jk = 2 -J/2 f (x k ), and since f ∈ H(s, L), we have

|α Jk -f (x k )| = | f φ Jk -f (x k )| 2 -J(s+1/2
) . Together with ( 13) and ( 25), this entails sup (2s+1) . This entails sup

x∈[0,1] r n (x) -1 | f n (x) -f (x)| max 0 k 2 J -1 sup x∈S k r n (x) -1 | f ( b ∆ k ) k (x k ) -f (x k )|. ( 26
) Since µ is continuous, r n (•) is continuously differentiable. Hence, since |S k | = 2 -J ≍ n -1 , we have sup x∈S k |r n (x) -1 -r n (x k ) -1 | 2 -J (r -1 n ) ′ ∞ , where g ′ stands for the derivative of g. Moreover, |(r n (x) -1 ) ′ | h ′ n (x)h n (x) -(s+1) n -1 , since h ′ n (x) is uniformly bounded and h n (x) (log n/n) 1/
x∈S k r n (x) -1 r n (x k ) -1 . ( 27
)
In what follows, • ∞ denotes the supremum norm in R R+1 . The following lemma is a version of the bias-variance decomposition of the local polynomial estimator, which is classical: see for instance Fan andGijbels (1995, 1996), [START_REF] Goldenshluger | On spatially adaptive estimation of nonparametric regression[END_REF], [START_REF] Spokoiny | Estimation of a function with discontinuities via local polynomial fit with an adaptive window choice[END_REF], among others. We define the matrix

E (δ) k := Λ (δ) k X(δ) k Λ (δ)
k , where Xk is given by ( 18) and Λ (δ)

k := diag[ ϕ k0 -1 δ , . . . , ϕ kR -1 δ ]. Lemma 1. Conditionally on X n , for any f ∈ H(s, L) and δ ∈ G k , we have | f (δ) k (x k ) -f (x k )| λ(E (δ) k ) -1 L|δ| s + σ(nμ n (δ)) -1/2 U (δ) k ξ ∞ on Ω k (δ), where U (δ) k is a X n -measurable matrix of size (R + 1) × (nμ n (δ)) satisfying U (δ) k (U (δ) k ) ⊤ = Id R+1 .
The proof of Lemma 1 is given later on. Note that within this lemma, the bandwidth δ can change from one point x k to another. We denote

U k := U (δ k ) k for short. Let us define W := Uξ where U := (U ⊤ 0 , . . . , U ⊤ 2 J ) ⊤ . In view of Lemma 1, W is conditionally on X n a centered Gaussian vector such that E f µ [W 2 k |X n ] = 1 for any k ∈ {0, . . . , (R + 1)2 J }. We introduce W N := max 0 k (R+1)2 J |W k | and the event W N := |W N -E[W N |X n ]| L W (log n) 1/2
, where L W > 0. We recall the following classical results about the supremum of a Gaussian vector (see for instance in [START_REF] Ledoux | Probability in Banach spaces[END_REF]):

E f µ W N |X n (log N ) 1/2 (log n) 1/2 ,
and

P f µ W ∁ N |X n exp(-L 2 W (log n)/2) = n -L 2 W /2 . ( 28
)
Let us define the event

T k := {μ n (∆ k ) μn ( ∆ k )} and R k := σ log n nμ n (∆ k ) 1/2
, where the intervals ∆ k are given by

∆ k := argmax δ∈G k μn (δ) | L|δ| s σ log n nμ n (δ) 1/2 .
There is an event S n ∈ X n such that µ n [S ∁ n ] = o(1) faster than any power of n, and such that R k ≍ r n (x k ) and λ(E

(∆ k ) k
) λ 0 for some constant λ 0 , uniformly for any k ∈ {0, . . . , 2 J -1}.

This event is constructed later on. We decompose

| f ( b ∆ k ) k (x k ) -f (x k )| A k + B k + C k + D k ,
where

A k := | f ( b ∆ k ) k (x k ) -f (x k )|1 W ∁ N ∪S ∁ n , B k := | f ( b ∆ k ) k (x k ) -f (x k )|1 T ∁ k ∩W N ∩Sn , C k := | f ( b ∆ k ) k (x k ) - f (∆ k ) k (x k )|1 T k ∩Sn , D k := | f (∆ k ) k (x k ) -f (x k )|1 W N ∩Sn . Term A k . For any δ ∈ G k , we have | f (δ) k (x k )| (nμ n (δ)) 1/2 f ∞ (1 + W N ). ( 29
)
This inequality is proved later on. Hence, using together ( 25), ( 29) and f ∞ Q, we obtain

E f µ max 0 k 2 J r n (x k ) -1 | f ( b ∆ k ) k (x k )| 2b |X n n 2sb/(2s+1)+b+2 .
Then, using w(x) A(1 + |x| b ) and the Cauchy-Schwarz inequality, we obtain

E f µ w( max 0 k 2 J r n (x k ) -1 A k ) n sb/(2s+1)+b/2+1 P f µ [W ∁ N ∪ S ∁ n ] 1/2 = o(1), since µ n [S ∁ n ] = o(1)
faster than any power of n, and L W can be chosen arbitrarily large in (28).

Term D k . Using Lemma 1, together with the definition of ∆ k and the fact that W N (log n) 1/2 on W N , we have

| f (∆ k ) k (x k ) -f (x k )| λ(E (∆ k ) k ) -1 (L|∆ k | s + σ(nμ n (∆ k )) -1/2 W N ) λ(E (∆ k ) k ) -1 R k (1 + (log n) -1/2 W N ) λ(E (∆ k ) k ) -1 r n (x k ) on W N ∩ S n , thus E f µ w( max 0 k 2 J r n (x k ) -1 D k ) C. Term C k . We introduce G k (δ) := {δ ′ ∈ G k |δ ′ ⊂
δ} and the following events:

T k (δ, δ ′ , p) := | f (δ) k - f (δ ′ ) k , ϕ kp δ ′ | σ ϕ kp δ ′ T n (δ, δ ′ ) , T k (δ, δ ′ ) := ∩ 0 p R T k (δ, δ ′ , p), T k (δ) := ∩ δ ′ ∈G k (δ) T k (δ, δ ′ ).
By the definition (21) of the selection rule, we have

T k ⊂ T k ( ∆ k , ∆ k ). Let δ ∈ G k , δ ′ ∈ G k (δ). On T k (δ, δ ′ ) ∩ Ω k (δ ′ ) we have (a proof is given later on) | f (δ) k (x k ) - f (δ ′ ) k (x k )| λ(E (δ ′ ) k ) -1 log n nμ n (δ ′ ) 1/2 . ( 30
)
Thus, using (30), we obtain

E f µ w( max 0 k 2 J r n (x k ) -1 C k ) C.
Term B k . By the definition (21) of the selection rule, we have T ∁ k ⊂ T k (∆ k ) ∁ . We need the following lemma.

Lemma 2. If δ ∈ G k satisfies L|δ| s σ log n nμ n (δ) 1/2 (31)
and f ∈ H(s, L), we have

P f µ T k (δ) ∁ |X n (R + 1)(nμ n (δ)) 1-D 2 /2
on Ω k (δ), where D is the constant from the threshlod (22).

Using together Lemma 2, f ∞ Q and (29), we obtain

E f µ w max 0 k 2 J R -1 k | f ( b ∆ k ) k (x k ) -f (x k )|1 T ∁ k ∩W N |X n C, thus E f µ w( max 0 k 2 J r n (x k ) -1 B k ) C,
and Theorem 1 follows.

Proof of Lemma 1. On Ω k (δ), we have X(δ) k = X δ k , and λ(X

(δ) k ) > (nμ n (δ)) -1/2 > 0, thus X (δ)
k and E (δ) k are invertible. Let f k be the Taylor polynomial of f at x k up to the order ⌊s⌋ and θ k ∈ R R+1 be the coefficient vector of f k . Using f ∈ H(s, L), we obtain

| f (δ) k (x k ) -f (x k )| | (Λ (δ) k ) -1 ( θ(δ) k -θ k ) , e 1 | + |δ| s = | (E (δ) k ) -1 Λ (δ) k X (δ) k ( θ(δ) k -θ k ) , e 1 | + |δ| s .
In view of ( 17), we have on Ω k (δ) for any p ∈ {0, . . . , R}:

(X (δ) k ( θ(δ) k -θ k )) p = f (δ) k -f k , ϕ kp δ = Y -f k , ϕ kp δ thus, X (δ) k ( θ(δ) k -θ k ) = B (δ) k + V (δ) k where (B (δ) k ) p := f -f k , ϕ kp δ and (V (δ)
k ) p := ξ , ϕ kp δ , which correspond respectively to bias and variance terms. Since f ∈ H(s, L) and λ(M ) -1 = M -1 for any symmetrical and positive matrix M , we have

| (E (δ) k ) -1 Λ (δ) k B (δ) k , e 1 | λ(E (δ) k ) -1 L|δ| s . Since (V (δ) k ) p = (nμ n (δ)) -1 D (δ) k ξ where D (δ) k is the (R + 1) × (nμ n (δ)) matrix with entries (D (δ) k ) i,p := (X i -x k ) p , X i ∈ δ, we can write | (E (δ) k ) -1 Λ (δ) k V (δ) k , e 1 δ | σ(nμ n (δ)) -1/2 (E (δ) k ) -1/2 U (δ) k ξ ∞ , where U (δ) k := (nμ n (δ)) -1/2 (E (δ) k ) -1/2 Λ (δ) k D (δ) k satisfies U (δ) k (U (δ) k ) ⊤ = Id R+1 since E (δ) k = Λ (δ) k X (δ) k Λ (δ) k and X (δ) k = (nμ n (δ)) -1 D (δ) k (D (δ) k ) ⊤ , thus the lemma.
Proof of (29). If μn (δ) = 0, we have f (δ) k = 0 by definition and the result is obvious, thus we assume μn (δ) > 0. Since λ(

X(δ) k ) (nμ n (δ)) -1/2 > 0, the matrices X(δ) k and Λ (δ) k are invertible thus E (δ)
k also is, and we have

| f (δ) k (x k )| = | (Λ (δ) k ) -1 θ(δ) k , e 1 | (E (δ) k ) -1 Λ (δ) k X(δ) k θ(δ) k = (E (δ) k ) -1 Λ (δ) k Y (δ) k .
Moreover, we have by the definition of

X(δ) k : (E (δ) k ) -1 (Λ (δ) k ) -1 2 ( X(δ) k ) -1 ( X(δ) k ) -1 = λ( X(δ) k ) -1 (nμ n (δ)) 1/2 . Let us denote Ẽ(δ) k := Λ (δ) k X (δ) k Λ (δ)
k . With the same notations as in the proof of Lemma 1, we have

|(Λ (δ) k Y (δ) k ) p | = ϕ kp -1 δ f , ϕ kp δ + (Λ (δ) k ) p ξ , ϕ kp δ f ∞ + (nμ n (δ)) -1 Ẽ(δ) k ( Ẽ(δ) k ) -1 Λ (δ) k D (δ) k ξ p = f ∞ + (nμ n (δ)) -1/2 Ẽ(δ) k U (δ) k ξ p , thus (29), since Ẽ(δ) k R + 1.
Proof of (30). Let us define H (δ)

k := Λ (δ) k X (δ) k . On Ω k (δ ′ ), we have: | f (δ) k (x k ) - f (δ ′ ) k (x k )| = |( θ(δ) k - θ(δ ′ ) k ) 0 | Λ (δ ′ ) k ( θ(δ) k - θ(δ ′ ) k ) ∞ = (E (δ ′ ) k ) -1 H (δ ′ ) k ( θ(δ) k - θ(δ ′ ) k ) ∞ λ(E (δ ′ ) k ) -1 H (δ ′ ) k ( θ(δ) k - θ(δ ′ ) k ) ∞ .
Since on Ω k (δ ′ ), (H

(δ ′ ) k ( θ(δ) k - θ(δ ′ ) k )) p = f (δ) k - f (δ ′ ) k
, ϕ kp δ ′ / ϕ kp δ ′ , and since δ ′ ⊂ δ, we obtain (30) on T k (δ, δ ′ ).

Proof of Lemma 2. We denote by P (δ)

k the projection onto Span{ϕ k0 , . . . , ϕ kR } with respect to the inner product • , • δ . Note that on Ω k (δ), we have f (δ)

k = P (δ) k Y . Let δ ∈ G k and δ ′ ∈ G k (δ).
In view of (17), we have on Ω k (δ) for any ϕ = ϕ kp , p ∈ {0, . . . , R}:

f (δ ′ ) k - f (δ) k , ϕ δ ′ = Y - f (δ) k , ϕ δ ′ = f -P (δ) k Y , ϕ δ ′ + ξ , ϕ δ ′ = A k -B k + C k , where A k := f -P (δ) k f , ϕ δ ′ , B k := σ P (δ) k ξ , ϕ δ ′ and C k := σ ξ , ϕ δ ′ . If f k
is the Taylor polynomial of f at x k up to the order ⌊s⌋, since δ ′ ⊂ δ and f ∈ H(s, L) we have:

|A k | ϕ δ ′ f -f k + P (δ) k (f k -f ) δ ϕ δ ′ f -f k δ ϕ δ ′ L|δ| s ,
and using (31), we obtain

|A k | ϕ δ ′ σ log n nμ n (δ) 1/2 . Since P (δ)
k is an orthogonal projection, the variance of B k is equal to

σ 2 E f µ P (δ) k ξ , ϕ 2 δ ′ |X n σ 2 ϕ 2 δ ′ E f µ P (δ) k ξ 2 δ ′ |X n = σ 2 ϕ 2 δ ′ Tr(P (δ) k )/(nμ n (δ ′ )),
where Tr(M ) stands for the trace of a matrix M . Since P (δ)

k is the projection onto Pol R , Tr(P (δ) k ) R + 1, and the variance of B k is smaller than σ 2 ϕ 2 δ ′ (R + 1)/(nμ n (δ ′ )). Then,

E f µ [(B + C) 2 |X n ] σ 2 ϕ 2 δ ′ C 2 R /(nμ n (δ ′ )). ( 32
)
In view of the threshold choice ( 22), we have

| f (δ) k - f (δ ′ ) k , ϕ δ ′ | > ϕ δ ′ T n (δ, δ ′ ) ⊂ ϕ -1 δ ′ |B k + C k | σ(nμ n (δ ′ )) -1/2 C R > D log(nμ n (δ)) 1/2 ,
and using (32) together with P[|N (0, 1)| > x] exp(-x 2 /2) and |G k (δ)| (nμ n (δ)), we obtain

P f µ [T (δ) ∁ |X n ] δ ′ ∈G k (δ) R p=0 exp -D 2 log(nμ n (δ))/2 (R + 1)(nμ n (δ)) 1-D 2 /2 ,
which concludes the proof.

Construction of S n . We construct an event S n ∈ X n such that µ n S ∁ n = o(1) faster than any power of n, and such that on this event, R k ≍ r n (x k ) and λ(E

(∆ k ) k
) λ 0 uniformly for any k ∈ {0, . . . , 2 J }. We need preliminary approximation results, linked with the approximation of µ by μn . The following deviation inequalities use Bernstein inequality for the sum of independent random variables, which is standard. We have

µ n μn (δ) µ(δ) -1 > ǫ exp -ε 2 nµ(δ) (33)
for any interval δ ⊂ [0, 1] and ε ∈ (0, 1). Let us define the events

D (δ) n,a (x, ε) := 1 µ(δ) δ • -x |δ| a dμ n -e a (x, µ) ε
where e a (x, µ) := (1 + (-1) a )(β(x) + 1)/(a + β(x) + 1) (a is a natural integer) where we recall that β(x) comes from Assumption D (if x is such that µ(x) > 0 then β(x) = 0). Using together Bernstein inequality and the fact that

1 µ(δ) δ t -x |δ| a µ(t)dt → e a (x, µ)
as → 0, we obtain

µ n (D (δ) n,a (x, ε)) ∁ exp -ε 2 nµ(δ) . (34)
By definition (23

) of G k , we have ∆ k = [x k -H n (x k ), x k + H n (x k )]
where

H n (x) := argmin h∈[0,1] Lh s σ log n nμ n ([x -h, x + h]) 1/2 (35)
is an approximation of h n (x) (see (2)). Since μn is "close" to µ, these quantities are close to each other for any x. Indeed, if δ n (x) := [x -h n (x), x + h n (x)] and ∆ n (x) := [x -H n (x), x + H n (x)] we have using together ( 35) and ( 2):

H n (x) (1 + ε)h n (x) = μn [(1 + ε)δ n (x)] µ[δ n (x)] (1 -ε) -2 (36)
for any ε ∈ (0, 1), where

(1 + ε)δ n (x) := [x -(1 + ε)h n (x), x + (1 + ε)h n (x)]
. Hence, for each x = x k , the left hand side event of (36) has a probability that can be controlled under Assumption D by (33), and the same argument holds for

{H n (x) > (1 -ε)h n (x)}.
Combining (33), ( 34) and ( 36), we obtain that the event

B n,a (x, ε) := 1 μn (∆ n (x)) ∆n(x) • -x |δ n (x)| a dμ n -e a (x, µ) ε
satisfies also (34) for n large enough. This proves that (X

(∆ k ) k
) p,q and (Λ

(∆ k ) k
) p are close to e p+q (x k , µ) and e 2p (x k , µ) -1/2 respectively on the event S n := a∈{0,...,2R} k∈{0,...,2 J -1}

B n,a (x k , ε).

Using the fact that λ(M ) = inf x =1 x ⊤ M x for a symmetrical matrix M , where λ(M ) denotes the smallest eigenvalue of M , we can conclude that for n large enough,

λ(Λ (∆ k ) k X (∆ k ) k Λ (∆ k ) k ) min x∈[0,1] λ(E(x, µ)) =: λ 0 ,
where E(x, µ) has entries (E(x, µ)) p,q = e p+q (x, µ)/(e 2p (x, µ)e 2q (x, µ)) 1/2 . Since E(x, µ) is definite positive for any x ∈ [0, 1], we obtain that on S n , λ(X

(∆ k ) k
) λ 1 for some constant

λ 1 > 0, thus S n ⊂ Ω n (∆ k ) and λ(E (∆ k ) k
) λ 0 uniformly for any k ∈ {0, . . . , 2 J -1}, since

E (∆ k ) k = Λ (∆ k ) k X (∆ k ) k Λ (∆ k ) k on Ω n (∆ k ). Moreover, since R k = LH n (x k ) s , using together (33)
and ( 36), we obtain R k ≍ r n (x k ) uniformly for k ∈ {0, . . . , 2 J -1}.

Proof of Theorem 2. The main features of the proof are first, a reduction to the Bayesian risk over an hardest cubical subfamily of functions for the L ∞ metrics, which is standard:

see [START_REF] Korostelev | An asymptotically minimax regression estimator in the uniform norm up to exact contant[END_REF], [START_REF] Donoho | Asymptotic minimax risk for sup-norm loss: Solution via optimal recovery[END_REF], [START_REF] Korostelev | The asymptotic minimax constant for sup-norm loss in nonparametric density estimation[END_REF] and [START_REF] Bertin | Minimax exact constant in sup-norm for nonparametric regression with random design[END_REF], and the choice of rescaled hypothesis with design-adapted bandwidth h n (•), necessary to achieve the rate r n (•).

Let us consider ϕ ∈ H(s, L; R) (the extension of H(s, L) to the whole real line) with support [-1, 1] and such that ϕ(0) > 0. We define

a := min 1, 2 ϕ 2 ∞ 1 1 + 2s + β -α 1/(2s)
and

Ξ n := 2a(1 + 2 1/(s-⌊s⌋) ) sup x∈[0,1] h n (x),
where we recall that ⌊s⌋ is the largest integer smaller than s. Note that (7) entails

Ξ n (log n/n) 1/(1+2s+β) . ( 37
) If I n = [c n , d n ], we introduce x k := c n + k Ξ n for k ∈ K n := 1, . . . , |I n | Ξ -1 n
, and denote for the sake of simplicity h k := h n (x k ). We consider the family of functions

f (•; θ) := k∈Kn θ k f k (•), f k (•) := La s h s k ϕ • -x k h k ,
which belongs to H(s, L) for any θ ∈ [-1, 1] |Kn| . Using Bernstein inequality, we can see that

H n := k∈Kn μn ([x k -h k , x k + h k ]) µ([x k -h k , x k + h k ]) 1/2 satisfies µ n [H n ] = 1 -o(1). (38)
Let us introduce b := c s ϕ(0). For any distribution B on Θ n ⊂ [-1, 1] |Kn| , by a minoration of the minimax risk by the Bayesian risk, and since w is non-decreasing, the left hand side of ( 9) is smaller than

w(b) inf b θ Θn P n θ max k∈Kn | θ k -θ k | 1 B(dθ) w(b) Hn inf b θ Θn P n θ max k∈Kn | θ k -θ k | 1|X n B(dθ)dµ n .
Hence, together with (38), Theorem 2 follows if we show that on H n

sup b θ Θn P n θ max k∈Kn | θ k -θ k | < 1|X n B(dθ) = o(1). (39)
We denote by L(θ; Y 1 , . . . , Y n ) the conditional on X n likelihood function of the observations

Y i from (1) when f (•) = f (•; θ). Conditionally on X n , we have L(θ; Y 1 , . . . , Y n ) = 1 i n g σ (Y i ) k∈Kn g v k (y k -θ k ) g v k (y k ) , where g v is the density of N (0, v 2 ), v 2 k := E{y 2 k |X n } and y k := n i=1 Y i f k (X i ) n i=1 f 2 k (X i )
.

Thus, choosing

B := k∈Kn b, b := (δ -1 + δ 1 )/2, Θ n := {-1, 1} |Kn| ,
the left hand side of (39) is smaller than

1 i n g σ (Y i ) k∈Kn g v k (y k ) k∈Kn sup b θ k {-1,1} 1 | b θ k -θ k |<1 g v k (y k -θ k )b(dθ k ) dY 1 × • • • × dY n ,
and θ k = 1 y k 0 -1 y k <0 are strategies reaching the supremum. Then, in (39), it suffices to take the supremum over estimators θ with coordinates θ k ∈ {-1, 1} measurable with respect to y k only. Since conditionally on X n , y k is in law N (θ k , v 2 k ), the left hand side of (39) is smaller than

k∈Kn 1 -inf b θ k ∈{-1,1} {-1,1} 1 | b θ k (u)-θ k | 1 g v k (u -θ k )du b(dθ k ) . Moreover, if Φ(x) := x -∞ g 1 (t)dt inf b θ k ∈{-1,1} {-1,1} 1 | b θ k (u)-θ k | 1 g v k (u -θ k )du b(dθ k )
1 2 min g v k (u -1), g v k (u + 1) du = Φ(-1/v k ).

On H n , we have in view of (2)

v 2 k = σ 2 n i=1 f 2 k (X i ) 2 (1 -δ) ϕ 2 ∞ c 2s log n ,
and since Φ(-x) exp(-x 2 /2)(x √ 2π) for any x > 0, we obtain Φ(-1/v k ) (log n) -1/2 n {α-1/(1+2s+β)}/2 =: L n .

Thus, the left hand side of ( 39) is smaller than (1 -L n ) |Kn| , and since

|I n |Ξ -1 n L n n {1/(1+2s+β)-α}/2 (log n) 1/2-1/(1+2s+β) → +∞ as n → +∞, Theorem 2 follows.

Proof of Corollary 1. Let us consider the loss function w(•) = | • |, and let f v n be an estimator converging with rate v n (•) over F in the sense of (3). Hence,

1 sup f ∈F E f µ sup x∈In r n (x) -1 | f v n (x) -f (x)| sup x∈In v n (x) r n (x) sup f ∈F E f µ sup x∈In v n (x) -1 | f v n (x) -f (x)| sup x∈In v n (x) r n (x) ,
where we used Theorem 2.

|∂ m f (δ) k (x k ) -∂ m f (x k )| λ(E (δ) k ) -1 |δ| -m L|δ| s + σ(nμ n (δ)) -1/2 W N ,
where in the same way as in the proof of Theorem 1, W N satisfies

E f µ [W N |X n ] (log N ) 1/2 , ( 40
)
with N depending on the size of the supremum, to be specified below. First, we prove a). (1 + (log ℓ n ) -1/2 W N ).

Then, integrating with respect to P f µ (•|X n ) and using ( 40) where N = [ℓ n ] entails a), since log ℓ n = o(log n).

The proof of b) is similar to that of a). In this setting, the rate r n (•) (see ( 2)) can be written as r n (x) = (log n/n) αn(x) for x in I n (for n large enough) where α n (x 0 ) = s/(1 + 2s + β) and α n (x) > s/(1 + 2s + β) for x ∈ I n -{x 0 }. We define

x k+1 =   
x k + n -αn(x k )/s for k ∈ {-N, . . . , -1}

x k + n -αn(x k+1 )/s for k ∈ {0, . . . , N },

where N := [ℓ n ]. All the points fit in I n , since

|x -N -x N | -N k N
n -min(αn(x k ),αn(x k+1 ))/s 2(ℓ n /n) 1/(1+2s+β) .

We consider the bandwidths (1 + (log ℓ n ) -1/2 W N ), hence

E f µ sup x∈In r n (x) -1 | f n (x) -f (x)| log ℓ n log n s/(1+2s+β)
= o(1), which concludes the proof of Proposition 1.

Proof of Proposition 1 .

 1 Without loss of generality, we consider the loss w(•) = |•|. In order to prove Proposition 1, we use the linear LPE. If we denote by ∂ m f the m-th derivative of f , a slight modification of the proof of Lemma 1 gives for f ∈ H(s, L) with s > m,

Since

  |I n | ∼ (ℓ n /n) 1/(2s+1) , if I n = [a n , b n ], the points x k := a n + (k/n) 1/(2s+1) , k ∈ {0, . . . , N },where N := [ℓ n ] belong to I n . We consider the bandwidth we takeδ k := [x k -h n , x k + h n ].Note that since µ(x) > 0 for any x, μn (δ) ≍ |δ| as |δ| → 0 with probability going to 1 faster than any power of n (using Berstein inequality, for instance). We consider the estimator defined byf n (x) := r m=0 ∂ m f (δ k ) k (x k )(x -x k ) m /m! for x ∈ [x k , x k+1 ), k ∈ {0, . . . , [ℓ n ]}, (42)where r := ⌊s⌋. Using a Taylor expansion of f up to the degree r together with (41) gives (n/ log n) s/(1+2s) sup x∈In | f n (x) -f (x)| log ℓ n log n s/(1+2s)

  h k := (log ℓ n /n) αn(x k )/s , and the intervals δ k = [x k -h k , x k + h k ]. We keep the same definition (42) for f n . Since x 0 is a local extremum of r n (•), we have in the same way as in the proof of a) that sup x∈In r n (x) -1 | f n (x) -f (x


Alan Tassin
email: alan.tassin@ifremer.fr

Thibaut Breton

Nicolas Jacques

Evolution of the contact line during the water exit of flat plates

Introduction

We investigate experimentally and numerically the evolution of the contact line during the water exit of flat plates (circular disc and square plate). The water exit problem, or the lifting of a body initially floating at the water surface, has regained attention and motivated a number of studies in the last years [START_REF] Korobkin | A linearized model of water exit[END_REF][START_REF] Tassin | Two-dimensional water entry and exit of a body whose shape varies in time[END_REF]. The evolution of the contact line is a central part of the analytical models proposed by [START_REF] Korobkin | A linearized model of water exit[END_REF] and [START_REF] Tassin | Two-dimensional water entry and exit of a body whose shape varies in time[END_REF], which are based on a linearisation of the boundary conditions on the initial flat free surface (z = 0). In [START_REF] Tassin | Two-dimensional water entry and exit of a body whose shape varies in time[END_REF], a modified von Karman (geometrical) condition is used during the exit stage for the water entry and exit of two-dimensional bodies, whereas [START_REF] Korobkin | A linearized model of water exit[END_REF] employed a condition which states that the speed of contraction of the wetted surface is proportional to the speed of the water particles located at the contact point:

ċ(t) = γ • ϕ x (x = c(t), z = 0, t), (1)
where c(t) is the location of the contact point on the horizontal x-axis, ϕ is the linearized velocity potential and γ is a factor of proportionality. [START_REF] Korobkin | A linearized model of water exit[END_REF] obtained good results in terms of force prediction with γ = 2 when comparing with CFD results. Note that this model is suitable both for two-dimensional and axisymetric cases and that it can deal with flat bodies. The choice of the value of γ = 2 remains however based on comparisons in terms of force prediction but might not give the best results in terms of contact point position. The lack of experimental results motivated the present experimental investigation. Given the importance of the contact point location, we aimed at measuring the wetted surface during the water exit of flat bodies. However, in contrast to previous water-entry experiments during which the wetted surface was obtained from a bottom view of the mock-up, we observed during preliminary experiments that it was difficult to follow the wetted surface from bottom views during water-exit experiments. In order to overcome this limitation, we are developping a new technique based on the use of transparent mock-ups and the diffusion of light in the material. We show that with a single LED light source placed at the centre of a circular disc with a diameter of 20cm, it is possible to illuminate the contact line and to follow the contact line location with a high-speed video camera at 1000fps. In order to validate the measurement technique, we performed experiments with a draughtboard located at the bottom of the tank similarly to [START_REF] Scolan | Impact of three-dimensional standing waves on a flat horizontal plate[END_REF], showing a good agreement between the two techniques. The evolution of the contact line is obtained by a contour tracking algorithm and compared to the model of [START_REF] Korobkin | A linearized model of water exit[END_REF]. In parallel, we performed numerical simulations with the ABAQUS CFD software for a circular disc exiting water at infinite Froude number and a constant acceleration. We also present experimental results obtained during the water exit of a square plate with a tangential LED lighting system. These results show the complexity of the shape of the contact line during the water exit of a square plate and demonstrate the performance of the tangential LED lighting system for such a complex case.

Experimental set-up

A sketch of the experimental set-up is drawn in Fig. 1. One can see a transparent mock-up made out of PMMA fixed to a rigid frame by high stiffness strings. The rigid frame is lifted by an eletric actuator. A highspeed camera (Photron Fastcam MiniAX50) records the scene from the top via a mirror. The water tank (1 m long, 0.8 m high, 0.6 m wide) was filled up to a level of 40 cm. In the following, we report experiments obtained with a circular disc and a modified square plate. The

Numerical simulations

Numerical simulations were performed using the Eulerian module of the Finite Element software ABAQUS/Explicit. The simulations are based on a non-viscous approach and the Volume-Of-Fluid method. The equations were solved in a moving coordinate system attached to the moving body in order to avoid re-meshing in the calculations (see [START_REF] Tassin | Etude expérimentale et numérique du phénomène de sortie d'eau[END_REF]). The effect of gravity was not taken into account in the calculations presented in the present paper.

Results

A sequence of images obtained during an experiment of water exit with the circular disc is plotted in Fig. 4. One can observe two concentric bright circles, the exterior circle corresponding to the contour of the disc and the interior circle corresponding to the contact line which contracts towards the centre of the disc during the exit. In order to demonstrate that the illuminated contour delimits the surface of contact between the liquid and the disc, we also performed experiments during which a draughtboard was placed at the bottom of the water tank. A sequence of images obtained with the draughtboard technique, and for similar elevations as in Fig. 4, is plotted in Fig. 5. The contour observed in the different pictures of Fig. 4 has been extracted with a contour detection algorithm and superimposed to the images with the draughtboard in Fig. 5. This comparison clearly shows the close connection between the illuminated contour and the contact line. Small discrepancies can nevertheless be observed, probably because of the imperfections of the set-up. We adjusted the altitude of the mock-up such as to minimize the penetration depth before the experiments, but it is difficult to control the initial penetration depth given that the mock-up is held by strings and is not perfectly horizontal. The evolution of the relative radius of the contact surface as function of the elevation is plotted in Fig. 6. In the experiments, the value of c(t) (resp. c 0 ) is the average value of the semi-axes of the ellipse obtained with the contour detection algorithm when fitting the contact line (resp. the contour of the disc). A record of the acceleration during the water exit of the circular disc is plotted in Fig. 7. The acceleration curve exhibits important oscillations because of the compliance of the strings. The elevation curve plotted in Fig. 7 was obtained by a double time integration of the measured acceleration. Note that these new experimental results are more accurate than those presented in [START_REF] Tassin | Etude expérimentale et numérique du phénomène de sortie d'eau[END_REF], thanks to the use of a more appropriate acceloremeter. The results obtained from the numerical simulations and the analytical model of Korobkin (for 2 values of the parameter γ) for the water exit of a circular disc at constant acceleration and infinite Froude number are also plotted in Fig. 6. A sequence of images obtained (at 1000 fps) during the water exit of the modified square plate is plotted in Fig. 8, showing the complexity of the shape of the contact line for an initially square wetted surface. Note the very elongated regions of the contact line along the diagonals of the square in Fig. 8

Conclusion and discussion

An original technique has been proposed for the measurement of the contact surface during the water exit of flat plates. The central LED technique has been used to measure the evolution of the contact surface during the water exit of a circular disc. Preliminary numerical results for a circular disc exiting water at constant acceleration and without gravity have been presented. New simulations will be run in order to simulate the experimental conditions (including gravity and viscosity). The edge lighting technique is a promising technique for more complex cases. The quality of the resuts obtained for the modified square plate are very satisfactory for image processing. We believe that this technique is likely to be extended to mock-ups of bigger size and to three-dimensional bodies.

Figure 1 :

 1 Figure 1: Description of the experimental set-up

Figure 4 :

 4 Figure 4: Sequence of images obtained during the water exit of a circular for different values of the elevation h(t). (a-b): grey levels multiplied by 3, (c-d): original grey levels

Figure 5 :

 5 Figure 5: Comparison between the contours extracted from Fig. 4 (red dashed line) and images obtained with the draughtboard technique during the water exit of a circular disc

Figure 6 :

 6 Figure 6: Measured and calculated relative radius of the contact point as a function of the elevation

Figure

  Figure 7: Acceleration and elevation

Figure 8 :

 8 Figure 8: Sequence of images obtained during the water exit of the modified square plate for different of the elevation h(t)

Acknowledgements

We would like to thank Sébastien Chalony for his help in the construction of the circular disc mock-up and Dominique Le Roux for his help in the design of the modified square plate mock-up.