Keywords: synchronization, iterative algorithms, read-write locks Calculs synchronisation, algorithmes itératifs, verrous lecture/écriture

case of iterative computations with many parallel tasks which access their resources in a cyclic pattern we provide a generic technique to implement them by means of ORWL. We show that the possible execution patterns for such a system correspond to a combinatorial lattice structure and that this lattice is finite iff the configuration contains a potential deadlock. In addition, we provide efficient algorithms: one that allows for a deadlock-free initialization of such a system and another one for the detection of deadlocks in an already initialized system.

Introduction and Overview

Many iterative computations are be found to observe data dependency patterns between their different computation tasks. In this paper we handle the common case that the output of a task may be input to one or many other tasks and that the read and write access to that data cannot be done atomically. Such dependencies hold e.g for block oriented matrix computations, see [START_REF] Barrett | Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods[END_REF], where the data chunks that are needed for reading are far to big to allow for an atomic wait-free operation on system level.

A well-known technique to handle such situations uses read-write locks (RWL). RWL are designed to allow efficient concurrent access of several readers without involving more than one atomic operation to check readability, see e.g [START_REF] Mellor-Crummey | Algorithms for scalable synchronization on shared-memory multiprocessors[END_REF][START_REF] Krieger | A fair fast scalable reader-writer lock[END_REF] for parallel environments and [START_REF] Wagner | Token-based read/write-locks for distributed mutual exclusion[END_REF] for an algorithm for distributed environments. Before a task reads data that was the output of some other tasks it acquires a read-lock (or shared lock) for that data, meaning that the data can't be modified in the mean time. But eventually other tasks may read the same data without creating a conflict. Before writing, the corresponding task acquires a write-lock (or exclusive lock) that hinders any other task to read or write the data until the lock is released.

Implementations of such RWL data structures usually do not prescribe which task is granted a lock in case that several of them simultaneously request access. This is e.g the case for both RWL that are specified for POSIX [START_REF] Josey | The Open Group Base Specifications Issue 6 -IEEE Std[END_REF], namely pthread_rwlock_t and range locks on files (with fcntl). Here, the norm explicitly states that no guarantee is given on the order in which locks are granted and that applications should not rely on the ordering in which locks are required. In particular, it explicitly allows to grant access to writers (to avoid writer starvation) even if the write-lock request had been clearly issued after the read-lock request.

While such an underspecification of the lock order may be convenient on the system side it clearly is very annoying for an application designer: because of possible lock inversion, cyclic data dependencies easily lead to deadlocks and which to avoid becomes very tedious. This is probably the primal reason why RWL although present in all modern OS do not have a wide spread use.

This underspecification also has the disadvantage that it becomes difficult to guarantee an equitable progression of all tasks. In case of a contention on a lock, two writers could e.g alternate on holding a particular lock while other tasks (readers) would be waiting endlessly to obtain their locks.

Another disadvantage of the commonly used RWL models is the fact that a lock is granted to a process (e.g file locks) or a thread (pthread_rwlock_t) and not to a data entity. Such a dissociation would be convenient when a task wants to reserve a resource pro-actively for an access in a near future ("give me a lock on resource X whence it is available"), to come back to that lock request later, and then only block on it when this has become unavoidable.

In this paper we try to overcome these inconveniences by first imposing that the locks are granted in the FIFO ordering of the requests. Second, we introduce handles as entities that require, acquire and release a lock (Section 2). As an additional benefit, lock-handles give the possibility that a task may issue a new requests on a particular lock while already holding one through another handle ("give me a lock on resource X after all current requests have been satisfied").

With these modifications we are able to introduce a convenient strategy (Section 3) for iterative computations with cyclic data dependencies that can detect (respectively avoid) deadlocks while still guaranteeing a high degree of parallelism and asynchronicity. In particular, in Section 4 we prove that the possible states of such a system of dependencies form a combinatorial lattice that only depends on the initial configuration (ordering) of the locks. As a consequence, we see then that a configuration may deadlock iff this lattice is finite (things that may go wrong will go wrong) and also that the computation then obeys a homogeneous progress, the "homogeneity" only depending on the connectivity properties between the tasks.

Finally, Section 5, we will briefly introduce an algorithm that allows for an efficient instantiation of such lock systems as well as another one that detects if a system that is in a given state would lead to a deadlock or not.

Model

In the following, we suppose we are given a set of computational tasks T that is to be performed and such that there are data dependencies between these tasks. As part of an iterative process, tasks may be recurrent, i.e we may want to executed them many times.

Data dependencies are modeled via read and write operations that are not necessarily atomic. So a data dependency of v ∈ T from w ∈ T then implies that v may only execute while w doesn't. Otherwise v could eventually read inconsistent parts of w's output, one from before an update and one from after.

In order to model parallelism between tasks, we introduce an auxiliary graph, the conflict graph C(T ). We draw an edge between v, w ∈ T if v reads the output of w or w reads the output of v. We say that a subset of tasks T ′ ⊆ T is independent if there is no data dependency between any pair of tasks v, w ∈ T ′ . Independent sets of tasks may be executed in parallel. Clearly T ′ is independent iff it forms an independent set in graph C(T ). The size of the maximum independent set in C(T ) is thus the maximal amount of parallelism that may be reached for the set of tasks T .

We now describe the tools used in our model along with their basic properties.

Ordered Read-Write Locks. Our model targets applications with several tasks which have temporal and possibly data dependencies. Its goal is to allow easy and predictable synchronization between tasks and therefore relies on ordered read-write locks (ORWL). This type of locks has the same semantic of common read-write locks (Concurrent Read, Exclusive Write) but enforces the use of a FIFO policy for its waiting queue. Furthermore, these locks are resource-oriented. Acquisition is thus granted to lock-handles (LH) rather than threads following a two-step pattern.

1. Post a read-or write-request to the lock through a handle. This inserts the request in the FIFO queue for further use (and the requester is thus free to continue execution).

2. Require the previous request. This waits until the request moves first in the FIFO queue, thus granting read-or write-access to the associated resource.

INRIA

This pattern is designed for a particular class of applications which require iterative computation (see Section 3). Obviously, for a comfortable use of ORWL other primitives would be convenient, in particular a non-blocking test that allows to know if a request has been achieved. But since they are not needed in the sequel, we will not go into details of these.

