Bogdan Cautis
email: bogdan.cautis@inria.fr

Serge Abiteboul
email: serge.abiteboul@inria.fr

Tova Milo

Reasoning about XML Update Constraints *

Keywords: H.2.3 [Database management]: Languages; H.2.0 [Database management]: General-Security, integrity, and protection Algorithms, Languages, Theory Semi-structured data, XML, update constraints, implication, data integrity

We introduce in this paper a class of constraints for describing how an XML document can evolve, namely XML update constraints. For these constraints, we study the implication problem, giving algorithms and complexity results for constraints of varying expressive power. Besides classical constraint implication, we also consider an instancebased approach. More precisely, we study implication with respect to a current tree instance, resulting from a series of unknown updates. The main motivation of our work is reasoning about data integrity under update restrictions in contexts where owners may lose control over their data, such as in publishing or exchange.

INTRODUCTION

Restricting the ways in which data is modified and transformed is often a necessity and the basis for reasoning about data validity. When data is under centralized control, arbitrarily complex update constraints can be actively enforced inside the boundaries of the data owner, who can monitor changes. But in distributed, loose environments, for * This work has been partially supported by the ANR grant DocFlow, the EC project EDOS and the Israel Science Foundation.

instance when data is published or exchanged, it becomes much harder to control updates. The enforcement of update restrictions can be passively achieved via cryptographic techniques, and by consequence only simpler update restrictions can be imposed. Dealing with simpler update limitations has, however, an advantage, since it allows users to do more reasoning about data properties, beyond "no illegal update occurred", understanding what could have happened and how.

To illustrate, consider an XML document that is exchanged between three parties, Source, Broker and User (Figure 1). Assume Broker is allowed to modify data he receives from Source, but only in a controlled manner. For instance, advertisements may be introduced but only in certain welldefined areas. Also, some information may be filtered out, but again in well-defined areas. For instance, Broker may be allowed to remove a private phone number but not to replace it by another one. In particular, the rules of the game should be precise enough so that (a) the Source can choose the right restrictions on how data can be modified and can specify them in a clear way, and (b) based on the given update restrictions and the data to which they apply, the User has the means to decide on the validity of the data that interests her.

This paper introduces a constraint model that allows data owners to specify restrictions on allowed updates for XML trees. Starting from this model, we focus on inference techniques that help data owners choose the right restrictions and help users reason about the integrity properties of data. In short, the constraints we consider allow stating that a set of selected XML nodes representing the result to some path query should always grow, or shrink, or should not change at all. Then we study two inference problems, namely, the constraint implication problem and the instance-based implication problem.

The constraint implication problem is defined as follows. Given a set of update constraint C and a constraint c, is it true that each pair (I, J) of consecutive data instances (i.e., a tree instance before and after updates) satisfying C also satisfies c?

In the instance-based implication problem, J is known. The problem becomes: is it true that for each I such that (I, J) satisfies C, (I, J) also satisfies c. Thus this may be viewed as a question over the past. For instance, knowing that C is enforced, can we derive from the instance we received that no new product has been inserted. A symmetrical problem (not studied here) is obtained by giving I instead of J and questioning the future. Instance-based implication may be viewed as a foray into the more general problem of temporal queries under update constraints.

Source

As our constraint language closely captures what cryptographic techniques can support, we believe that such a simple model, that talks only about increasing or decreasing sets of XML nodes, is best suited to express update restrictions on data with limited owner control and no log or history of updates. Hence, it has not only theoretical but also practical value, as it can be effectively enforced in noncentralized environments. However, the focus of this paper is not on the actual enforcement, but on reasoning about integrity properties of data under update constraints. We only remind here that although classic signing techniques prevent any kind of modification on signed data, more flexible approaches have been provided lately [START_REF] Rivest | Two signature schemes[END_REF][START_REF] Devanbu | Authentic third-party data publication[END_REF][START_REF] Abiteboul | Digital signatures for modifiable collections[END_REF][START_REF] Bellare | Incremental cryptography: The case of hashing and signing[END_REF][START_REF] Johnson | Homomorphic signature schemes[END_REF], in which some restricted modifications may still occur, without causing the invalidation of the data. For example, by digital signatures, one can impose that a certain collection of items can only increase (or decrease).

To the best of our knowledge, this work is the first to consider update constraints for tree structured data. Perhaps the work that is closest in spirit is the one of Miklau and Suciu [START_REF] Miklau | Modeling integrity in data exchange[END_REF] which, for relational data, models integrity guarantees of digital signature schemes as embedded dependencies and considers query related issues that can be solved by the relational chase [START_REF] Abiteboul | Foundations of Databases[END_REF]. As we will see, both for constraint implication and instance-based implication, new issues are raised when considering trees. While integrity constraints for XML data have received a lot of attention lately [START_REF] Deutsch | XML queries and constraints, containment and reformulation[END_REF][START_REF] Fan | Integrity constraints for XML[END_REF][START_REF] Buneman | Reasoning about keys for XML[END_REF], we study here update constraints, defined in terms of XPath expressions, which talk about how a document can be changed. Nevertheless, our work gives also new insight into XML integrity constraints in general.

The paper is organized as follows. In Section 2 we define the constraint language and the implication problems studied in the paper. In Section 3 the two implication problems are related to previous works on query containment and constraints for XML data. Constraint implication is studied in Section 4 and instance-based implication in Section 5. We briefly discuss a model extension, namely relative constraints, in Section 6. In Section 7 we discuss other related works and we conclude. For space reasons, we only give the intuition of proofs.

XML AND UPDATE CONSTRAINTS

Given two infinite domains, the domain of node identifiers (N ) and the domain of labels (L), we define XML trees as follows.

Definition 2.1. An (unordered) data tree is an expression (T, λ), where T = (N, E) is a finite unordered tree, with set of nodes N ⊂ N , directed edges E ⊂ N × N , and λ : N → L is a labeling function over nodes.

By the above definition, we intend to capture XML data which, besides labels (L), have unique node Ids (N ). Hence a node is a pair in N × L and from here on, when we speak of an individual node, we mean such a pair1 .

In the specification of update constraints, we rely on XPath queries from the fragment XP {/, [], //, * }, generally referred to as unary tree pattern queries. More precisely, the XPath expressions used in this paper are generated by the following grammar: Notice that the root of the document is treated differently from other nodes, as predicates cannot be defined on the root. The reason for this is that we are mainly interested in queries that test properties of individual nodes, and not of entire documents.

The semantics of such queries is defined in the standard way (see, for instance, [START_REF] Wadler | A formal semantics of patterns in XSLT[END_REF][START_REF] Benedikt | XPath leashed[END_REF]). For example, the previous query returns the set of b nodes having both a c child and an a ancestor which is child of the document root. For some node n in a data tree I and path query q, q(n, I) denotes the result of q evaluated on the subtree of I rooted at n. We write q(I) for q(root, I). We stress that the result of a query is set of pairs (Id, label). The evaluation of XP {/, [], //, * } queries can be done in polynomial time [START_REF] Gottlob | The complexity of XPath query evaluation and xml typing[END_REF].

By concrete path, we denote a path that has the output node labeled by a concrete label (not wildcard). In order to simplify the presentation, we will only discuss in this paper concrete XPath queries. However, all the results can be extended and reformulated to deal also with non-concrete paths.

Throughout this paper, we use of the notions of query containment (denoted by ⊆) and equivalence (denoted by ≡), both defined in a standard way. We also consider the intersection of queries (denoted by ∩). Informally, we say that q ≡ q1 ∩ • • • ∩ q k if for all instances I, we have q(I) ≡ q1(I) ∩ • • • ∩ q k (I).

As in [START_REF] Tatarinov | Updating XML[END_REF], an update on an XML tree is defined as a sequence of node insertions deletions, moving and modifications of labels. In this paper, we will simply abstract an update as a pair of data trees (I, J), where I (resp. J) is the before (resp. after) update tree.

We next define update constraints.

Definition 2.2 (Syntax). An XML update constraint is an expression (q, σ), where q is an XPath query called the range and σ is the constraint type, i.e., one of no-insert (in short ↓) or no-remove (in short ↑) . Definition 2.3 (Semantics). We say that a pair of trees (I, J) is valid with respect to some constraint c = (q, σ) (denoted (I, J) ⊢ c) if we have q(I) ⊆ q(J) (resp. q(J) ⊆ q(I)) when σ is no-remove (resp. no-insert). A pair (I, J) is valid for a set of constraints if it is valid for each of them. Note that we can express immutability restrictions by simply pairing no-remove and no-insert conditions. As a shorthand, we will use (q, ⊤) to denote such a pair of no-remove and no-insert constraints.

Example 2.1. For example, consider the (I,J) instances of Figure 2 and the following constraints:

• c1 = (/patient[/visit], ↓) • c2 = (/patient[/clinicalTrial], ⊤) • c3 = (/patient/visit, ↑),
The first constraint states that the set of patients having a visit can only shrink. The second one says that the set of patients having a clinicalTrial cannot change at all, while the third one says that the overall set of visits can only grow. The pair of instances (I, J) in Figure 2 is valid for c1 and c2 but not for c3. This is because the visit node n7 has been deleted.

We will briefly consider one extension to this constraints, namely relative update constraints, in Section 6. These are constraints that specify update restrictions relative to some scope, e.g., a particular constraint should hold for each patient in the medical document that is sent. Other possible extensions and directions for future work are discussed in Section 7.

Finally, note that in our model constraints are always consistent and, in particular, a pair (I, I) of identical instances is valid for any set of update constraints. This would no longer be the case if we consider arbitrary inclusions such as (q1(I) ⊆ q2(J)), that would actually "force" modifications to happen.

Implication problems

We are now ready to formally define the problems we study. First, we consider the implication problem for update constraints: Definition 2.4 (General implication). Given a set of update constraints C and an update constraint c, we say that C implies c (denoted C |= c) if for any pair of tree instances I, J, we have (I, J) ⊢ C ⇒ (I, J) ⊢ c.

In Example 2.1, the constraint c = (/patient[/visit][/clinicalTrial], ↓)
is implied by {c1, c2}. We briefly explain why: in order to violate c, by adding in some instance I a node in the result of /patient[/visit][/clinicalTrial], one should either (a) add some new patient node, along with visit and clinicalTrial children (but this would violate c1 and c2), or (b) just add some visit and / or clinicalTrial children to a node that did not qualify for at least one of these predicates before (but this would again violate at least one of c1 or c2).

We also consider implication when the current tree instance (J), to which previous updates lead, is available. The corresponding implication problem is called instance-based implication.

Definition 2.5 (Instance-Based implication). Given a set of update constraints C, an instance J and a constraint c, we say that C implies c for J (denoted C |=J c) if for any tree instance I, we have (I, J) ⊢ C ⇒ (I, J) ⊢ c.

Considering the J instance and constraints of Example 2.1, the constraint

c = (/patient[/clinicalTrial]/visit, ↑)
is implied by {c3} and J. Let us consider what could have happened on an initial I instance in order to violate c: one could have completely removed from I a visit of some patient with clinicalTrial (this would violate c3); and one could have moved a visit of a patient with clinical-Trial below another patient without clinicalTrial (this is not possible because there is no such patient in the current instance, J). Observe that c would not be implied by c3 alone, i.e., for any pairs of instances.

The two implication problems capture different scenarios for data integrity. General implication is relevant in situations of data exchange or publishing when a publisher wants to decide a priori, regardless of the published data, what update restrictions should be imposed. Instance-based implication is relevant when someone obtains a document with update constraints and wants to understand the integrity properties of this data. It is easy to observe that the general constraint implication implies the instance-based one.

These problems abstract more practical ones such as deciding if some update can be safely performed or understanding the integrity properties of a query result. Instance-based implication can be viewed as verifying properties of the past, i.e., questioning the past evolution. Similarly, we could consider inference when the I instance is given, i.e., questioning the future evolution. The problem becomes somewhat analogous to the one we consider here, in some sense the symmetric in the future of the problem we consider about the past. Besides instance-based implication, other validity questions may be relevant when we consider data. For example, we could simply ask if a certain node could have been added to the result of a query, or could have been removed. Solutions to the above implication problem represent a first step towards inferring such richer, fine-grained assertions. A detail study of such aspects is left for future work.

On sequences of instances Observe that the current definition of validity and implication considers only pairs of instances and can only capture contexts of exchange among three parties (such as the one of Figure 1). However, in many other scenarios, it is also worth considering sequences of instances.

Let us consider a sequence (I0, . . . , I k ). We call it pairwise valid if each of its pairs (Ii, Ij), i < j, are valid according to Definition 2.3. When the last instance is fixed, we can give a more data-oriented definition of validity, one that only takes into account this last instance: we say (I0, . . . , I k ) is valid for I k if the pair (I0, I k ) is valid. Then, implication (in both flavors) for sequences would be defined based on the corresponding notions of validity. All the results presented in this paper, referring to pairs of instances, remain valid also for sequences. This becomes immediate from the definitions of pairwise validity and validity for I k . So, without any loss of generality, in the rest of the paper we will only refer to pairs of instances.

Notation We consider during our analysis various sub-fragments of XP {/, [], //, * }. They will be represented by the navigational primitives that are allowed. For instance, by XP {/, //} we denote paths without predicates and wildcards. To denote implication in restricted contexts, we use the notation |= X σ , where X is the XPath fragment we assume and σ ∈ {↑, ↓}. For example, |= XP {/,[]} ↑ denotes the constraint implication problem for no-remove constraints expressed in XP {/, []}. Similarly, we use |= X J,σ for instancebase implication in restricted contexts.

RELATED PROBLEMS

To further clarify the implication problems outlined in the previous section, we first consider some initial results relating them to previous work on topics such as the equivalence of path queries, regular XML keys and XML Integrity Constraints (XICs).

Query equivalence Since we rely on XPath queries to express update constraints, it comes as no surprise that XPath query containment and equivalence [START_REF] Schwentick | XPath query containment[END_REF] are tightly related to our implication problems. Regarding the relationship between query equivalence and implication, we can prove the following: Theorem 3.1. Given two constraints c1 = (q1, σ) and c2 = (q2, σ), expressed in XP {/, [], //, * }, we have c1 |= c2 (and symmetrically c2 |= c1) iff q1 ≡ q2.

Proof: [Sketch] Without loss of generality we assume that σ is ↑; the opposite type is analogous by symmetry. From the definition of implication, one directions is obvious (c1 |= c2 ⇐ q1 ≡ q2). Now suppose c1 |= c2. Suppose also that q2 q1, then there exists some tree I and node n such that n ∈ q2(I) and n / ∈ q1(I). We can easily obtain a contradiction to c1 |= c2 by the pair instances (I, I[n → n ′ ]), where by I[n → n ′ ] we denote the instance obtained by replacing n with a new node n ′ with the same label.

Regarding the other containment, if we assume q1 q2, then there exists some tree T ′ and node n ′ such that n ′ ∈ q1(T ′ ) and n ′ / ∈ q2(T ′ ). We can then obtain a contradiction to c1 |= c2 by a transformation as the one illustrated in Figure 3. In this figure, T is any tree with some node n in q2(T ). By putting together T and T ′ (i.e., merging their root nodes), the presence of n and n ′ in range queries is not affected in any way. In the transformation I → J we simply interchange n and n ′ . Since n and n ′ have the same label, by this transformation, we remove the node n from the result of q2, without removing anything from the result of q1.

T n n' T' T n' n T' n ∈ ∈ ∈ ∈ q 1 , n ∈ ∈ ∈ ∈ q 2 I J n' ∈ ∈ ∈ ∈ q 1 , n' ∉ ∉ ∉ ∉ q 2 n' ∈ ∈ ∈ ∈ q 1 , n' ∈ ∈ ∈ ∈ q 2 n ∈ ∈ ∈ ∈ q 1 , n ∉ ∉ ∉ ∉ q 2
A similar result can be proven for instance-based implication. So, in general, the implication problem, in both flavors, is at least as hard as query equivalence and containment2 .

To illustrate further the relationship of constraint implication with query containment and equivalence, let us consider a restricted setting in which all constraints have the same type (say ↑). As a sufficient approach for testing implication, we can state the following proposition, which follows from the definition of implication. Proposition 3.1. A constraint (q, ↑) is implied by a a set of ↑ constraints C if there exist some constraints c1, ..., c k in C, with their respective range queries q1, . . . , q k , s.t. q ≡ q1 ∩ ... ∩ q k . We will see further that, in some restricted cases, this condition of equivalence is also necessary (but only in restricted cases).

Regular XML key constraints Previous works addressed the implication problem for inclusion dependencies on semistructured data [START_REF] Buneman | Reasoning about keys for XML[END_REF][START_REF] Abiteboul | Regular path queries with constraints[END_REF][START_REF] Fan | Integrity constraints for XML[END_REF] and XML keys/foreign keys [START_REF] Arenas | Consistency of XML specifications[END_REF][START_REF] Fan | On XML integrity constraints in the presence of DTDs[END_REF], taking into account also schema information (such as DTDs). In particular, regular XML keys [START_REF] Arenas | Consistency of XML specifications[END_REF] have the form β.τ [X] → β.τ , for β being a regular expression over schema types and wildcard, τ being a schema type and X being a set of node attributes3 . The interpretation is that the tuple of X attributes represents a key for the path β, i.e., they uniquely determine nodes which are found on the path β. Similarly, a regular foreign key has the form β1.τ1[X] ⊆ β2.τ2[Y ], for X and Y being sequences of attributes of the same cardinality. Such constraints are said to be unary if they only refer to one attribute.

Given a set of key and foreign key regular constraints and a Document Type Definition (DTD) ( [START_REF]Extensible Markup Language 1[END_REF]), the consistency problem (defined in [START_REF] Arenas | Consistency of XML specifications[END_REF]) is asking whether there exists an XML document that conforms both to the DTD and the regular key constraints. (The exact definitions can be found in [START_REF] Fan | On XML integrity constraints in the presence of DTDs[END_REF][START_REF] Arenas | Consistency of XML specifications[END_REF].)

Although this constraint formalism is generally not comparable to our XPath-based formalism, regular key constraints can be used to express some of our update constraints. More precisely, they can express constraints described by only linear paths (i.e., no use of predicates). We can see node identifiers as being the only node attribute and pairs (I, J) as being the two main branches of a document. We need an unary key constraint to enforce uniqueness for node identifiers and one unary foreign key constraint for each update constraint. In fact, we show in Section 4 how constraint implication can be reduced to consistency in the presence of DTDs and unary regular constraints, even for queries with predicates.

XML Integrity Constraints (XICs) This is probably the richest formalism that has been proposed for expressing integrity constraints for XML data in terms of XPath expressions [START_REF] Deutsch | XML queries and constraints, containment and reformulation[END_REF]. An XIC is defined as follows: where A, B are conjunctions of atoms u = v or u p v, with p being a path step (such as /label, //label or /@attribute) evaluated at u which returns v.

While the implication problem for XICs has not been fully explored yet, implication under some limitations and query containment in the presence of such constraints have been considered in [START_REF] Deutsch | XML queries and constraints, containment and reformulation[END_REF]. In general, implication of XICs was shown to be undecidable. It becomes decidable for a tighter class, namely bounded XICs, which are XICs for which usage of // and attributes are not allowed under existential quantifiers, and the technique used is a classical inference technique, the chase [START_REF] Abiteboul | Foundations of Databases[END_REF].

First, our update constraints can be fully expressed by XICs, even in the instance-based setting. For that, it suffices to see a pair (I, J) of instances as a virtual document divided into two main branches, I and J. We just have to use an Id attribute, with no two nodes under the same main branch (I or J ) having the same Id value.

Unfortunately, the XICs needed to capture update constraints are not bounded because of both // axis and the Id attribute (it is existentially quantified). Indeed, we can exhibit very simple examples of constraint implication where the chase technique fails to terminate. So our contribution is also to show decidability and give complexity bounds for constraint implication in a family of unbounded XICs.

CONSTRAINT IMPLICATION

In this section we study constraint implication. Instancebased implication is the topic of the next section. We first give some intuition on how constraints of opposite types may interact (Section 4.1). Then, in Section 4.2, we study the complexity of the constraint implication problem. We first show that constraint implication is decidable, but with high complexity (NEXPTIME upper bound), although the tightness of this bound remains open. We then study complexity when restricting the expressivity of constraints. More precisely, there are two directions in which one can restrict constraints: (a) restrictions on the XPath fragment used, and (b) restrictions on the update types (for instance, only ↓ or only ↑), and we will consider both. The results of this section are summarized in Table 1.

Interacting types

As we will see, the interaction between no-insert and noremove constraints is surprising. For each such constraint type σ (↓ or ↑), and each set C of constraints, let C σ denote the constraints in C of type σ. A property that may seem rather intuitive is the following: It turns out that this is not true in general, as can be witnessed in the following example. imply c = (//b//a//c, ↑), while the no-remove constraints alone do not. For space reasons, the detailed explanation of this example is omitted.

So, when looking at the implication of constraints we need to take into account both update types. A restricted case where we can indeed limit to one type only is when we disallow the // axis. We can prove the following. The intuition behind the proof of this result is that we can exhibit a pair of instances that witnesses non-implication using some tree transformations.

Complexity of constraint implication

We first show that constraint implication is decidable in NEXPTIME. A coNP lower bound follows immediately from the fact that constraint implication is at least as hard as query equivalence (Theorem 3.1). Theorem 4.2. |= XP {/,[],//, * } is in NEXPTIME and co-NP-hard.

Proof: [Sketch] We solve the constraint implication problem by reducing it to the consistency problem for unary regular constraints and DTDs (described in Section 3). The main difficulty is to take into account predicates, which are not handled by such constraints. The crux is to transform normal labeled trees into annotated trees, where the label of a node describes precisely the predicates that can be matched below that node. (The predicates to be considered are only those occurring in constraints.)

In this way, instead of evaluating tree patterns with predicates on the normal tree, one can evaluate linear paths on the annotated tree and obtain the same result (modulo the modified labels). To avoid that annotations "lie" about the patterns that can be matched at a node, we control the correspondence between a node's annotations and its content by a specialized DTD (an extension of DTDs that decouples node labels and types; see, for instance, [START_REF] Papakonstantinou | DTD inference for views of XML data[END_REF]). Regarding its general structure, this DTD describes trees having 3 main branches, {I, J, witness}, where the witness gives one node that is removed or inserted in order to violate c. (1) in NEXPTIME coNP-hard coNP-hard coNP-hard

(1): if the number of constraints and the maximal number of wildcards between consecutive //'s are bounded by constants.

Table 1: Upper and lower bounds for the implication of constraints.

We reduce constraint implication to an instance of the XML consistency problem in which: (a) the DTD has exponential size, (b) the number of unary regular constraints is polynomial in the number of unary constraints, and (c) the size of unary regular constraints is exponential but each constraint can still be described by a deterministic finite-state automaton of only exponential size.

The consistency problem was shown to be solvable in 2-NEXPTIME [START_REF] Arenas | Design principles for XML data[END_REF]. More precisely, the complexity is (1) nondeterministic doubly-exponential in the number of regular constraints, and (2) only non-deterministic polynomial in the size of the product of their deterministic finite-state automata, and in the size of the DTD.

While this would lead to an 2-NEXPTIME upper-bound, the problem remains in NEXPTIME due to the limited type of inclusions we must handle (i.e., only between two main branches, I and J).

Given the high complexity of the above decision procedure, we consider in the following various restrictions on the expressivity of constraints, tracing a fairly tight borderline between tractable and intractable cases.

XPath fragment restrictions We start by restricting the XPath language. First, when predicates are not used, the general upper bound can be refined to NP, under two restrictions:

Theorem 4.3. |= XP {/,//, * } is in NP if the number of constraints and the maximal number of wildcards between two consecutive //'s are bounded by constants.

Proof: [Sketch] We use the same reduction from the XML consistency problem under unary regular constraints, which is simpler in the absence of predicates. As before, the DTD describes trees having the structure {I, J, witness}, where the witness contains one node that is removed or inserted in order to violate c. Now, our update constraints can be modeled as a deterministic automata of only polynomial size 4 . Again, the upper bound benefits from the limited type of inclusions we consider (i.e., only between I and J), instead of arbitrary ones.

Next, moving from an XPath fragment without predicates to one without // axis or wildcard, we can prove that finding an equivalence with some intersection of ranges is not only a sufficient condition (by Theorem 3.1) but also a necessary one. This will translate into a PTIME decision algorithm for XP {/, [], * }. We remind that we already know that, for this fragment, we can safely limit to only one constraint type, ↓ or ↑ (by Theorem 4.1).

Theorem 4.4. Given a set of constraints C all with update type σ and a constraint c = (q, σ), all expressed either in XP {/, [], * } or XP {/, [], //} we have C |= c iff there exist constraints c1, ..., c k ∈ C with respective ranges q1, . . . , q k , s.t. q ≡ q1 ∩ ... ∩ q k . Proof: [Sketch] We can assume w.l.o.g. no-remove constraints; the opposite type is analogous by symmetry. One direction (sufficiency) was already discussed (Proposition 3.1). The other direction is proven by induction on the number of no-remove constraints. (We already proved the statement for one no-remove constraint in Theorem 3.1.)

Once we know that equivalence is also a necessary condition, a naive decision procedure is to just look for a combination of range queries having their intersection equivalent to the to-be-implied range. We can avoid such an expensive search by taking all the range queries qi such that q ⊆ qi (testable in polynomial time [START_REF] Miklau | Containment and equivalence for an XPath fragment[END_REF]), and then test if q ≡ ∩iqi. While the fragment XP {/, [], * } is closed under intersection and the intersection of queries can be computed in linear time, it remains open if the same can done for the fragment XP {/, [], //}. It can be easily checked that the latter fragment is not closed under intersection.

From Theorems 4.1 and 4.4 we obtain that:

Theorem 4.5. |= XP {/,[], * } is in PTIME.
Finally, regarding lower-bounds for the discussed XPath fragments, we can show that implication remains coNPhard when predicates or wildcard are combined with descendant axis.

Theorem 4.6. |= XP {/,[],//} and |= XP {/,//, * } are coNPhard.

We reduce from the unsatisfiability of 3SAT formulas.

One type restrictions

We next consider restricting the type of constraints, more precisely assuming that all constraints have one same type. Observe that the problems |= ↓ and |= ↑ are equivalent by symmetry, so in general only one of them will be discussed (we denote this by the generic notation |=σ). We first show that under the one-type restriction, constraint implication becomes solvable in coNP time. Proof: [Sketch] We show that if there exists a pair (I, J) that is a contradiction for implication, we can find another one, (I ′ , J ′ ), of polynomial size in C and c with the same property (we call this the small instance property). The size of (I ′ , J ′ ) will depend on that of c and C, and in particular on the maximal star-length of ranges 5 . We first apply a number of pruning steps on J, while maintaining the witness property. After obtaining a J ′ instance of polynomial size in size of c and the maximal star-length from ranges, we apply similar pruning steps to the I instance. The pruning steps are complex and for space reasons not presented here. In conclusion, we can guess in polynomial time a pair of instances that witnesses non-implication.

We next show that if we now restrict the XPath fragment, by disallowing predicates, constraint implication becomes solvable in PTIME. We show the following:

Theorem 4.8. |= XP {/,//, * } σ
is in PTIME if the number of constraints and the maximal number of wildcards between consecutive //'s are bounded by constants.

Proof: [Sketch] The proof is based on finite state automata techniques. First, if we assume that implication does not hold and a counterexample exists, it is immediate that we can limit to looking for pairs of trees contradicting C |= c that are made only of linear paths (i.e., nodes have at most one child). Then, for any constraint c, the range can be modeled as a deterministic automaton of polynomial size (denoted Ac). Hence, the complement of a range can also be modeled by a deterministic automaton of polynomial size (denoted A¬c). We then look at products of such automata, and there are polynomially many products to be considered if the number of update constraints is considered fixed.

INSTANCE-BASED IMPLICATION

We study in this section instance-based implication. Given a set of constraints and a current tree instance, we want to check if other constraints are implied. Unless specified otherwise, when we mention complexity, we mean combined complexity, i.e., in the size of c, C and J. The results of this section are summarized in Table 2.

First, similar to constraint implication, we can show that instance-based implication is at least as hard as query containment and equivalence. So when all navigational primitives are used, even with only one update type, instancebased implication is coNP-hard. Next, we show that this lower bound is tight, by showing that we can guess a counterexample pair of instances in polynomial time.

Theorem 5.1. |= XP {/,[],//, * } J is coNP-complete.
Proof: [Sketch] We show that we have a small instance property; more precisely, if there exists an instance I such that the pair (I, J) is a contradiction for implication, we can find an instance I ′ of polynomial size in |J| and |C| with the same property. We apply a number of pruning steps on I, making sure to preserve at each step the witness property of the pair. The size of the resulting I ′ will depend in particular on the maximal star-length of ranges.

Next, we show that, even for classes where the implication problem is tractable, instance-based implication may become intractable.

We show that when no-remove and no-insert constraints are used together, the problem becomes coNP-hard for fragments on which general implication was in PTIME. (We note that some of the hardness results of fragments with wildcard are obtained without making use of this primitive. For brevity of presentation, the cases with and without wildcard are grouped together in Table 2.)

Theorem 5.2. |= XP {/,[]} J and |= XP {/,//} J are coNP-hard.
The proof is by reduction from the unsatisfiability of 3SAT formulas. Intuitively, the hardness comes from the fact that we can affect c (without affecting the constraints of C) by permuting data from J, and the moves to consider are exponentially many. Hence we have an exponential search space in which we need to find a "previous" instance I such that (I, J) ⊢ C but (I, J) c.

In order to trace the tractability boundary, we state without proof that for the most restricted fragment, XP {/}, instance-based implication is in PTIME.

Since one cannot obtain tractability by imposing reasonable XPath restrictions, we next consider restricting the update types. More precisely, we consider instance-based implication when all constraints (both of C and c) have the same constraint type. We begin with no-insert constraints, looking first at the fragment XP {/, [], * }.

Theorem 5.3. |= XP {/,[], * } J, ↓ is in PTIME.
Proof: [Sketch] Let C = {(qi, ↓)} and c = (q, ↓). We will construct in PTIME an instance F (J) such that C J c iff (F (J), J) contradicts C c. This instance will contain all the certain facts that can be obtained from data and constraints. We build F (J) as follows. Initially, F (J) is just root. Then, for each constraint (qi, ↓) and each node n ∈ qi(J), we add to F (J) a tree having the structure of the range qi. This tree will have the actual n as the distinguished node and nodes with fresh identifiers for the other query nodes. We put a fresh label (z) for wildcard nodes.

We then take the trees obtained at the previous step, identify nodes with the same Id, and merge respectively their ancestors. We use the following policy for the node identifiers: when two merged nodes have both fresh identifiers, the merged node gets one of them arbitrarily. When one of them has an original label (i.e., a label appearing in C), the merged node gets this label. If one of the nodes has an original Id (i.e. one from J) the merged node gets this Id. It should be noted that no conflicts may arise in the above merging process, namely it cannot be the case that we need to merge two nodes that both have original identifiers, merged nodes will not have different original labels, and no paths of different structures will need to be merged.

Once F (J) is obtained, we rely on the following claim: C J c iff q(J) contains some node that does not belong to q(F (J)). For space reasons, the proof of the claim is omitted.

The same upper bound can be obtained for XP {/, //, * } under restrictions similar to those of Theorem 4.8: (2) in PTIME (2) in PTIME (2) The proof is almost identical to that for general implication in this fragment (Theorem 4.8).

We now consider the opposite update type, no-remove. We show that, under no fragment restrictions, we obtain a tractable solution in the size of J and C, though exponential in that of c. Proof: [Sketch] Let c = (q, ↑). We show that we can test implication while limiting to I instances that have the "shape" of q. (The construction is similar to the one used in the proof of Theorem 4.7.)

Given an instance I, query q such that q(I) is not empty, and a node n ∈ q(I), we say a node n ′ ∈ I is redundant for n and q if n ∈ q(I ′ ), where I ′ is the tree obtained from I by removing the subtree rooted at n ′ .

We say that an instance I is a possible embedding of q if it satisfies the following conditions (stated informally):

(1) there is a homomorphism from q to I that preserves the parent-child (for / axis) and ancestor-descendant (for // axis) relationships among nodes, the labels of query nodes that are not wildcards, and the root node, (2) for some n ∈ q(I), there are no redundant nodes for n and q, (3) the nodes of I that are matched (in the evaluation of q yielding n) only to query nodes labeled by wildcards have a fresh label z, and (4) all the paths in I that are matched in this evaluation to a // in the query are sequences of (m + 1) nodes labeled z, for m being the maximal star-length of ranges.

The proof is based of the following observation:

C J c iff there is a previous tree instance I such that

• (I, J) ⊢ C (i.e. all the range sets are subsets of the ones in J),

• I is a possible embedding of q in which we assign to nodes that are not labeled z either Ids from J or fresh Ids,

• and q(I) q(J).

We can enumerate all the possible embeddings by taking the tree pattern representation of q and (1) assigning to wildcard nodes either a label occurring in data or constraints, or the special z label, (2) merging some nodes having the same label, and (3) deciding on how the remaining ones are ordered (i.e., choosing the child/parent and ancestor/descendant relationships that are not already given by q and don't contradict q).

The number of nodes that are not labeled z is at most |q|. The number of possible embedding depends only on q (it does not depend on maximal star-length), and is at most exponential.

From the above observation we can derive a naive enumeration algorithm for testing if C |=J c. The number of Id assignments is bounded by (|J| + 1) |q| , so polynomial in |J|, although exponential in |q|.

For the same setting, i.e., only no-remove constraints, we can also prove coNP hardness even for the sub-fragments XP {/, []} and XP {/, //, * }.

Theorem 5.6. |= XP {/,[]} J, ↑ |= XP {/,//, * } J, ↑ are coNP-hard.
The proof uses a construction similar to that of Theorem 5.2. Details are omitted.

RELATIVE CONSTRAINTS

We briefly consider in this section relative constraints. For instance, while we imposed in Example 2.1 that the overall set of visits can only increase, we cannot require that the visits of each individual patient element can only increase as well. This form of update restriction can be expressed by introducing a scope over which constraints are specified. More precisely, we would express the above restriction on visits by the relative constraint:

(/patient, /visit, ↑)

As already noted in previous works on XML integrity constraints, such relative constraints are particulary suited for hierarchically structured data. For instance, keys that are relative to a node type were introduced in [START_REF] Fan | On XML integrity constraints in the presence of DTDs[END_REF].

A possible model extension to relative update constraints could be the following: Definition 6.1 (Syntax). A relative XML update constraint is an expression of the form (qs, qr, σ), where qs, qr are queries called the scope and the range , and σ is the constraint kind, i.e., one of no-insert (in short ↓) or no-remove (in short ↑). Definition 6.2 (Semantics). We say a pair of trees (I, J) is valid with respect to some relative constraint c = (qs, qr, σ) (denoted by (I, J) ⊢ c) if for all x in qs(I) ∩ qs(J) we have qr(x, I) ⊆ qr(x, J) (resp. qr(x, J) ⊆ qr(x, I)) when σ is no-remove (resp. no-insert). Also, with relative constraints, implication for sequences and for pairs are not necessarily equivalent, as we can easily exhibit sequences in which consecutive pairs are valid but the overall sequence is not. To address this drawback, some soundness requirements could be imposed on constraints.

Regarding complexity, although in the case of constraint implication one should expect complexity to increase, we believe that upper-bounds for instance-based implication should not be affected, and that most of our proofs can be extended to deal with scopes. It seems on the other hand that such an extension with scopes may have a very serious impact on the constraint implication problem. Indeed, it is not even clear whether the problem is still decidable. Implication for relative constraints remains mostly open and is a direction we intend to follow in future work.

CONCLUSION

We introduced in this paper a family of update constraints for XML data. We studied general constraint implication, i.e., for all possible instances, and instance-based implication, i.e., in the presence of a current tree instance. Our work was motivated by contexts of exchange or publishing where data has update constraints but no history of updates is maintained. In particular, the constraints considered here could be enforced by existing digital signing techniques [START_REF] Rivest | Two signature schemes[END_REF][START_REF] Devanbu | Authentic third-party data publication[END_REF][START_REF] Abiteboul | Digital signatures for modifiable collections[END_REF][START_REF] Bellare | Incremental cryptography: The case of hashing and signing[END_REF][START_REF] Johnson | Homomorphic signature schemes[END_REF]. In the reminder of the section we consider additional related work and open questions.

Instance-based implication is related to representing and querying incomplete information (e.g. [START_REF] Abiteboul | Representing and querying XML with incomplete information[END_REF]). One may consider representing a document which is subject to controlled modifications by a combination of certain and possible facts, describing which parts may have changed and how. However, the results of [START_REF] Abiteboul | Representing and querying XML with incomplete information[END_REF] can not be applied directly to our XPath-based setting -the work in [START_REF] Abiteboul | Representing and querying XML with incomplete information[END_REF] uses a different query semantics where queries return, besides the result nodes, also the full root to node path. The instance-based flavor of implication is also related to query answering in XML data exchange [START_REF] Arenas | XML data exchange: consistency and query answering[END_REF]. Intuitively, one could see update constraints as source-to-target dependencies. The analogy does not fully go through because we do not consider DTDs and we can also have target-to-source dependencies. Some of our constraints can be expressed by first-order formulas with 2 variables over unranked, ordered trees with data values. The logic F O 2 (∼, <)6 over trees was proven decidable in [START_REF] Bojanczyk | Two-variable logic on data trees and XML reasoning[END_REF]. However, this logic captures only update constraints without // axis and the complexity of implication is high.

Several open problems and future work directions were identified throughout the paper. In particular, we highlighted a number of open issues regarding relative constraints. Also, tighter complexity bounds are open for some of the studied problems. Other future directions have to do with richer XPath fragments and "static" integrity constraints (such as keys and foreign keys [START_REF] Fan | Integrity constraints for XML[END_REF][START_REF] Buneman | Reasoning about keys for XML[END_REF]) and schema information, which are often available for XML data. It is important to understand the role they play in update constraint implication. Note that we assume an update language where nodes may also be moved around. So, in two "consecutive" instances, the same node may appear in totally different parts of the document. However, in some settings, parent-child relations may not be modifiable, and as a consequence one cannot move a node from one parent to another. We leave the study of such "no-move" constraints for future work.

Regarding the instance-based context, besides the studied implication, a more fine-grained language for data validity assertions and temporal reasoning may be worth considering. Also, for both implication problems, as some cases where proven difficult, it may be useful to consider sound approaches. For instance, we could build on the sufficient test of general implication, by taking into consideration only some data properties.

Figure 1 :

 1 Figure 1: Exchange with update constraints (C).

  path ::= /step | //step | path path step ::= label pred pred ::= ǫ | [path] | pred pred label ::= L | * By / we denote child axis navigation. By // we denote descendant axis navigation. L denotes labels and * is the wildcard label. The path inside brackets is called a predicate. Queries have one distinguished output node. For example, the b node is the output node of the query /a//b[/c].

Figure 2 :

 2 Figure 2: Pair of instances (I, J).

Figure 3 :

 3 Figure 3: Counterexample pair of instances (I, J).

∀

  xi, . . . , xn A(x1, . . . , xn) → ∃ y1, . . . , ∃ ym B(x1, . . . , xn, y1, . . . , ym)

[

  Same-type property] For a constraint c of type σ and any set of constraints C, we have C |= c iff C σ |= c.

Example 4 . 1 .

 41 The following constraints: • (c1) : (//a//c, ↑) • (c2) : (//b//c, ↑) • (c3) : (//a//b//c, ↓) • (c4) : (//a//b//a//c, ↑) • (c5) : (//b//a//b//c, ↑)

Theorem 4 . 1 .

 41 For any constraint c of type σ and any set of constraints C, all expressed in XP {/, [], * }, we have C |= c iff C σ |= c.

Theorem 4 .

 4 7. |= XP {/,[],//, * } σ is in coNP.

Theorem 5 .

 5 5. |=XP {/,[],//, * } J, ↑ can be decided in time polynomial in the size of J and C, exponential in that of c.

Example 6 . 1 .

 61 We next briefly discuss what changes or may change when we have relative constraints. First of all, we can easily exhibit examples (see Example 6.1 below) showing that the same-type property of Section 4.1 is no longer true even for XP {/, []} (it was proven true for the fragment XP {/, [], * } in Theorem 4.1). Given the constraints C:• c1 = (/patient, ↓) • c2 = (/patient, /visit, ↓) • c3 = (/patient/visit, ↑),the constraint c = (/patient[/visit], ↑) is implied by C, although it is not implied by the only no-remove constraint (c3) alone.

Table 2 :

 2 Upper and lower bounds for the instance-based implication of constraints.

		coNP-hard	coNP-hard	coNP-hard
	arbitrary update types	in PTIME coNP-complete coNP-complete	coNP-complete
	(1): if the number of constraints and the maximal number of wildcards between consecutive //'s
	are bounded by constants.
	(2): if the size of c is bounded by a constant.

Other aspects of the XML data model[START_REF]Extensible Markup Language 1[END_REF] such as data values (text content) or attribute values can be considered as being part of the node label.

Query equivalence and containment were shown to be coNP-hard in[START_REF] Miklau | Containment and equivalence for an XPath fragment[END_REF] (see also[START_REF] Schwentick | XPath query containment[END_REF]) for XP {/, [], //, * }; the proof of this lower bound uses only concrete paths.

Attributes can be seen as nodes that are uniquely identified by their label for each parent node.

The deterministic finite-state automaton that describes a linear path has exponential size only in the maximal number of wildcard nodes between two consecutive // edges (see[START_REF] Green | Processing XML streams with deterministic automata[END_REF]).

The star-length of a path denotes the maximal length of a chain of wildcards occurring in the path (this notion was introduced by[START_REF] Miklau | Containment and equivalence for an XPath fragment[END_REF]).

∼ is a predicate that checks equality of two data values (such as the Id attribute), while < refers to two relations, for parent/child and sibling.

Acknowledgments. We would like to thank Alin Deutsch and Luc Segoufin for helpful discussions and comments.


Marie-Lou Barnaud
email: marie-lou.barnaud@gipsa-lab.grenoble-inp.fr

Jean-Luc Schwartz

Julien Diard

Pierre Bessière

Sensorimotor learning in a Bayesian computational model of speech communication

Although sensorimotor exploration is a basic process within child development, clear views on the underlying computational processes remain challenging. We propose to compare eight algorithms for sensorimotor exploration, based on three components: "accommodation" performing a compromise between goal babbling and social guidance by a master, "local extrapolation" simulating local exploration of the sensorimotor space to achieve motor generalizations and "idiosyncratic babbling" which favors already explored motor commands when they are efficient. We will show that a mix of these three components offers a good compromise enabling efficient learning while reducing exploration as much as possible.

I. INTRODUCTION

Acting efficiently in the environment requires a precise knowledge of the relationship between motor commands and sensory outputs. Cognitive theories of motor control as well as computational approaches in robotics generally consider that agents have at their disposal internal models linking motor and sensory information [START_REF] Kawato | Internal models for motor control and trajectory planning[END_REF]. There are two kinds of internal models: forward and inverse models. To implement a forward model, cognitive or computational agents have to learn to predict the sensory output s corresponding to a given motor command m. Conversely, within an inverse model, agents must learn to select motor commands m corresponding to a given sensory output s.

Sensorimotor learning, for either forward or inverse models, typically involves sensorimotor exploration supposed to occur at an initial stage in child development, and accordingly called "babbling". Exploration enables the agent to visit parts of the sensorimotor environment, so as to be able to learn the association between sensory and motor variables inside the visited regions, and to hopefully be able to generalize the learned patterns to other regions of the sensory or motor space. The key question in this process is to select adequate regions to explore, so as to make the learning process as rapid and efficient as possible.

There are two main families in sensorimotor exploration algorithms: motor and goal babbling. In motor babbling, the agent selects a motor command m and observes its sensory effect s. In goal babbling, the agent selects an effect s and tries to find a motor command m able to generate this effect. This research can be performed by some kind of estimation process, like inference [START_REF] Moulin-Frier | Exploration strategies in developmental robotics: a unified probabilistic framework[END_REF] or optimization [START_REF] Rolf | Goal babbling permits direct learning of inverse kinematics[END_REF]- [START_REF] Murakami | Seeing [u] aids vocal learning: babbling and imitation of vowels using a 3d vocal tract model, reinforcement learning, and reservoir computing[END_REF], among others.

Both approaches can be decomposed in two steps: element selection and learning. In the first step, the agent selects an element to learn: a motor command m in motor babbling or a sensory percept s in goal babbling. The choice of adequate elements to select in order to increase learning speed and accuracy is crucial. Indeed, selection can be random but a number of studies show that a thoughtful choice can considerably improve learning [START_REF] Moulin-Frier | Exploration strategies in developmental robotics: a unified probabilistic framework[END_REF], [START_REF] Baranes | Intrinsically motivated goal exploration for active motor learning in robots: A case study[END_REF], [START_REF] Rolf | Autonomous development of goals: From generic rewards to goal and self detection[END_REF].

This choice can be made internally according to criteria decided by the agent, or externally tuned by a master or by social guidance. Internal criteria should enable the agent to develop adequate sensorimotor exploration according to considerations about the interest of some regions of the space, e.g. for improving the performance of the internal models or to increase the knowledge of the possible relationships between motor and sensory variables [START_REF] Baranes | Intrinsically motivated goal exploration for active motor learning in robots: A case study[END_REF], [START_REF] Baranes | Active learning of inverse models with intrinsically motivated goal exploration in robots[END_REF].

Social guidance uses the experience of other agents to guide learning. For instance, selection can be supervised by an imitation process during which a learning agent tries to reproduce elements provided by a teacher agent.

Another dimension characterizing the selection step concerns whether or not it is influenced by previously selected items. When it is the case, it is called active learning [START_REF] Baranes | Active learning of inverse models with intrinsically motivated goal exploration in robots[END_REF], [START_REF] Saegusa | Active learning for multiple sensorimotor coordination based on state confidence[END_REF].

After the selection step, an (m, s) pair is available. It is used by the agent to update parameters of its internal models; this is the learning step proper.

Despite its apparent simplicity, sensorimotor exploration is a challenging problem, particularly if the sensorimotor space to explore is dimensionally large. In this paper, in the context of sensorimotor exploration in speech communication, we present a new algorithm called accommodation goal babbling (AGB) under social guidance by a master. We also introduce two additional mechanisms likely to improve exploration and learning: local extrapolation which generalizes sensorimotor observations to a neighborhood of each selected motor command, and idiosyncratic babbling which aims at favoring motor commands that are already known to efficiently approximate the selected sensory goal.

We evaluate the efficiency of the three proposed components, in comparison with classical sensorimotor exploration algorithms, around three questions:

• Does the AGB algorithm efficiently learn the motor-tosensory relationship in the portions of the sensory space provided by the master? • Does local extrapolation improve learning?

• Does idiosyncratic babbling improve learning? The proposed algorithms are implemented in the framework of a Bayesian model of speech communication, named COSMO, in which we study the learning of the relationship between articulatory motor gestures and their corresponding auditory outputs (typically formants of an auditory signal).

In Section II, we detail the different algorithms. In Section III, we present the Bayesian model COSMO and provide implementation details. In Section IV, we describe experimental results of the comparison of the algorithms we study. Finally, we discuss these results and give some limitations and possible improvements in Section V.

II. SENSORIMOTOR LEARNING

Within a Bayesian framework, we consider a motor space M composed of motor commands m and a sensory space S composed of sensory percepts s; both spaces are described as probabilistic variables. Learning agents are defined by the joint probability distribution P (S M ), decomposed as a product of a forward internal model P (S | M ) and a prior distribution on motor gestures P (M ). We note Prod the algorithm that performs the transformation from a motor gesture m to a sensory percept s: s = Prod(m) .

(

) 1
Prod is the "ground-truth" transformation that learning agents aims at identifying. In this paper, we implement altogether eight algorithms, all based on the two steps described before: selecting an element to learn and determining a method to learn it.

A. Random motor babbling and random goal babbling

We first propose two exploration-by-babbling algorithms providing a baseline for further comparisons. In the random motor babbling (RMB) algorithm, the agent selects a uniformly random motor command m. In the random goal babbling (RGB) algorithm, the agent selects a uniformly random sensory percept s. Then, it infers a motor command m thanks to P (M | [S = s]) where:

P (M | [S = s]) ∝ P (M )P ([S = s] | M ) . (2)
In both cases, the agent then "performs" m, which is transformed by Prod (Eq. 1), resulting in a sensory output s . This provides a couple m, s , which enables the learning agent to update its forward model P (S | M ).

Notice that this implementation of RGB follows a recent definition of goal babbling [START_REF] Moulin-Frier | Exploration strategies in developmental robotics: a unified probabilistic framework[END_REF], that does not use a distance measure to compare s and s , contrary to previous versions [START_REF] Rolf | Goal babbling permits direct learning of inverse kinematics[END_REF], [START_REF]Online goal babbling for rapid bootstrapping of inverse models in high dimensions[END_REF]. Indeed, the agent just modifies its forward model based on the observed m, s couple whatever the success of the inference process (described in Eq. ( 2)). This opportunistic behavior will also be a crucial component of the accommodation algorithm introduced in the next section.

B. Accommodation and idiosyncratic goal babbling

The proposed algorithm, called accommodation goal babbling (AGB), can be seen as goal babbling with social guidance. The agent receives a sensory stimulus s provided by the master. Then, the inference and learning processes are identical to the ones in the random goal babbling algorithm. We expect that the agent should first draw motor commands uniformly randomly at the beginning of the learning process. Then, it should progressively focus on sensory stimuli provided by the master and only improve its forward model around the corresponding sensory regions.

On this basis, we add an "idiosyncratic babbling" component. The model, called idiosyncratic goal babbling (IGB), is exactly the same as the previous one (AGB) except that once the m, s couple is obtained, the agent updates not only its forward model P (S | M ) thanks to the couple m, s , but also its prior distribution of motor gestures P (M ) thanks to m. We expect that motor exploration should focus around adequate motor commands already selected, and therefore convergence could be quicker, by keeping an already found good motor solution (possibly idiosyncratic, that is, different from one agent to another), rather than searching for all possible solutions1 .

C. Local extrapolation

Finally, we explore a variant of each of these four algorithms incorporating a "local extrapolation" component. This consists in updating P (S | M ) with couples m i , s at each learning step, where m i corresponds to several motor commands in the neighborhood of m, and where s is the sensory output computed with Prod for m. We expect that local extrapolation should increase the speed and efficiency of exploration around the target regions provided by the master by providing motor generalization around the explored motor regions, at the cost of potential inaccurate local learning. Indeed, associating m i with s might be incorrect with respect to Prod; the larger the generalization neighborhood volume or the less smooth Prod around m, the greater this inaccuracy. We hence obtain four new algorithms with this variant: RMB-LE (for RMB with Local Extrapolation), RGB-LE, AGB-LE, and IGB-LE.

III. APPLICATION TO A BAYESIAN MODEL OF

COMMUNICATION

In this paper, we focus on sensorimotor exploration occurring during speech development. More specifically, the algorithms we compare are incorporated into a Bayesian model of communication named COSMO (for "Communicating Objects using Sensory-Motor Operations") that we have been developing in the last years. This model has already been applied to the emergence of sound systems in human languages [START_REF] Moulin-Frier | Communicating about Objects using Sensory-Motor Operations"): A Bayesian modeling framework for studying speech communication and the emergence of phonological systems[END_REF], the study of speech perception in adverse conditions [START_REF] Moulin-Frier | Adverse conditions improve distinguishability of auditory, motor, and perceptuo-motor theories of speech perception: An exploratory Bayesian modelling study[END_REF], [START_REF] Laurent | A computational model of perceptuo-motor processing in speech perception: learning to imitate and categorize synthetic CV syllables[END_REF], and it is currently expanded towards modeling speech production [START_REF] Patri | Optimal speech motor control and token-to-token variability: a bayesian modeling approach[END_REF]. Here, we only implement the portion of the COSMO model involving sensorimotor exploration and we test our algorithms in the context of learning vowel production.

A. Model definition

The motor space M corresponds to articulatory configurations of the vocal tract. Configurations and commands are defined from a realistic articulatory model of the vocal tract, called VLAM (for "Variable Linear Articulatory Model") [START_REF] Maeda | Compensatory articulation during speech: Evidence from the analysis and synthesis of vocal-tract shapes using an articulatory model[END_REF]- [START_REF] Ménard | Auditory normalization of French vowels synthesized by an articulatory model simulating growth from birth to adulthood[END_REF], which can transform configurations of articulatory positions into sounds. Each configuration is described by seven parameters, but only three are essential to model vowels: lip height (L H ) controlling the distance between the lips, tongue body (T B ) corresponding to the advancement/retraction of the tongue, and tongue dorsum (T D ) controlling the tongue height.

Sensory percepts S are described by components of the acoustic signal, called formants, corresponding to frequency peaks of the signal spectrum. We keep only the two first formants, F 1 and F 2, which are essentially sufficient to characterize vowels.

The motor and sensory spaces are discretized, so that sensorimotor exploration occurs inside a motor space M containing 15,625 articulatory positions (25*25*25) and a sensory space S containing 4,703 (59*73) couples of formants F 1, F 2 . In a realistic fashion, there are more motor than sensory configurations and different motor configurations may result in the same sensory effect (this is referred to as the "manyto-one problem").

As described in Section II, learning agents have a forward model P (S | M ) and a prior about motor commands P (M ). The conditional probability distribution P (S | M ) is defined by a set of Gaussian distributions2 :one for each motor gestures, that is, 15,625 Gaussian distributions, with a mean µ and a covariance matrix Σ for each distribution. µ is initialized in the middle of the sensory space and with a large variance, so as to approximate a uniform distribution. In the RMB, RGB, AGB and IGB algorithms, P (S | M ) is updated with the couple m, s at each learning step. This update is weighted by a constant value equal to 1. In algorithms with local extrapolation (RMB-LE, RGB-LE, AGB-LE and IGB-LE), P (S | M ) is updated at each learning step with a set of couples m i , s , which are also weighted: weights follow a Gaussian distribution around mean m with a small variance. This allows fair comparison between variants with and without local extrapolation: both receive experimental observations weighted, overall, by 1, and this unitary weight is concentrated in a single m value without local extrapolation, and spread over the neighborhood of m with local extrapolation.

In IGB and IGB-LE, the prior P (M ) is represented by a histogram over the 15,625 motor values, with one bin for each motor value. This histogram is initialized as uniform with an initial frequency f i and updated with a weight 1 for each incoming observation, at each learning step. We tested f i for three values : 1, 0.1 and 1/15625. In all other algorithms, P (M ) does not change from a uniform distribution.

B. Selection and production phases

Motor commands and sensory percepts are uniformly randomly selected respectively in the motor babbling RMB/RMB-LE and the goal babbling RGB/RGB-LE algorithms. On the contrary, AGB/AGB-LE and IGB/IGB-LE algorithms use the sensory goals s provided by a master. More precisely, the master follows a probability distribution of sensory percepts corresponding to the vowels /a, i, u/ (e.g. in American English, /a/ as in "far", /i/ as in "feed" and /u/ as in "food"). We choose these vowels as they correspond to vowels present in nearly all languages [START_REF] Schwartz | The dispersionfocalization theory of vowel systems[END_REF].

C. Experimental evaluation

We simulate sensorimotor exploration for 100,000 learning steps. At the end of the learning process, we evaluate our algorithms in two manners: quality of learning and amount of exploration.

Quality of learning is assessed by the capacity of the learning agent to reproduce sounds provided by its master. This aims at checking that the agent has learned the forward model P (S | M ) accurately in the useful sensory regions, that is, where vowels lie. Therefore, a confusion matrix P (S prod | S given ) is computed, in which S given is a given sound to reproduce and S prod is the sound achieved by the agent at the end of a given sensorimotor learning algorithm, when it tries to reproduce S given . This matrix can be computed with Bayesian inference:

P (S prod | S given ) = M P (S prod | M )P (M | S given ) , (3)
where P (S prod | M ) is the real production system in the environment, computed thanks to the VLAM model, and P (M | S given ) is the inversion of the forward model of the learning agent. Thereafter, we only conserve the diagonal of the confusion matrix, noted Diag ConfMat , giving for each sensory value the probability that it is correctly reproduced. From Diag ConfMat evaluated at each learning step, we look at sensory values drawn according to the master distribution and compute their weighted average providing an accuracy measure. The contrary probability gives us an error measure.

For quantifying exploration, we count the number of different selected motor commands m to assess the relative volume of the motor space explored during learning. For algorithms with local extrapolation (RMB-LE, RGB-LE, AGB-LE and IGB-LE), we consider that neighborhood exploration does not increase this count since the total volume of local explored configurations was controlled to count for 1 (see Section III-A).

IV. RESULTS

Let us describe how accommodation, idiosyncratic babbling and local extrapolation affect both quality of learning and the amount of exploration during sensorimotor learning.

A. Accommodation: comparing AGB with RMB and RGB

Let us first compare the AGB algorithm to RMB and RGB. We display the evolution of the error measure during learning for each algorithm (colored dotted lines in the top of Figure 1). We observe that, although error measures all appear to converge towards zero, convergence is quicker for RGB (around 45,000 learning steps) than for AGB (around 80,000 learning steps ) and for RMB (approaching convergence at the end the 100,000 simulated learning steps).

In terms of exploration, we compare the number of selected motor commands m for the three algorithms during learning (colored dotted lines in the bottom of Figure 1). Overall, the three algorithms explore all the motor space M at the end of the learning phase, though a little faster, that is with more exploration, at each step for RGB.

Let us now focus on the portions of the motor space explored during learning. As a reference, consider the distributions of the sensory stimuli provided by the master (top left of Figure 2); there are three regions of the sensory space with high probabilities, that correspond to the three vowels /a, i, u/ (/i/ on the top left, /a/ on the bottom and /u/ on the top right).

Then, we display the values of Diag ConfMat for all sensory values at the end of learning simulations (top right and bottom Values spread from dark blue (low probability) to red (high probability) plots of Figure 2). Non-zero values form a rounded triangle in the sensory space. This corresponds to the classical vocalic space, that is, the portion of the sensory space which can be produced by motor gestures. In this area, the AGB algorithm is especially efficient on regions corresponding to the master's stimuli, with high probability in the areas corresponding to /a/ and /i/, and to a lesser extent for /u/. The RMB and RGB algorithms are naturally more diffuse since they do not rely on the master's guidance. Interestingly, they focus more on the left part of the vocalic space, especially RMB. This suggests that right portions of the sensory space are harder to learn: there are more motor gestures corresponding to the left portions of the vocalic space (probably due to redundancy in the motor space). Therefore, vowels /a/ and /i/ are easier to find than /u/, which probably explains why the AGB algorithm displays higher probability on the two vowels /a/ and /i/.

The proposed interpretation is that, at the onset of learning, all algorithms first explore more or less randomly the motor space in the same way until around 20,000 learnings steps. As more motor gestures correspond to the left portion of the vocalic space, they have higher probability in this area. Then, RGB continues to explore randomly and constantly improves its performance, resulting in Figure 1 in a linear decrease of error towards convergence. At the end of learning, it is efficient on the whole vocalic space but keeps higher performance on the left area, that was more explored in the initial learning phase (Figure 2). Meanwhile, the AGB algorithm succeeds to focus on the master's portions of the space, which reduces its exploration but somewhat slows down its error decrease (Figure 1). Finally, since the RMB algorithm randomly selects motor gestures, it has to deal with the redundancy of the motor space, hence it becomes efficient on highly redundant portions of the space but decreases slowly its error on the remaining space (Figures 1 and2).

In summary, the AGB algorithm succeeds to focus on the master's sensory stimuli. However, it obtains similar performance as the RGB and RMB algorithms at the end of learning, and it actually converges more slowly than the RGB algorithm.

B. Local extrapolation: comparing RMB, RGB, AGB with RMB-LE, RGB-LE, AGB-LE

The top plot of Figure 1 also shows error during learning for the three variants RMB-LE, RGB-LE, AGB-LE, i.e., that include local extrapolation. We observe that error decrease for these algorithms appear exponential rather than linear, and that they converge faster than without local extrapolation (RMB, RGB, AGB), with convergence around 20,000 learning steps. However, this is at the expense of a residual error which remains around 20% higher than without local exploration. At the bottom of Figure 1, we observe that AGB-LE explores marginally less than the other algorithms.

Altogether, this suggests that adding a local extrapolation component somewhat accelerates learning, though of course at the cost of a weak error at the end of the learning phase. This sustained error is due to the update of the forward model with m i , s pairs where s actually corresponds to the production of m and not to the production of the actual m i .

C. Idiosyncratic behavior: comparing IGB/IGB-LE with AGB/AGB-LE

In the same manner as in Figure 1, we compare in Figure 3 AGB/AGB-LE with IGB/IGB-LE algorithms. The curves for the AGB/AGB-LE algorithms are the same as in Figure 1 and are used here as a reference. We display three versions for the IGB/IGB-LE algorithms differing in their initial frequency f i .

We observe that for a high initial frequency f i (increasing the initial trend for uniform M selection) performance and exploration are close to those with the AGB/AGB-LE algorithms, particularly for IGB-LE. With smaller initial frequencies (increasing the role of idiosyncrasies), the IGB/IGB-LE algorithms explore less but are also less efficient.

A more detailed comparison shows that the ratio between performance and exploration is different between the AGB-LE and IGB-LE algorithms. Indeed, the IGB-LE algorithm achieves performance close to AGB-LE by exploring much less. For instance, with f i equal to 0.1, IGB-LE is 10% less efficient but performs 30% less exploration of the motor space.

This suggests that an adequately tuned idiosyncratic babbling, coupled with local extrapolation, could offer a good compromise between performance and motor space exploration for sensorimotor learning.

V. CONCLUSION

In this paper, we implemented and compared eight algorithms for sensorimotor learning within the Bayesian model COSMO. We introduced and tested three components for sensorimotor learning: "accommodation babbling", "local extrapolation" and "idiosyncratic babbling".

The first result is that the agent efficiently learns the sensory stimuli provided by its master with the AGB algorithm. Importantly, the agent mainly focuses on regions relevant to the master, after however acquiring some knowledge of the other sensory regions thanks to the initial, uninformed stage of the learning process. The second result is that the addition of a "local extrapolation" process (RMB-LE, RGB-LE, AGB-LE) accelerates learning: algorithms converge more quickly, at the expense of a small residual error at the end of learning. The third and last result suggests that "idiosyncratic babbling" coupled with "local extrapolation" (IGB-LE) offers leverage towards a good compromise. IGB-LE provides an efficiency similar to simple "local extrapolation" algorithms, but with less exploration of the motor space.

Of course, these results depend on theoretical and implementation choices which can be discussed. Let us notice four points.

First, we have chosen to learn a forward model P (S | M ). Alternatives would be to learn an inverse model or a global internal model of sensorimotor representations [START_REF] Moulin-Frier | Exploration strategies in developmental robotics: a unified probabilistic framework[END_REF]. Formally, and without simplifying assumptions, these three representations are equivalent:

P (S M ) = P (S)P (M | S) = P (M )P (S | M ) .
We use a forward model for implementation reasons. Indeed, because of the many-to-one problem, the distributions P (M | S) involved in an inverse model are likely to be complex and presenting several modes, requiring sophisticated parametric forms, difficult to specify on theoretical grounds. For the same reasons, the number of parameters of P (S M ) can be difficult to evaluate a priori, since a given motor gesture results in a single sensory output. The Gaussian parametric form of P (S | M ) appears simpler and appropriate.

Second, "accommodation babbling" relies on social guidance by a master, enabling the learning agent to focus on relevant sensory regions. This choice is reasonable in the framework of speech development. Indeed, children focus their learning on the phoneme repertoire of their native language (as displayed by perceptual narrowing, [START_REF] Werker | Influences on infant speech processing: Toward a new synthesis[END_REF]). Of course, internal motivation could be used as a complement of social guidance, in a hybrid algorithm; how social guidance and self-motivated explorations combine in speech development in children is an open question.

Third, "local extrapolation" is built on the hypothesis that one can associate motor gestures m i , close to a selected motor gesture m, with the sensory output s produced with the selected m. We have observed that this motor smoothing process can accelerate learning, although it induces a residual error at the end of the learning process. This could be improved by conceiving a dynamic process in which "local extrapolation" would only appear at the beginning of the learning phase to accelerate exploration of the sensorimotor space and then decrease progressively along learning, in a manner similar to classical simulated annealing [START_REF] Russell | Artificial Intelligence: A Modern Approach[END_REF].

Finally, "idiosyncratic goal babbling" appears as a promising component for sensorimotor learning. However, we focused here on a specific implementation of how the prior about motor gestures P (M ) is learned. For instance, we considered that this distribution was uniform at the onset of the learning process, which is of course questionable. We have seen that vowel /u/ seemed more difficult to learn than vowels /a/ and /i/, since less motor gestures are related to this vowel. However, /u/, as /a/ and /i/, is a quasi universal. It could be assumed that motor gestures related to /u/ have a higher prior, thus facilitating their learning, e.g. because they are related to sucking behaviors in the first months of age [START_REF] Boë | Integrating articulatory constraints in the prediction of sound structures[END_REF].

Whatever the limitations of the studied algorithms, we believe that their comparison within our Bayesian framework is promising, and likely to shed interesting light on the computational processes at hand in sensorimotor exploration in speech development.

Fig. 1 :

 1 Fig. 1: Error measure (Top) and amount of exploration (Bottom) as a function of time, during learning, for RMB/RMB-LE, RGB/RGB-LE and AGB/AGB-LE algorithms. See text for the definitions of the error and exploration measures.

Fig. 2 :

 2 Fig. 2: Top Left: Distribution of the sensory stimuli provided by the master. Values of Diag ConfMat represented in the sensory space for (Top right) the AGB algorithm, (Bottom left) the RGB algorithm and (Bottom right) the RMB algorithm. The x-axis is reverse F 2 and the y-axis is reverse F 1. Values spread from dark blue (low probability) to red (high probability)

Fig. 3 :

 3 Fig. 3: Error measure (Top) and amount of exploration (Bottom) as a function of time, during learning, AGB/AGB-LE algorithms and IGB/IGB-LE algorithms with different initial frequency f i .

Assuming here, as is commonly the case, a many-to-one motor-to-sensory transformation Prod.

More precisely, as S is a discrete space, P (S | M ) corresponds to truncated, bell-shaped distributions that appproximate Gaussian distributions.

ACKNOWLEDGMENT

Research supported by a grant from the European Research Council (FP7/2007-2013 Grant Agreement no. 339152, "Speech Unit(e)s").