Synchronization overlay. For a given interdependent system of tasks, our model associates a synchronization overlay as an abstraction of the data access pattern. Its role is to give control to tasks whenever it is appropriate (based on the dependencies between them). More specifically, the data space is partitioned maximally according to the different dependencies of the tasks: to each primitive part of the data (called a location) corresponds an ORWL and to each individual request for that part of the data corresponds one (or later several) LH. Acquiring control for a task is done by requiring a write access to a data block (which can be viewed as being proprietary data of the task), while dependencies are modeled by requiring read accesses to other data blocks (viewed as owned by other tasks). Once these accesses are granted, the task is allowed to perform whatever action it is designed for on its data (with possible read-only use of other tasks' data). This model is of course best suited for applications requiring parallel computation over a data space. The partitioning method for the data itself is application-dependent. As an example, take a matrix oriented computation where locations would correspond to blocks of the matrix, tasks would be responsible for writing an individual block. These tasks would then compete for write access to their own block and for read-access to 'neighboring' blocks. Definition 2.1 (Overlay) Consider a synchronization overlay used atop an executable system of n locations.

• Each of these locations can stack any number of exclusive and inclusive lockrequests (abbreviated Xreq and Ireq, respectively), numbered bottom-up. This numbering is called the priority rank of the lock request in the location.

• The request in a location (if any) that has the lowest priority is accounted as being acquired.

• Ireqs may correspond to several (but at least one) LH for which a read-request was issued for the location. Xreqs always correspond to exactly one LH for which was issued a write request for the location. In the priority order, Ireqs may only be directly followed by an Xreq; no such restriction applies to Xreqs which may be directly followed by an Xreq or Ireq.

• Locations which have no Xreqs are called unconstrained and can safely be removed from the system. Others are called constrained.

• An active task is represented by an Xreq along with all the Ireqs that it requested.

We visualize such a lock overlay system by a directed data dependency graph as shown in Figure 1. Here Xreqs are symbolized by a and Ireqs by a . The requests are connected together following the data dependency of their defining tasks. Connections always connect an Xreq to an Ireq, thereby capturing the requirements for a given write request to hold read-locks on other locations.

In the above definition we ask for a task to require exactly one Xreq. This is not a restriction in the modelling capacity since a job that has to place several Xreqs can be easily split into several tasks with one Xreq each such that the read-write semantics remain the same. Take Figure 2 as an example. Here the two coupled write requests A 1 and A 2 are replaced by one request A ′ o that allows to pull the data from locations L 1 and L 2 and two requests A ′ 1 and A ′ 2 that allows to push the modified data back to L 1 and L 2 .

We give now a few definitions to clearly identify the elements of our overlays and their attached semantic.

Definition 2.2 (Executability)

A task is executable if all its locks are acquired, otherwise it is delayed. For a given overlay S, the subset R(S) of locations where the lowest lock is the Xreq of an executable task defines the set of executable locations of S. Locations that are not executable are blocked. Definition 2.3 (Deadlock) An overlay is in a deadlock if all its locations are blocked. Definition 2.4 (Minimal Support) A deadlock's minimal support in an overlay S is the smallest subset of S (both over the locations and over the priority ranks) so that the overlay restricted to that subset is in a deadlock situation. For an overlay to be in deadlock clearly implies that there must be some cycle among its dependencies (see also Lemma 2.1 below). Figure 3 shows different types of minimal supports of deadlocks.

A 1 A 2 L 2 L 1 (a) Two coupled write requests L 0 A ′ 2 A ′ 0 A ′ 1 L 2 L 1
In its general form, our model allows multiple tasks to operate on the same data. This is modeled by several Xreqs on the same location. From such a general overlay S, it is possible to derive an overlay where there is only one Xreq per location but still offers the same execution order of the tasks. Here a location with n Xreqs is split into n different locations. The Xreqs are placed on their respective locations with just one new Ireq underneath and above. The Xreq on location L i is then connected to the upper Ireq on L i-1 and to the lower one on L i+1 . Some slightly modified rules apply to the Xreqs 1 and n as indicated in the figure. This reordering from a chain on one location to a staircase on several locations does not change the relative ordering in which the Xreqs are acquired.

Other Xreqs that are connected to the Ireqs (e.g the grey one) are connected to the respective two copies. For Xreqs (as A or B), that connect to the top or the bottom of the chain, special connection rules apply.

It is important to note that these replacement rules ensure that the order of the acquisition of the requests remains stable, even if the analogous requests for completed task are re-issued after their termination: e.g B always gets acquired just after n is freed, and 1 only gets acquired just after B, whereas A and B are always executed in between n and 1 but their respective order is not fixed.

Let n be the size of the initial location and m be the number of external connection into that location. Then the number of added Ireqs is at most 2n and the number of added links is at most 2n + m. Since each Xreq and each link appears at most once in such a replacement of a chain, the overall size of the overlay remains linear in size compared to the original one.

In the sequel we will usually assume that an overlay is given in canonical form. This means in particular that any given location may have at most three requests that are pending, the valid configurations are illustrated in Figure 5. Thus an implementation may restrict the length of the priority queue to three items. As we have seen, this assumption does not change the modelling capacity nor does it increase the size of the overlay by more than a constant factor. It has the advantage that from now on we may identify three conceptually different types of objects, namely the set of tasks, the set of lock locations and the set of Xreqs : each task corresponds to exactly one (data) location and is the only one to have an Xreq for that location. INRIA Definition 2.6 (Delay digraph) For a given overlay S in canonical form, its delay digraph is constructed as follows:

1. Build an undirected graph whose vertices are the locations. One edge is added each time a link exists in the overlay between a pair of locations. This graph is isomorphic to the conflict graph C(T ) over tasks from above.

2. Add orientation to the edges depending on the link in the overlay:

• If the Xreq A is connected to an Ireq which is above an Xreq B, the edge is oriented A → B, as in Figure 6(a).

• If the Xreq A is connected to an Ireq which is below an Xreq B, the edge is oriented A ← B, as in Figure 6(b).

Lemma 2.1 An overlay S in canonical form has a deadlock iff there is a cycle in its delay digraph. Proof. In a delay digraph, a location L connected to a location L ′ means that L is blocked as long as L ′ is blocked. Therefore, if a cycle exists in the delay digraph, all the locations in the cycle are blocked and thus obviously fit the definition of a deadlock. Contrariwise, if there is a deadlock then all the locations in the deadlock are blocked and are thus connected to a blocked location in the delay digraph. Suppose that all these connections do not form a cycle, then at least one of the location has to be a sink which means that it is not blocked and is thus not part of the deadlock, a contradiction.

Iterative Computations

In this section, we explain how our model can be applied to iterative computations. This category of computations shows data dependencies that allow to run parallel execution by slicing data and feeding a pipeline. As applied here, the model performs per-slice synchronization, i.e it synchronizes between computations of data blocks. The use of ORWL and their FIFO policy perfectly suits the dependency requirements of such algorithms. As an iterative algorithm generally computes until stabilization or a predefined number of iterations, computation over a single data block is performed with the following loop: wait to acquire the ORWL for reading (or writing), then perform computation (if any), then release the ORWL. Therefore a complete execution of an iterative algorithm over some data space requires one ORWL per sliced data block (a location). We now detail the execution model for such algorithms and give some of its properties. Setup.

L1 L2 L3 (a) L1 G G L3 L2 L1 (b) L2 | | L3 L2 L1 (c) L3 y y L1 G G L1+L3 `L1 L2 L3 (d) L3 y y
• A new Xreq is posted on top of L.

• For each Ireq to which the lowest Xreq in L is connected to, a new Ireq is posted on top of the corresponding location.

• For each connection between the lowest Xreq in L and an Ireq, a similar connection is established between the new Xreq and new Ireq that were previously added.

Run.

• The system is now ready to execute the computational task represented by L.

Clean up.

• All connections from the original Xreq in L are removed (including the target Ireq if it was the last connection to it).

• The original Xreq in L is removed.

Less formally, execution of a location is done by reinserting the Xreq and its Ireqs (the task) back on top of their locations (for further execution) and then removing it (after the execution of the task took place). Figure 7 gives the evolution of a linear chain of three tasks.

INRIA

The setup phase uses the delayed request feature of ORWL. Once a lock is acquired, a new request for the same lock is posted for the future iteration. The clean up phase is simply releasing of all acquired locks.

Iterative computations with our model involve an initial distribution of requests (see Section 5). Then each task only competes on a predefined subset of ORWL and runs according to the previously defined loop. This means that posting a new request during the setup phase can only Figure 8: New non-trivial configuration be done if the corresponding (old) request is already hold.

Therefore once a new Xreq has been posted in the setup phase, the location is not in canonical form until the clean up phase. This introduces only one new possible configuration given by Figure 8. This situation is not problematic since the iterative execution model states that nothing can be added atop the location until the middle Ireq has been acquired. This can only happen after the lowest Xreq has been released, which leads back to a canonical form. In this new half canonical form, the lowest Xreq corresponds to the task performing the n th iteration, while the highest Xreq corresponds to the computation of the n + 1 th iteration by the same task.

Definition 3.2 (Parallelism)

The parallelism level of a given overlay S is given by:

(1)

S = |R(S)| |S|

A parallelism level of 0 is a deadlock situation (R(S) = ∅, so there is no executable location). A parallelism level of 1 is maximal (R(S) = S, so the entire overlay is executable).

As defined, the parallelism level is computed on a snapshot of a single iteration. Iterative algorithms may show different parallelism levels, depending on the chosen iteration and data dependency pattern. For instance, the linear chain of three tasks has two possible configurations cycles of three configurations each (abc and bcd). On each of these cycles, one configuration has a parallelism level of 2 3 and the other two have a parallelism level of 1 3 . The average parallelism level on the cycle is thus of 4 9 .

Definition 3.3 (Devolution)

The evolution rule can easily be reverted by considering the horizontally mirrored overlay and then applying the evolution rule. This is equivalent to the evolution rule with "lowest" replaced by "highest" and "on top of" by "below".

The following lemma shows that our execution model for iterative algorithms cannot undo a deadlock, nor can it spawn a new one. Lemma 3.1 Whenever a deadlock exists in an overlay, then the minimal support for that overlay exists in all its ancestors and successors.

Proof: Suppose we have an overlay which contains a deadlock. All the Xreqs in the deadlock's minimal support are either not the lowest in their corresponding locations or are connected to Ireqs that are not the lowest in their corresponding locations. This means that whenever an execution occurs, all the items that are removed from the overlay are not part of the deadlock's minimal support and so are the items added atop the overlay. Thus, execution does not modify the deadlock's minimal support, which is therefore present in all successors.

With the devolution rule, the same applies to all ancestors of a given overlay.

Lattice Structure and Deadlocks

In this section, we will give the constructs and proofs of a lattice structure over the overlay configuration space and characterize the configuration spaces with deadlock.

Definition 4.1 (Overlay configuration) Given an overlay I, an overlay S that can be obtained from I by i applications the evolution rule is said to be in configuration (i, S).

The overlay I is in configuration (0, I) and is said to be the initial configuration. Let (i, A) * -→ (j, B) and (j, B) * -→ (i, A). First, notice that (i, A) + -→ (j, B) =⇒ i < j. Suppose now that (i, A) = (j, B). The evolution rule is thus applied at least once and we have i < j and j < i, which is contradictory. Therefore (i, A) = (j, B) (antisymmetry). Therefore after both a and b have been executed, all the elements added and removed from S are the same, no matter the order in which the two locations were executed.

Lemma 4.3 Let (t, I t ) any common predecessor of (i, A i ) and (j, B j ) such that the two execution paths from (t, I t ) to (i, A i ) and (j, B j ) have a common executable location. Then (t, I t ) is not a maximal predecessor.

Proof. Let a = a t , . . . , a i-1 be the path from (t, I t ) to (i, A i ) and b = b t , . . . , b j-1 be the path from (t, I t ) to (j, B j ). Let us assume that L = a λ is the first element in a with L ∈ a ∩ b. If λ = t then L is executable for (t, I t ). Otherwise, if λ = t the locations a t , . . . , a λ-1 are not executed in b. Then, since L is also executed in b, a t , . . . , a λ-1 can't change the property of L of being executable or not. Thus L must already be executable for (t, I t ).

(i, A i ) (t, I t ) L G G (t + 1, I t+1 ) * S S * A A (j, B j )
By the Lemma 4.2, we know that the execution order of initially executable elements along a path does not matter, thus if there is L ∈ a ∩ b, we can permute the execution order so that L appears first in both a and b. Now denote by (t + 1, I t+1 ) the configuration that is obtained from (t, I t ) by executing L. Then we have the situation of Figure 9 and this completes the proof of the claim. Proof: Since any two configurations are derived from the initial configuration, by Lemma 4.3 we see that there is a unique maximal predecessor (p, P p ) to any two attainable configurations (i, A i ) and (j, B j ) with i > p and j > p, and (i, A i ) * -→ (j, B j ) and (j, B j ) * -→ (i, A i ). It follows that the locations that are executed on the two path from (p, P p ) to (i, A i ) and (j, B j ) form two sets of locations that are mutually disjoint.

We now show by induction that (i, A i ) and (j, B j ) have a common successor and that the minimal such successor is unique.

Let a = { {a p , . . . , a i-1 } } be the multiset containing the locations along the execution path from (p, P p ) to (i, A i ) and similarly let b = { {b p , . . . , b j-1 } } be the multiset containing the locations along the execution path from (p, P p ) to (j, B j ).

By definition a ∩ b = ∅ and either a = ∅ or b = ∅ (otherwise A i = B j ). W.o.l.g, let assume that a = ∅. Lemma 4.2 states that, as a p is executable in (p, P p ), it remains so along the path to (j, B j ). Thus (j, B j ) ap -→ (j + 1, B j+1 ). Let (p, P ) ap -→ (p + 1, P p+1 ). (p + 1, P p+1 ) is the maximal predecessor of (i, A i ) and (j + 1, B j+1 ). Now suppose that A i * -→ B j+1 . Then obviously (p + 1, P p+1 ), (i, A i ) and (j + 1, B j+1 ) still fulfill the induction hypothesis. So by induction we may conclude that we may subsequently add elements to B = B j , B j+1 , . . . , B ℓ until

(i, A i ) * -→ (ℓ, B ℓ ).
This show that there is a common successor of (i, A i ) and (j, B j ). B ℓ is minimal and unique with that property since by construction its set of locations is a ∪ b and ℓ = |a ∪ b|.

Chip Firing Games. During the development of our model, we defined a morphism from overlays to chip firing games (CFG). CFG, as defined in [START_REF] Magnien | Étude du modèle du tas de sable abélien : points de vue algorithmique et algébrique[END_REF], are directed graphs whose vertices are numbered by a certain amount of chips. Once a vertex acquires more chips than its outgoing degree, it can be fired. Firing a vertex means to decrease its chips INRIA by its outgoing degree and distribute one chip along each outgoing link, which is then added to the connected vertex. Definition 4.3 (Evolution by a CFG) The evolution of an overlay in canonical form can be modeled with a chip firing game (CFG). The support for the CFG of a given overlay S is built as follows:

(0, b) L2 (1, c) L3 Ó Ó L1 ' ' L1+L3 (2, a)
• Each constrained location in the overlay gives a vertex in the support.

• Each location connected to a non-constrained location in the overlay gives a loop to its corresponding vertex.

• Each connection between an Xreq and an Ireq in a constrained location in the overlay gives a pair of arcs, one directed forward (according to the corresponding locations) and the other directed backward.

With:

• δ S (L) be the number of connections originating from location L.

• σ S (L) be the total number of requests in location L.

• ω S (L) be the rank of the Xreq in location L.

• ρ S (L, L ′ ) be the rank of the Ireq in location L ′ to which the Xreq in location L is connected (if such a connection exists, 0 otherwise).

The initial chip distribution for a vertex v given by a constrained location L is:

chips(v) = δ S (L) + σ S (L) -1 -ω S (L) - L ′ ∈S ρ S (L, L ′ )
Note that by construction, all connected components in the CFG are closed components.

In [START_REF] Latapy | The lattice structure of chip firing games and related models[END_REF], an extended configuration for the CFG is given for the general case, in particular the ones with closed components. This new configuration space has the same properties of the original one, notably the equal length of paths between two configurations and the lattice structure.

Infinite Lattices and Deadlocks. In the general case of iterative computations, the configuration space is an infinite lattice. This is a desired state since this kind of applications typically require computation to be performed until some external event occurs (stabilization or user-defined termination). Figure 10 gives the beginning of the lattice structure for the linear chain of three tasks with initial configuration given by Figure 7(b). Theorem 4.2 (Deadlock is finite) An overlay which has a deadlock has a finite configuration space and the maximal configuration is a deadlock situation.

Algorithm 1: Compute an initial request ordering

Input: A set of tasks T , a set of lock locations L and for each task T ∈ T a list of Xreqs (X 1 , . . . , X w ) and of Ireqs (I 1 , . . . , I r ), where the X i and I j are locations in L. Output: For each L ∈ L a priority ordering of the requests for L such that the resulting overlay as a whole is deadlock free.

construct construct an implicit representation of the conflict graph C(T ); color compute a coloring T 1 , . . . , T x of C(T ); foreach location L ∈ L of T do initialize p(L) to 0;

insert foreach color c = 1, . . . , x do foreach task T ∈ T c do in parallel foreach Xreq X of T , X = X 1 , . . . , X w do increment p(L), set the priority of X to the new value and increment p(L) again; foreach Ireq I of T , I = I 1 , . . . , I r do set the priority of X to p(L); Proof: A finite configuration space (and thus a maximal configuration) obviously fits the definition of a deadlock (no further evolution possible).

Suppose we have an overlay which is known to have a deadlock. Let (i, D) be a configuration of a deadlock at minimum distance i from the initial configuration. Let (i, C) be another configuration at the same distance from the initial configuration. The configuration space is a lattice, so we have (j, B) with (i, C) + -→ (j, B) and (i, D) + -→ (j, B). Since (i, D) is in fact a deadlock, we must have that j = i and thus that B = D. But then also C = D = B and the two configurations are the same. Thus (i, D) is the only configuration that exists at distance i. It follows that there is no other attainable configuration at distance j > i. Hence the lattice is finite (with the maximal configuration being the deadlock configuration).

Overlay Initialization and Deadlock Detection

In the first part of this section we will not be able to assume that an overlay would be in canonical form or that each task only has one Xreq. This is so, since the replacement techniques that we introduced already need a priority ordering as an input.

Deadlock Free Initialization. For a strategy to construct an initial overlay see Algorithm 1. It consists of first computing the conflict graph, finding a partition of it into independent sets (i.e a coloring) and then placing the lock requests according to the position of color class of the task. Since it only handles tasks in parallel that don't have conflicts, at most one Xreq X is inserted for a given location L during each of the x insertion phases. The following lemma is easily verified by observing that in the corresponding delay digraph the orientations of the arcs always lead from a task with a higher number in the coloring to one with a lower number. Lemma 5.1 Algorithm 1 generates an overlay that is deadlock free. Lemma 5.2 Besides the phases construct and color, Algorithm 1 runs in sequential time that is proportional to the input and can be implemented in parallel to run in time x, where x is the coloring number that color computed.

The two phases construct and color are not explained in Algorithm 1 (and thus in Lemma 5.2). In construct, we could be tempted to construct the entire graph C(T ). This graph could be quite large for the case that there are several Xreqs in one location; C(T ) then has a clique containing all the tasks that write to the same location. Such an explicit construction can be avoided by using a data structure that uses the knowledge about the shared locations. Details of that are left to the extended version of this paper.

With this implicit representation of C(T ) in color we then have to construct a coloring. Although this problem is NP-hard in general, there are good heuristics that provide colorings with ∆ + 1 colors, where ∆ is the maximum degree of the graph. They can be computed in parallel and in a distributed setting, see [START_REF] Gebremedhin | Graph Coloring on a Coarse Grained Multicomputers[END_REF], and large scale tests (especially for matrix computations) show that these algorithms behave quite well in practise, see [START_REF] Bozdag | A framework for scalable greedy coloring on distributed memory parallel computers[END_REF]. We don't think these computations will be a bottleneck for real applications of our techniques. Also, usually we may suppose that we are in a setting where each processor will have to perform several tasks per iteration. Thus a rough estimate of the coloring number should suffice.

In addition, Algorithm 1 is only computing the initial setting, afterwards the system evolves asynchronously. The set of tasks that are active in parallel can be the set of executable locations of any of the reachable configurations. Consider the example in Figure 11. Both subfigures represent different initializations for the same system of tasks and that both could be produced by Algorithm 1. 11(a) corresponds to a nonoptimal coloring where each task has its own color and these colors are taken in worst possible order. In contrast, 11(b) corresponds to an optimal coloring with just two colors. 11(b) has a much higher degree of parallelism than 11(a) and is therefore clearly preferable. Nevertheless, both configurations are part of the same configuration space and reachable from each other. Thus, the behavior of the system on the long run does not depend too much from initial setting but much more on the execution strategy that chooses among the executable tasks.

Transforming into Canonical Form. As we have seen in Section 2, a transformation of an overlay into canonical form can be done with local replacement rules that eventually introduce new locations and Ireqs, and may move some dependencies from one request to another. It is easy to see that such replacements can be computed in a distributed setting. Also observe that these replacements do not change the execution: no additional tasks are introduced and the relative order of tasks is strictly respected. We leave the details for a full version of this paper.

Deadlock Detection. If for some reason an overlay can't be initialized by Algorithm 1 we may use the tools of Section 2 to detect a deadlock. The idea would be to first construct the conflict graph and then the delay digraph C(T ) from it. Then from Lemma 2.1 it follows that a simple test for cycles will show whether or not the overlay contains a deadlock or not.

But with the structural results of Section 4 we even have a much easier strategy, which consists in a test execution of all tasks. Theorem 5.1 Suppose an overlay has a sequence of executions such that each location is executed at least once. Then the overlay is deadlock free.

Proof: First assume that the overlay is connected. Let L = (L 1 , . . . , L k ) be an execution path that executes all locations. Let L ′ = (L ′ 1 , . . . , L ′ k ′ ) the sub-sequence of the first occurrence of the locations. From Lemma 4.2 we know that L ′ is also executable. Thus L ′ leads back to the initial configuration and as a consequence the lattice of configurations is infinite. Theorem 4.2 then proves that the overlay must be deadlock-free.

If the overlay is not connected the argument applies to each connected component.

The algorithmic details of such a deadlock detection routine are left to the reader.

Conclusion and Outlook

The analysis of our model shows valuable properties for parallel computation in general and iterative algorithms in particular. It is interesting to note that it allows for automated initialization of a system from an abstract representation of tasks and dependencies. The user has only to specify these dependencies and to implement the computational part of the different tasks. The lattice structure of the overlay configuration space then ensures that a deadlock-free initialized system will run as expected; namely is guaranteed to remain without deadlock and to execute all tasks evenly. A first implementation of ORWL has been added to our PARXXL library [START_REF] Gustedt | parXXL: A fine grained development environment on coarse grained architectures[END_REF]. It is based on request stamps (the priority ranks) that are accorded to lock-handles data structure and on condition variables to regulate congestion.

As ORWL are a general tool which is not bound to a particular class of applications, we plan some extensions. For instance, it could be used to model byte-range locking on files or other objects by tackling the problem of joint ranges. This would provide predictable access to shared objects without imputing to the user more overhead than INRIA common read-write locks operations. Also, as ORWL are resource-oriented they can more easily be extended to distributed environments. This will enable us to implement the data handover API as it was described in [START_REF] Gustedt | Data Handover: Reconciling Message Passing and Shared Memory[END_REF].

As shown, the coloring method directly impacts the initialization of a given system. For some applications, different initializations can lead to disconnected configuration spaces. For instance, it is possible to initialize a linear cycle to produce either a token-ring or a half-homogeneous execution pattern. This makes it possible to also use ORWL as a temporal synchronizing tool.

Figure 1 :

 1 Figure 1: Sample overlay with an executable task (light grey) and a delayed task (dark grey).

2 Figure 2 :Figure 3 :

 223 Figure 2: Transforming coupled write requests

Definition 2 . 5 (

 25 Canonical Form) An overlay is in canonical form if it has at most one Xreq per location.

Figure 4

 4 Figure4gives the rewrite pattern used to transform an overlay into canonical form. Here a location with n Xreqs is split into n different locations. The Xreqs are placed on their respective locations with just one new Ireq underneath and above. The Xreq on location L i is then connected to the upper Ireq on L i-1 and to the lower one on L i+1 . Some slightly modified rules apply to the Xreqs 1 and n as indicated in the figure. This reordering from a chain on one location to a staircase on several locations does not change the relative ordering in which the Xreqs are acquired.Other Xreqs that are connected to the Ireqs (e.g the grey one) are connected to the respective two copies. For Xreqs (as A or B), that connect to the top or the bottom of the chain, special connection rules apply.It is important to note that these replacement rules ensure that the order of the acquisition of the requests remains stable, even if the analogous requests for completed task are re-issued after their termination: e.g B always gets acquired just after n is freed, and 1 only gets acquired just after B, whereas A and B are always executed in between n and 1 but their respective order is not fixed.Let n be the size of the initial location and m be the number of external connection into that location. Then the number of added Ireqs is at most 2n and the number of added links is at most 2n + m. Since each Xreq and each link appears at most once in such a replacement of a chain, the overall size of the overlay remains linear in size compared to the original one.In the sequel we will usually assume that an overlay is given in canonical form. This means in particular that any given location may have at most three requests that are pending, the valid configurations are illustrated in Figure5. Thus an implementation may restrict the length of the priority queue to three items.

Figure 4 :

 4 Figure 4: Transforming a chain in location L to canonical form on locations L 1 , . . . , L n .

Figure 5 :

 5 Figure 5: Non-trivial configurations in canonical form

  priority of Ireq over Xreq

Figure 6 :

 6 Figure 6: Delays imposed by the priority order on the lock requests

Figure 7 :

 7 Figure 7: Evolutions of a linear chain of three tasks.

Definition 4 . 2

 42 The relation (i, A) -→ (i+1, B) denotes the application of the evolution rule once from (i, A) to get (i + 1, B). The relation * -→ is the reflexive transitive closure of the relation -→. The relation + -→ is the transitive closure of the relation -→.

Lemma 4 . 1 (

 41 Order) For a given initial configuration (0, I), the relation + -→ defines a partial order.Proof: It is obvious that (i, A) * -→ (i, A) by not applying the evolution rule once (reflexivity).Let (i, A) * -→ (j, B) and (j, B) * -→ (k, C). It is obvious that (i, A) * -→ (k, C), by applying the evolution rule along the two paths to and from (j, B) (transitivity).

Lemma 4 . 2 (

 42 Evolution Independence) Whenever two locations a and b are independently executable in an overlay S, any order of execution of a and b leads to the same overlay S ′ .Proof. As a and b are independent, all the elements added and removed by the execution of a do not modify the location b. Contrariwise, all the elements added and removed by the execution of b do not modify the location a.

Figure 9 :

 9 Figure 9: Inductive step.

Theorem 4 . 1 (

 41 Lattice structure) The configuration space built from an overlay initial configuration and the evolution rule forms a lattice.

L1

Figure 10 :

 10 Figure 10: Lattice for the linear chain of three tasks.

  One color class per location L1 L2 L3 L4 L5 L6 (b) The result of a 2-coloring

Figure 11 :

 11 Figure 11: Two different initializations of the same set of requests

RR n°6685


Gilles Lebrun
email: gilles.lebrun@unicaen.fr

Christophe Charrier
email: christophe.charrier@unicaen.fr

Olivier Lezoray
email: olivier.lezoray@unicaen.fr

Hubert Cardot
email: hubert.cardot@univ-tours.fr

Tabu Search Model Selection for SVM

A model selection method based on tabu search is proposed to build support vector machines (binary decision functions) of reduced complexity and efficient generalization. The aim is to build a fast and efficient support vector machines classifier. A criterion is defined to evaluate the decision function quality which blends recognition rate and the complexity of a binary decision functions together. The selection of the simplification level by vector quantization, of a feature subset and of support vector machines hyperparameters are performed by tabu search method to optimize the defined decision function quality criterion in order to find a good sub-optimal model on tractable times.

Introduction

Data mining is considered as one of the challenging research fields of the 21 th century. Extracting knowledge from raw data is a difficult problem which covers several disciplines: Artificial Intelligence, Machine Learning, Statistics, Data Bases. Machine learning methods aim at providing classification methods which induce efficient decision functions. Among all possible inducers, Support Vector Machine (SVM) are founded on strong statistical learning theory [START_REF] Vapnik | Statistical Learning Theory[END_REF] and have become very popular in the past few years because they delivered state-of-the-art performance in many real world pattern recognition and data mining applications 2 : text categorization, hand-written character recognition, image classification, bioinformatics, etc. However, decision functions provided by SVM have a complexity which increases with the training set size [START_REF] Platt | Fast training of SVMs using sequential minimal optimization, advances in kernel methods-support vector learning[END_REF][START_REF] Yu | Classifying large data sets using SVM with hierarchical clusters[END_REF][START_REF] Lebrun | SVM training time reduction using vector quantization[END_REF] . A recent theoretical re-sult by Steinwart 6 shows that the number of examples used by a given SVM decision function grows as a linear function of the number of examples in the SVM training set. Therefore, time decision with SVM inducer to classify huge datasets is not directly tractable; especially for application requiring high classification speed [START_REF] Keerthi | Building support vector machines with reduced classifier complexity[END_REF] . For instance, Martin et al [START_REF] Martin | Learning to detect natural image boundaries using local brightness, color and texture cues[END_REF] conclude that SVM are not well suited to edge detection. Indeed, the training time and complexity are too high to be interesting as regards the huge dataset they used. However, they use SVM as brute-force algorithm whitout taking care of model selection both training time and complexity. Our aim, in this paper, is to tackle that problem.

In recent years, there has been a lot of interest to improve learning methods using SVM. One way is to optimize the SVM algorithm to solve the associated quadratic problem more efficiently [START_REF] Platt | Fast training of SVMs using sequential minimal optimization, advances in kernel methods-support vector learning[END_REF][START_REF] Chang | Libsvm: a library for support vector machines[END_REF][START_REF] Vishwanathan | SimpleSVM. In ICML[END_REF] (less time and less memory used). Other approaches fo-cus on simplifying the SVM decision function. Many solutions were proposed to reduce the number of examples in SVM decision functions: (1) A preprocessing simplification step to reduce the size of SVM training set [START_REF] Yu | Classifying large data sets using SVM with hierarchical clusters[END_REF][START_REF] Ou | Expediting model selection for SVMs based on data reduction[END_REF][START_REF] Tsang | Core vector machines: Fast SVM training on very large data sets[END_REF] , (2) An incremental SVM learning method with stopping criteria [START_REF] Parrado-Hernndez | Growing support vector classifiers with controlled complexity[END_REF][START_REF] Yang | A training algorithm of incremental support vector machine with recombining method[END_REF][START_REF] Katagiri | Incremental training of support vector machines using hyperspheres[END_REF] , (3) A bound on the number of support vectors of the decision function [START_REF] Herbrich | Learning Kernel Classifiers[END_REF][START_REF] Lin | A study on reduced support vector machines[END_REF] or (4) A post-processing to reduce the number of support vectors of the decision function [START_REF] Thies | Optimal reduced-set vectors for support vector machines with a quadratic kernel[END_REF][START_REF] Abe | Support Vector Machines for Pattern Classification[END_REF] . Although SVM are less sensitive to the curse of dimensionality [START_REF] Christianini | Dimension reduction in text classification with support vector machines[END_REF] , dimensionality reduction techniques can improve their efficiencies [START_REF] Chapelle | Choosing multiple parameters for support vector machines[END_REF][START_REF] Fröhlich | Feature selection for support vector machines using genetic algorithms[END_REF] . Moreover, this is another way to reduce complexity of SVM decision functions [START_REF] Bi | Multi-objective programming in SVMs[END_REF][START_REF] Fröhlich | Feature selection for support vector machines using genetic algorithms[END_REF] . For learning methods using SVM, model selection is critical. Indeed studies have shown that SVM generalization efficiency depends on the choices of SVM parameters [START_REF] Chapelle | Model selection for support vector machines[END_REF][START_REF] Nakayama | Mop/gp models for machine learning[END_REF] . Other studies [START_REF] Rifkin | In defense of one-vs-all classification[END_REF][START_REF] Lebrun | An EA Multi-model selection for SVM Multiclass schemes[END_REF] have shown that multiclass SVM are efficient if an efficient model selection is performed for each involved binary SVM. Therefore, as regards these considerations, new approaches aim at incorporating a simplification step into the model selection [START_REF] Ou | Expediting model selection for SVMs based on data reduction[END_REF][START_REF] Lebrun | SVM training time reduction using vector quantization[END_REF] . Previous cited works highlight that complete SVM model selection (reduction of both the number of examples and features, and selection of hyperparameters) is a hard and still unresolved problem. Solution proposed in most of these works focus only on a sub-problem of the complete model selection problem. At our knowledge, there actually exist no way in literature to achieve such difficult SVM complete model selection: simultaneously tuning the hyper parameters, selecting accurate features and relevant examples (this is usually performed in a sequential manner).

Our approach aims at unifying feature selection, simplification of training set and hyperparameters tuning as a global optimization problem is order to produce efficient and low complexities Binary Decision Functions (BDF) with SVM [START_REF] Lebrun | Fast pixel classification by SVM using vector quantization, tabu search and hybrid color space[END_REF][START_REF] Lebrun | A new model selection method for SVM[END_REF][START_REF] Lebrun | A fast and efficient segmentation scheme for cell microscopic image[END_REF] . For this, a criterion named Decision Function Quality (DFQ) is defined which takes into account the recognition rate, the number of support vectors and the number of selected features of BDF. The objectives, for an efficient BDF, are to have a high recognition rate, few support vectors and few features used. The proposed DFQ criterion is based on regularization theory [START_REF] Tikhonov | Solution of Ill-posed Problems[END_REF][START_REF] Tikhonov | Ill-Posed Pproblems: Theory and Applications[END_REF] . The fitting term is expressed in terms of recognition rate. The smoothness term is expressed in terms of model complexity (number of support vectors and features used by a BDF). With this expression of DFQ, one wants to find solutions that are simultaneously smooth (few support vectors and features) and close to the initial data (high recognition rate) in terms of a compromise. In the framework of Multi-Objective Optimization (MOO) [START_REF] Coello | Evolutionary Algorithms for Solving Multi-Objective Problems[END_REF][START_REF] Engelbrecht | Fundamentals of Computational Swarm Intelligence[END_REF] , weighted sum of objectives in one possibility to transform MOO problem into a global single objective problem [START_REF] Bi | Multi-objective programming in SVMs[END_REF] . Then, regularization theory can be regarded as one way to transform the general problem of finding efficient solutions in the paradigm of multi-objective optimisation into the paradigm of single-objective optimisation. Indeed, one can produce fast and efficient decision SVM processes with a single-objective optimisation problem when DFQ criterion based on regularization theory is used to evaluate the produced solution. With the proposed approach, the selection of efficient values for all free parameters (feature selection or rejection, level of simplification and SVM hyperparameters) in order to optimize DFQ criterion is designed by the generic term of model selection.

Training set simplification is produced by the LBG (Linde, Buzo, Gray) algorithm used in vector quantization research field [START_REF] Gersho | Vector Quantization and Signal Compression[END_REF] . It has been retained because it can produce good prototypes of the initial dataset. Moreover, the simplification level is controlled by a single integer parameter the values of which are few and can range from extreme simplification with only one prototype by class to no simplification at all (i.e. selection of all initial examples in training set). However, the proposed learning method is enough general to be extended to other simplification methods [START_REF] Han | Data Mining: Concepts and Techniques[END_REF][START_REF] Gray | Data mining: multimedia, soft computing and bioinformatics[END_REF][START_REF] Tan | Introduction to Data Mining[END_REF] . To have a relevant tuning of SVM hyperparameters and an accurate selection of relevant features, an adapted tabu search (TS) method is proposed which includes specific intensification and diversification strategies. TS is relevant for SVM model selection since usual SVM model selection have local minima [START_REF] Dong | An improved handwritten chinese character recognition system using support vector machine[END_REF][START_REF] Abe | Support Vector Machines for Pattern Classification[END_REF] . Moreover, TS has proved its suitability for other model selection problems [START_REF] Glover | Tabu search[END_REF] , in particular with SVM learning problems [START_REF] Korycinski | Adaptive feature selection for hyperspectral data analysis[END_REF][START_REF] Pai | Using directed acyclic graph support vector machines with tabu search for classifying faulty product types[END_REF] .

Our approach is tested on several benchmark datasets and on an image segmentation problem. For the latter, the development of a microscopic cellular image segmentation application was performed [START_REF] Lebrun | A fast and efficient segmentation scheme for cell microscopic image[END_REF] . This kind of application must be efficient for reliable analysis and fast to process huge quantity of images. In contrast, recent studies have focused on improving segmentation quality [START_REF] Vandenbroucke | Color image segmentation by pixel classification in an adapted hybrid color space: application to soccer image analysis[END_REF][START_REF] Meurie | A supervised segmentation scheme for cancerology color images[END_REF][START_REF] Meurie | Combination of multiple pixel classifiers for microscopic image segmentation[END_REF] . Many segmentation schemes can have good qualities but their processing time is too expensive to deal with a great number of images per day [START_REF] Lebrun | Fast pixel classification by SVM using vector quantization, tabu search and hybrid color space[END_REF][START_REF] Lebrun | A fast and efficient segmentation scheme for cell microscopic image[END_REF] . The main reason is that pixel classification in a segmentation scheme requires most of the processing time. Therefore, the classifier design is crucial to produce fast and efficient pixel classification. Presented results show that our method satisfies those objectives for this cell segmentation application. Moreover, experimental results on benchmark datasets show that an efficient compromise between high generalization ability and low complexity can be found with our TS model selection.

Section 2 gives overviews of methods used by our TS model selection method. Section 3 describes the proposed new method and Section 4 gives experimental results. Last Sections conclude and propose future works.

Overviews of the underlying methods

Support Vector Machines (SVM)

The SVM was developed by Vapnik et al [START_REF] Vapnik | Statistical Learning Theory[END_REF] . They are based on the structural risk minimization principle from statistical learning theory 1 . Let's consider a binary classification problem with training data {(x i , y i )} i∈{1,...,m} (x i ∈ R n and y i ∈ {-1, +1}). A soft margin SVM [START_REF] Vapnik | Statistical Learning Theory[END_REF][START_REF] Cristianini | An Introduction to Support Vector Machines and other kernel-bases learning methods[END_REF] classifies an example x according to the sign of BDF h :

h(x) = sign(f (x)) (1)
with f (x) = i∈{1,...,m}

α i y i K (x i , x) + b (2)
and K(

SVM probabilities estimation

The output (2) of an SVM is not a probabilistic value, but an un-calibrated distance measurement of an example x to the separating hyper-plane. Platt proposed a method [START_REF] Platt | Probabilistic outputs for support vector machines and comparison to regularized likelihood methods[END_REF] to map the SVM output into a positive class posterior probability by applying a sigmoid function to the SVM output:

p(y = +1|x) = 1 1 + e a1•f (x)+a2 (3)
This method is used in SVM combination schemes based on probabilistic estimation.

SVM combination schemes

SVM are specifically designed for binary problems. Several combination schemes have been developed to take into account that specificity and deal with multiclass problems [START_REF] Price | Pairwise neural network classifiers with probabilistic outputs[END_REF][START_REF] Hastie | Classification by pairwise coupling[END_REF][START_REF] Dietterich | Solving multiclass learning problems via error-correcting output codes[END_REF][START_REF] Moreira | Improved pairwise coupling classification with correcting classifiers[END_REF] . Within all combination schemes, the one-versus-all scheme based on a winner-takes-all strategy and the one-versus-one (or pairwise) method based on a max-wins voting strategy are generally used [START_REF] Abe | Support Vector Machines for Pattern Classification[END_REF][START_REF] Rifkin | In defense of one-vs-all classification[END_REF] . When class probabilities on each binary problem are estimated (c.f. Section 2.2), the two above schemes have adapted decoding strategies to estimate class probabilities for the multiclass problem 53 .

Vector Quantization (VQ)

VQ is a classification technique used in the compression field [START_REF] Gersho | Vector Quantization and Signal Compression[END_REF] . VQ maps a vector x to another vector x ′ that belongs to m ′ prototypes vectors which is called codebook. The codebook S ′ is built from a training set S t of size m (m >> m ′ ). The algorithm must produce a set S ′ of prototypes which minimizes the distorsion

d ′ = 1 m m i=1 min 1≤j≤m ′ d(x i , x j ) (4)
where d(., .) is a L 2 norm. LBG is an iterative algorithm [START_REF] Gersho | Vector Quantization and Signal Compression[END_REF] which produces 2 k prototypes after k iterations. Table 1 provides the synopsis of the LBG

(i.e x ∈ S[j] → ∀i ∈ [0, . . . , 2 k -1], d(x, E[j]) ≤ d(x, E[i])).
In this synopsis, the centroid function determines the gravity center of a dataset S.

Table 1. Synopsis of LBG algorithm.

LBG(S, k) S ′ [0] ⇐ centroid(S) FOR i = 1 TO k FOR j = 0 TO 2 k-1 E[2j] ⇐ S ′ [j] + ǫ j E[2j + 1] ⇐ S ′ [j] -ǫ j ENDFOR {S[0], . . . , S[2 k -1]} ⇐ clustering(S, E) FOR j = 0 TO 2 k -1 S ′ [j] ⇐ centroid(S[j]) ENDFOR ENDFOR RETURN S ′

Tabu Search (TS)

Many meta-heuristics approaches exist to solve hard optimization problems, a set of them are called tabu search [START_REF] Glover | Tabu search[END_REF] . Those ones belongs to iterative neighbourhood search methods. The general step, at the it iteration, consists in searching, from a current solution θ it , the next best solution θ it+1 in a given neighborhood. This new solution may be less efficient than the previous one; however this avoids local minimum trapping problems. That is why TS uses short memory to avoid moves which might lead to recently visited solutions (tabu solutions). TS methods generally incorporate explicit strategies to control the efficiency of the search space exploration. These strategies are grouped in two terms: intensification and diversification. In a promising region of space, the first strategy allows extensive search of the path to find a best solution. However, if the search is in a region of space for which the solutions are poor or if the extensive search cannot produce better solutions, the second strategy enables large changes of the solution in order to find quickly another promising region. These two strategies are generally applied alternatively. Although the basic idea of TS is straightforward, the choice of solution coding, objective functions, neighborhood, tabu solutions definition, intensification and diversification strategies, all depend on the application problem.

TS Model Selection Method

By studying the SVM formulation problem, one notices that the number of support vectors used by BDF increases with the problem size [START_REF] Steinwart | Sparseness of support vector machines -some asymptotically sharp bounds[END_REF] . As the objective of our model selection is to produce a fast and efficient decision function, increasing the number of support vectors is interesting only if it is linked to a significant improvement in the recognition rate. For the same reason, features selected in a BDF is dependent of recognition rate improvement.

The idea of our method is to produce fast and efficient SVM BDF using few support vectors and few features. To that aim, a new Decision Function Quality (DFQ) criterion, based on regularization theory, has been defined which corresponds to a compromise between efficiency and complexity (c.f. Section 3.1). A SVM is therefore trained from a small dataset S ′ t representative of the initial training set S t in order to decrease the complexity of the BDF. The LBG algorithm has been used to perform the simplification of the initial dataset (c.f. Section 3.2). As the number of prototypes produced by LBG algorithm (2 k by class) cannot be easily fixed in an arbitrary way, a significant concept in our method is to regard parameter k as a variable of the model selection problem. The optimization of SVM DFQ thus requires, for a given kernel function K, the choice of: the simplification level k, the feature subset β, the regularization constant C and kernel parameters (σ with gaussian kernel). The search of the values of those variables is called model selection. Let θ be a model, k θ , β θ , C θ and σ θ be respectively the values of all the variables to tune, and q(θ) be the value of the DFQ criterion for a model θ (c.f. Section 3.1). The synopsis in Section 3.3 gives the details of the estimation of DFQ criterion from a model θ and a learning set S l with q(θ) ≡ SVM-DFQ(θ, S l ) the objective function which must be optimized. The search for the exact θ * which optimizes q(θ) not being tractable, we decide to define a specific TS metaheuristic method (c.f. Section 3.4) for the model selection problem with adapted intensification and diversification strategies (cf. Sections 3.5 and 3.6).

Decision Function Quality (DFQ)

Tabu Search Model Selection for SVM

We consider that the DFQ of a given model θ depends on the recognition rate R R but also on the complexity C P of the decision function h θ when processing time is critical. Let q(θ) = R R (h θ ) -C P (h θ ) be the DFQ. That definition is based on regularization theory [START_REF] Tikhonov | Solution of Ill-posed Problems[END_REF][START_REF] Tikhonov | Ill-Posed Pproblems: Theory and Applications[END_REF] . The fitting term is expressed in terms of recognition rate (R R ). The smoothness term is expressed in terms of model complexity (C P ). For SVM, the complexity of the decision function depends on the number of both support vectors and selected features. The empirical model we propose to model the complexity of a SVM BDF is:

C P (h θ ) = c p1 log 2 (n SV ) + c p2 log 2 (cost(β)) (5)
β is a boolean vector of size n representing selected features. Constants c p1 and c p2 fix the trade-off between classification rate improvement and complexity reduction. Let κ i denote the cost for the extraction of the i th feature, the value of cost(β) linked to the subset of selected features is defined by: cost(β) = β i κ i . When those costs are unknown, κ i = 1 is used for all features. Strictly speaking, a doubling of the number of support vectors (extraction cost) is accepted in our learning method if it is related to a recognition rate increase by at least c p1 (respectively c p2 ).

Simplification step

A natural way to reduce the complexity of SVM decision functions is to reduce SVM training set size. One possibility of doing that is to produce prototypes which efficiently sum up examples close to them. The LBG algorithm (c.f. Section 2.4) is used to produce 2 k prototypes for each class into a two class problem. The reduced dataset is a more or less simplified version of the initial one according to the parameter k value. The algorithm in Table 2 gives the details of this simplification (to speed up model selection, at each new value of k, the simplification result is stored for future steps which might use the same simplification level). Table 2. Synopsis of simplification step.

Simplification(S,k) S ′ ⇐ ∅ FOR c ∈ {-1, +1} T = {x | (x, c) ∈ S} IF 2 k < |T | THEN T ′ ⇐ LBG(T, k) ELSE T ′ ⇐ T S ′ ⇐ S ′ ∪ {(x, c) | x ∈ T ′ } ENDFOR RETURN S ′

DFQ estimation

The Decision Function Quality (DFQ) criterion of a specific model θ is evaluated from a learning dataset S l . The synopsis provided in Table 3 gives details on how the value of that criterion is determined. Let S t , S v denote the datasets which are produced by a random split (Split function in synopsis SVM-DFQ) with

|S t | = 2 3 |S l |, |S v | = 1 3 |S l |. S t ,
d β : d β (x i , x j ) = n l=1 β l (x l i -x l j ) 2 .

SVM-DFQ(θ,S

l ) (S t , S v ) ⇐ Split(S l ) S ′ t ⇐ Simplification(S t ,k θ ) h θ ⇐ TrainingSVM(S ′ t ,K β θ ,C θ ,σ θ ) (m correct -1 , m correct +1 ) ⇐ TestingBDF(h θ ,Sv) R R ⇐ m correct -1 2m-1 + m correct +1 2m+1 C P ⇐ Complexity(h θ ) q(θ) ⇐ R R -C P

TS specification

The objective function q to be optimized represents the quality of the BDF h θ (c.f. Section 3.1). Our problem is to choose an optimal model (good sub-optimal solution to be exact) θ * for a function q when c p1 and c p2 are fixed. A model θ can be represented by a set of n ′ integer variables

θ = (θ 1 , . . . , θ n ′ ) = (β 1 , . . . , β n , k, C ′ , σ ′ ). Notations k θ , β θ , C θ and σ θ used in Section 3.1 correspond respectively to k, (β 1 , . . . , β n ), √ 2
C ′ and √ 2 σ ′
in that integer representation of θ model. One basic move in our TS method corresponds to adding δ ∈ [-1, 1] to the value of a θ i , while preserving the constraints of the model which depend on it (i.e. ∀i ∈ [1, . . . , n ′ ], θ i ∈ [min(θ i ), . . . , max(θ i )] where min(θ i ) and max(θ i ) respectively denote lower and upper bound values of θ i variable). From these constraints, the list of all possible neighborhood solutions is computed. From these possible solutions, the one which has the best DFQ and which is not tabu is chosen. The set of all Θ it tabu solutions θ which are tabu at the it iteration step of TS is defined as follows:

Θ it tabu = {θ ∈ Ω | ∃ i, t ′ : t ′ ∈ [1, . . . , t], θ i = θ it-1 i ∧ θ i = θ it-t ′ i }
with Ω the set of all solutions and t an adjustable parameter for the short memory used by TS (for experimental results t = n ′ i=1 max(θ i )min(θ i )). The idea is that a variable θ i could be changed only if its new value is not present in the short memory. Then, our TS method does not go back to a value of θ i previously changed in short time, avoiding by that mechanism undesirable oscillation effects. Tabu status of solutions Θ it tabu may prohibit some attractive moves at iteration it. Therefore, our TS uses an aspiration criterion which consists in allowing a move (even if it is tabu) if it results in a solution with an objective value better than that of the current best-known solution.

The initialisation of model θ with our TS model selection is the following:

• k θ = ⌊log 2 (max(m +1 , m -1 )) /3⌋, • C θ = 1 and σ θ = 1,
• ∀i :

β i = 1.
In the expression of k θ , m +1 and m -1 are respectively the number of examples of positive and negative classes in binary sub-problems. The value of k θ allows to start with sufficiently simplified datasets in order to have low training times with SVM for the first intensification step.

Using intensification and diversification strategies can improve TS methods [START_REF] Glover | Tabu search[END_REF] . The model selection such as it was defined has to deal with two kinds of problems. First, testing all moves between two iterations with a great number of features can be time consuming. In particular, it is a waste of time to explore moves which are linked to features when the actual solution is not sufficiently promising. Therefore, focusing on moves which are only linked to SVM hyperparameters or simplification level is more efficient to discover new promising regions. Second, it is difficult for TS method to quickly escape from deep valleys or big clusters of poor solutions while only using the short memory and resulting in not tabu solutions. Using more diversified solutions can overcome this problem. This is dealt with by increasing step size (δ > 1) of moves and by forcing the use of all types of moves (except feature selection moves for the reason stated above).

In our TS method, intensification and diversification strategies are used alternatively and begin with the intensification strategy. The next two subsections give details on these two strategies.

Intensification strategy

In the intensification algorithm sysnopsis shown in Table 4, ExtensiveSearch explores all eligible basic moves, whereas FastExtensiveSearch explores only eligible basic moves which are not related to feature selection (i.e. changing the value of β). η promising controls when the actual solution is considered as sufficiently promising and this one permits to switch between the two functions stated above. BestNotTabu corresponds to the move procedure selection described in the previous Section (the best tabu solution is chosen if all moves are tabu). In this synopsis, θ intensification corresponds to the best solution found into a same phase of intensification, although θ best-known corresponds to the best solution found in all intensification and diversification steps. n max is the maximum number of intensification iterations for which no improvements of the last best intensification solution (θ intensification ) are considered as failure of the intensification strategy. n failure counts the number of failures of intensification strategy. If n failure is higher than a fixed maximum number of failures max, our TS method stops and returns the solution θ best-known . If a solution in Θ next has a QDF which is better than θ best-known , aspiration mechanism is used. That solution is selected as the new θ best-known and n failure is reset to zero. Table 4. Synopsis of TS intensification strategy.

Intensification(θ it ) IF q(θ it ) > η promising • q(θ best-known ) THEN Θ next ⇐ ExtensiveSearch(θ it ) ELSE Θ next ⇐ FastExtensiveSearch(θ it ) θ it+1 ⇐ BestNotTabu(Θ next ) IF q(θ it+1 ) > q(θ intensification ) THEN θ intensification ⇐ θ it+1 n WithoutImprove ⇐ 0 ELSE n WithoutImprove ⇐ n WithoutImprove + 1 IF n WithoutImprove > n max THEN n failure ⇐ n failure + 1 stategy ⇐ Diversification IF n failure > n max failure THEN STOP

Diversification strategy

In the diversification algorithm sysnopsis shown in Table 5, an eligible variable (one which does not have a link with features) is selected (SelectEligibleVariable) by random and a jump of ±δ is performed by modifying the selected variable in the actual solution. There are only two explored moves (TwoMove) to force the diversification of explored solutions. The jump size increases with the number of successive failures (n failure ) of the intensification strategy in order to explore more and more distant regions. During the diversification iterations, the best visited solution is stored (θ diversification ) and selected as the starting solution for the next intensification step (θ it intensification = θ it-1 diversification ). At any time of TS exploration, if aspiration is in-volved, the strategy automatically switches to intensification and the number of failures is reset (n failure = 0). Table 5. Synopsis of TS diversification strategy.

Diversification(θ it ) δ ⇐ n failure+1 i ⇐ SelectEligibleVariable Θ next ⇐ TwoMove(θ it , i, δ) θ it+1 ⇐ BestNotTabu(Θ next ) IF q(θ it+1 ) > q(θ diversification ) THEN θ diversification ⇐ θ it+1 n diversification ⇐ n diversification + 1 IF n diversification > n max • n failure THEN θ it+1 ⇐ θ diversification stategy ⇐ Intensification

Experimental results

Two types of experiments were performed. In the first one, the abilities of our TS model selection were tested on well-known benchmark datasets [START_REF] Lebrun | A new model selection method for SVM[END_REF] . In the second one, the goal was to produce a fast pixel classification by combining several SVM inducers of low complexities [START_REF] Lebrun | Fast pixel classification by SVM using vector quantization, tabu search and hybrid color space[END_REF] . Pixel classifiers were used to define a fast and efficient segmentation scheme for cell microscopic image [START_REF] Lebrun | A fast and efficient segmentation scheme for cell microscopic image[END_REF] .

Benchmark datasets

For the experiments, datasets Adults, OpticDigit, Letter and Shuttle are from UCI repository [START_REF] Blake | UCI repository of machine learning databases[END_REF] ; dataset Web comes from Platt experiments 3 ; and dataset ClassPixel comes from our works [START_REF] Lebrun | A fast and efficient segmentation scheme for cell microscopic image[END_REF] . Table 6

Influence of simplification level

To illustrate the importance of simplification step in our model selection method, this one is tested when the value of k is fixed for the TS process (feature selection possibility of our TS method is not used by forcing FastExtensiveSearch in our intensification strategy). The idea is to observe the evolution of BDF recognition rate according to simplification intensity. Table 7 summaries results obtained with the OpticDigit dataset for k ∈ {0, 2, 4, 8} (this corresponds to have respectively {1, 4, 16, 64} prototype examples by class). Those results show that each individual binary sub-problem is more or less sensitive to simplification level in a same multi-class problem. For several binary sub-problems, few prototypes (i.e. low values of k) are sufficient to produce efficient BDF with SVM learners. The selection of the simplification level (k value) is then dependent on each binary sub-problem in a multi-class problem when QFD criterion must be optimized. The choice of complexity penalty coefficient (c p1 ) also has an impact on selection of the optimal simplification level. For example with Table 7 results, if c p1 is fixed to 0.01, the k values which optimize DFQ criterion are respectively {2, 4, 4, 4, 8} . If c p1 is changed to 0.002, the k optimal values become {4, 6, 4, 8, 8}.

Table 7. Results with OpticDigit dataset for different simplification levels (value of k) on some binary subproblems involved in an one-versus-all decomposition. RR i is the recognition rate on test set for produced BDF in which i represents the digit in the binary sub-problem to identify for the others. Cp 1 is fixed to 0.01. [START_REF] Lebrun | Fast pixel classification by SVM using vector quantization, tabu search and hybrid color space[END_REF][START_REF] Lebrun | A new model selection method for SVM[END_REF] . From all those experiments one can conclude that increasing the training set size (number of prototypes) does not alway significantly improve the recognition rate for a specific binary problem. The main reason of that effect is that the level of redundancy in a dataset is variable. Moreover, complexity of a produced BDF is directly linked to training set size [START_REF] Lebrun | Fast pixel classification by SVM using vector quantization, tabu search and hybrid color space[END_REF][START_REF] Lebrun | A new model selection method for SVM[END_REF] . Those preliminary results show the importance of using DFQ criterion as an objective function because several θ models have very close recognition rates but great variations on their complexities.

k R R0 R R2 R R5 R R8 R R9 0

Tuning parameters of our TS method

The objective of our model selection method is to automatically select efficiently all free parameters (θ model) involded in the construction process of SVM BDF in order to optimize DFQ, but our TS method also has to introduce other free parameters (η promising , n max , n max failure ). Several experiments have been realized to determine efficient setting for them [START_REF] Lebrun | A new model selection method for SVM[END_REF] . Results from: (1) η promising = 0.99 is an efficient threshold value to determine if TS basic moves must incorporate feature selection possibility, (2) n max = 5 and n max failure = 5 are a good compromise between learning time reduction and the importance of TS exploration for determining when TS must be terminated.

Results with different datasets

We applied the TS model selection described in Section 3 with settings given in Section 4.3. Two penalty configurations are used: (1) c p1 = c p2 = 0.01, (2) c p1 = 0.0001 and c p2 = 0. For the first configuration, doubling the number of support vectors or the number of features used is only profitable if recognition rate is increased of at least 1%. For the second configuration, the idea is to be very close to classical SVM training: SVM hyper-parameters selection corresponding to minimizing expected error rate (c p1 is not equal to zero, but close to it, in order to avoid intractable SVM training time) with no feature selection possibility (i.e only FastExtensiveSearch with Intensification strategy). Each penalty configuration is used with datasets presented in Section 4.1. Table 8. Total training time ( T T ), mean of simplification level ( k), total number of support vectors ( SV ), average number of features (n f ) and recognition rate on test set ( RR) for the nc produced BDF (only one BDF is produced when nc = 2) with our TS model selection method. Two penalty configurations are used with the benchmark datasets: cp 1 = cp 2 = 0.01 for config. 1 and cp 1 = 0.0001 and cp 2 = 0 for config. 2. [START_REF] Lebrun | A new model selection method for SVM[END_REF] ; results show that our TS model selection method can produce a range of BDF which have different trade-off between celerity and precision. Of course, the good penalty trade-off is application dependant, but results in Table 8 show that our method can produce, for a same penalty configuration, fast BDF which have globally efficient generalization capacities through datasets of different natures.

If training times are compared to the classical grid-search technique (a grid points in the kernelparameter-and-C plane [START_REF] Abe | Support Vector Machines for Pattern Classification[END_REF] ) without simplification of training set [START_REF] Lebrun | A new model selection method for SVM[END_REF] , training time is greatly reduced (except with very low penalty values). Moreover, our method can also perform in addition feature and simplification level selections. Results in Table 8 show that the number of features used has been greatly reduced when configuration 1 and configuration 2 are compared. Time to proceed at model selection including feature selection (i.e. configuration 1) is tractable with our TS method if penalty coefficients are not too low (results, not presented here [START_REF] Lebrun | A new model selection method for SVM[END_REF] , show that model selection time increases quickly while penalty coefficient decreases). In the other case (i.e. configuration 2), feature selection possibility must be discarded. Let n k be the number of solutions θ examined by TS for which simplification level is equal to k. Global SVM training time of our method is O( n k (2 k ) γ ) with 2 < γ < 3. The examination of our TS method shows that n k decreases while k increases. This effect increases when c p values increases and explains the efficient training time of our TS model selection.

Fast pixel classification problem

Pixel classification is commonly used as an initial step in color image segmentation schemes [START_REF] Vandenbroucke | Color image segmentation by pixel classification in an adapted hybrid color space: application to soccer image analysis[END_REF][START_REF] Meurie | A comparison of supervised pixels-based color image segmentation methods. application in cancerology[END_REF][START_REF] Lebrun | Fast pixel classification by SVM using vector quantization, tabu search and hybrid color space[END_REF] for the extraction of seeds. As for any classification problem, the choice of an inducer which produces efficient decision functions having good generalization performances is critical. Working with any machine learning algorithm for pixel classification involves to take into account not only the recognition rate of the base inducer but also the processing time needed to perform pixel classification of all the pixels in an image. About millions of accesses to SVM inducers per image are necessary for that kind of application [START_REF] Lebrun | A fast and efficient segmentation scheme for cell microscopic image[END_REF] . Therefore, our model selection method is adapted to produce fast and efficient pixel classification. Vector quantization is used in order to reduce the inherent redundancy present in huge pixel databases. Feature selection in our method is used to select an adapted hybrid color space [START_REF] Vandenbroucke | Color image segmentation by pixel classification in an adapted hybrid color space: application to soccer image analysis[END_REF][START_REF] Lebrun | Fast pixel classification by SVM using vector quantization, tabu search and hybrid color space[END_REF] . The ClassPixel dataset is built from 8 microscopic images of bronchial tumors where ground truth is given by experts 30 (see fig. 1(a) and 1(b) which show respectively a cellular image and its corresponding expert segmentation). Results in Table 8 show that it is possible to produce efficient BDF with low complexity for that problem. If decomposition of combination scheme is changed to one-versus-one (c p coefficients are also changed), it is possible to increase recognition rate (R R = 86.7%) and decrease complexity ( SV = 10, nf = 3) of pixel classifiers. shows that shapes of nucleus and cytoplasm are well identified. Additional results show that pixel classification permits to produce a fast and efficient segmentation scheme for cell microscopic image 30 . is proposed to achieve a good compromise between fast decision process and precision of that decision.

Conclusion

A new learning method based on SVM inducers

To that aim, we have proposed: 4. To define a quality criterion, called DFQ, which corresponds to a trade-off between low complexity and precision of a SVM decision process.

5.

To define an adapted TS model selection which efficiently tunes parameters linked to the first three key points in order to optimize the DFQ criterion.

The objectives of the proposed learning method based on TS model selection is to produce BDF which have threefold advantages: high generalization abilities, low complexities and selection of an efficient features subsets. Experimental results on benchmark datasets illustrate that our TS selection method realizes those objectives. It also shows how to efficiently fix internal parameters of our TS method. Other experimental results for a cellular microscopic segmentation application shows that pixel classification can be fast and efficient. Resulting segmentations will be helpful for analysis, in particular for cancerous diagnostic-helping.

Future works

Future works have to deal with two topics. In the first one, we want to improve our model selection method with SVM inducers. In the second one, we have to compare the proposed method with other methodologies.

To improve the proposed TS model selection, several directions could be explored:

• Taking into account multi-class recognition rate and the total complexity of all BDF (induced by the binary decomposition) in the DFQ criterion. Recent results [START_REF] Lebrun | An EA Multi-model selection for SVM Multiclass schemes[END_REF] show that optimizing individually each BDF implied in a combination scheme does not necessary produce the optimal multi-class scheme. Moreover, in our case, reducing the complexity of a specific BDF could have a significant decrease of the binary recognition rate for that BDF, but a lesser significant decrease of the multi-class recognition rate for the combination scheme in which that BDF is used. More generally, this problem refers to the question on how to combine several classifiers together in order to achieve improved performance [START_REF] Kuncheva | Combining Pattern Classifiers: Methods and Algorithms[END_REF] .

• Extending TS model selection in order to have an efficient feature selection for the global multi-class problem. Indeed, feature selection is independently well tuned for a specific BDF, but the union of used features by all BDF in a multi-class decomposition is generally more important than the average of those ones. New type of TS moves must be defined to perform an efficient multi-class feature selection which preserves the global multi-class recognition rate for a given combination scheme, but makes sure that the union of every selected feature subset has the smallest possible size. Complexity term in the DFQ criterion must be also changed to favor that possibility.

• The influence of other simplification methods [START_REF] Yu | Classifying large data sets using SVM with hierarchical clusters[END_REF][START_REF] Tsang | Core vector machines: Fast SVM training on very large data sets[END_REF][START_REF] Ou | Expediting model selection for SVMs based on data reduction[END_REF] has to be quantized. In particular, QV methods can be time consuming when datasets have million of examples. For instance, using hierarchical clustering tree algorithms can speed up this simplification step. Another way is to directly work with several pruned versions of hierarchical tree database representations [START_REF] Yu | Classifying large data sets using SVM with hierarchical clusters[END_REF] . New moves for our TS model selection must be defined in order to permit to un-prune or prune the tree according to the promising status of regions and the complexity variations of DFQ criterion.

Comparison with other methodologies could be devised in two ways:

• SVM algorithms have efficient generalization propriety in the machine learning framework but other learning algorithms like Neural Networks (NN) or decision trees also have that propriety [START_REF] Bishop | Neural networks for pattern recognition[END_REF][START_REF] Haykin | Neural Networks: a comprehensive foundation[END_REF][START_REF] Breiman | Classification And Regression Trees[END_REF][START_REF] Quinlan | C4.5: Programs for Machine Learning[END_REF][START_REF] Kecman | Learning and soft computing[END_REF] . It will be interesting to substitute SVM for one of them. The problem is how to compare complexity of those different inducers. For instance with NN, reducing the number of examples in training set has no impact on NN complexity, but reducing the number of neurons used with a NN has a great impact.

• Other meta-heuristic methods exist to optimize DFQ criterion like simulated annealing, evolutionary, particle swarm or ant colony algorithms [START_REF] Coello | Evolutionary Algorithms for Solving Multi-Objective Problems[END_REF][START_REF] Engelbrecht | Fundamentals of Computational Swarm Intelligence[END_REF] . It will be interesting to compare them on the model selection problem. In terms of process time. Another interesting possibility, with meta-heuristic algorithms that find multiple solution [START_REF] Engelbrecht | Fundamentals of Computational Swarm Intelligence[END_REF] , is that a set of efficient models could then be produced in the framework of multi-objective optimization. Different realizations of the compromise between low complexity and precision could be produced without explicitly fixing c p coefficient values in QDF criterion. The selection of the classifier which has the best compromise will be determined later in function of application constraints.

  Figure 1(c) illustrates pixel classification for a cellular image (fig. 1(a)) when one-versus-one combination scheme is used. Comparing the pixel classification result (fig. 1(c)) to the expert segmentation (fig. 1(b))

Figure 1 :

 1 Figure 1: (a) Microscopic cellular image (RGB, 752x574 pixels) stained with international coloration of Papanicolaou. (b) expert segmentation of the microscopic image: background (black), cytoplasm (blue) and nuclei (green). (c) pixel classification results with BDF produced by our TS model selection method.

  Tabu Search Model Selection for SVM algorithm in which ǫ j represents the added noise to create two prototypes from existing ones. Those prototypes are used to perform the clustering of dataset S with respect to minimal distance

  S v are respectively indicate databases used for training SVM (training dataset) and for recognition rate estimation (validation dataset). This dissociation is essential to avoid the risk of overfitting when empirical estimation is used. The SVM training step is realized by using the SMO algorithm version of the Torch library 47 . When SVM training is performed with unbalanced class datasets, it is more suitable to use Balanced Error Rate (BER) instead of classical Error Rate for the estimation of recognition rate. Recognition rate formulation (noted R R ) in Table 3 corresponds to BER estimation where m y represents the number of examples in each class (y ∈ {+1, -1}) and m correct y the number of examples correctly identified. . The kernel functions K β used for training SVM are defined from a distance

  By using d β in

	the kernel function, the feature selection problem is
	embedded in the model selection problem. For this
	study, only Gaussian kernels K G β = exp(-d 2 β /λ 2 1 ) are
	used.

Table 3 .

 3 Synopsis of DFQ estimation for a specific model θ.

Table 6 .

 6 provides statistics on those datasets with m, n c and n f respectively the number of examples, the number of classes and the number of features (learning and test sets respectively have 2/3 and 1/3 of datasets size. Test sets are used to estimate recognition rate (R R ) after TS model selection step). Datasets description.

	bases	m	n c n f
	Adults	45222	2 103
	OpticDigit	3823	10 64
	Letter	20000 26 16
	Shuttle	58000	6	9
	Web	49749	2 300
	ClassPixel 224636 3

Table 8

 8 reports results obtained by each TS model selection. Those results show that recognition rate of BDF with configuration 1 are close to those with configuration 2. Although, for the first one, the model complexity is greatly decreased by reducing both the number of support vectors and features used by a BDF. More penalty configurations have been also tested on those classification problems

Acknowledgements

This work was supported by Université de Caen Basse-Normandie under grants of Coeur-Cancer association and the Low Normandy council funds. It was developed in the "Service d'Anatomie et de Cytologie Pathologiques de l'Hôpital Pasteur de Cherbourg". The authors thank their technical staff for time spent to produce manual segmentations of cell microscopic images.