David Picard
email: david.picard@lip6.fr

Arnaud Revel
email: arnaud.revel@univ-lr.fr

Matthieu Cord
email: matthieu.cord@lip6.fr

An Application of Swarm Intelligence to Distributed Image Retrieval

Keywords: Distributed information retrieval, Content based image retrieval, Multi-agents system, Ant colony optimization

In this article, we introduce an application of swarm intelligence to distributed visual information retrieval distributed over networks. Based on the relevance feedback scheme, we use ant-like agents to crawl the network and to retrieve relevant images. Agents movements are influenced by markers stored on the hosts. These markers are reinforced to match the distribution of relevant images over the network. We tackle the use of the information gathered during previous search sessions. In order to match the different categories available on the network, we use several markers. Sessions searching for the same category will thus use the same makers. The system involves three learning problems: the selection of relevant markers regarding the searched category, the reinforcement of these markers and the learning of the relevance function. All of these problems are based on the relevance feedback loop. We test our system on a custom network hosting images taken from the well known TrecVid dataset. Our system shows a high improvement over classical content based image retrieval systems which do not use previous sessions information.

Introduction

The exponential growth of multimedia contents (i.e. images, videos or music) available on the Internet raises the question of the adaptability of searching tools to this highly distributed context. This is even more crucial when considering p2p networks: no centralized structure can gather all the information in the manner of classical web search engine. However, the decentralized nature of the production of multimedia content can have numerous advantages, such as the possibility of sharing computational and storage resources, the absence of data replication (and the questions of updating), etc. To benefit from such distributed structures, searching tools must be able to find the good location of relevant documents, e.g. to route the query among the peers correctly. This question has been widely studied in the p2p literature [START_REF] Sripanidkulchai | Efficient content location using interest-based locality in peer-to-peer systems[END_REF].

The question of image retrieval in this distributed context has been studied recently [START_REF] Chen | Scalable image retrieval with optimal configuration for p2p network database[END_REF][START_REF] Picard | Cbir in distributed databases using a multi-agent system[END_REF]. Classically, in Content Based Image Retrieval (CBIR), visual features are extracted from the images and then compiled into an index or signature [START_REF] Veltkamp | Content-based image retrieval system: A survey[END_REF]. To perform the retrieval, a similarity function is computed to compare the index of the query to those of the collection. A ranking of the results is produced according to the similarity and shown to the users. To further improve the quality of the retrieval, an interaction with the user, called relevance feedback [START_REF] Wood | Iterative refinement by relevance feedback in content-based digital image retrieval[END_REF][START_REF] Huang | Image retrieval with relevance feedback: From heuristic weight adjustment to optimal learning methods[END_REF], can be added. The user labels a fraction of the results, and the similarity function is updated consequently. Some machine learning techniques have been widely used in this case, and have shown very good improvements. Distributed CBIR is more challenging. In order to be efficient, distributed systems shall include the relevance feedback scheme but also a network exploration strategy [START_REF] Chen | Scalable image retrieval with optimal configuration for p2p network database[END_REF]. Given a network of computers hosting images, systems must find the locations of relevant images, before any similarity learning. We have previously proposed such a CBIR extension to distributed sources based on biologically inspired multi-agents systems. In this system, the ant-like behavior of the agents leads to the optimization of the source selection in which we perform the retrieval, with successful results [START_REF] Picard | Image retrieval over networks : Active learning using ant algorithm[END_REF].

The main purpose of this paper is to deal with long-term memory of network based system for information retrieval. Indeed, the main drawback of classical Information Retrieval (IR) systems, is their absence of memory regarding previous queries. In the case of a widely used and highly distributed system, we dispose of numerous search sessions. The challenge is to be able to re-use the knowledge brought by users in past search sessions to improve future sessions. In this context, the improvement can be done in two different ways: either by updating the similarity function according to the previous sessions, or by improving the selection of the images collections regarding the locations previously learned. In this paper, we undertake to improve the source selection stage by using the relevance feedback of past sessions only. This leads to a threefold learning problem : learning paths during the search session, merging paths learnt during previous search sessions, and learning the similarity function. We introduce a multiple-layered architecture to handle the three learning problems in a unified framework. We use an ant-like multi-agents system that learns the paths leading to relevant images collections regarding the searched category.

In the next section, we introduce a biologically inspired multi-agents systems (MAS ) for information retrieval. In section 3, we describe how the system works for a single session, which we call our "intra-session" learning strategy. The use of several previous sessions to further improve the system, which is called the "inter-sessions" learning strategy, is shown in section 4. We then present extensive experiments done on an ad hoc network, using the TrecVid'05 image dataset.

Multi-agents Systems for information retrieval

Distributed information retrieval (IR) systems need to perform three tasks [START_REF] Callan | Distributed information retrieval[END_REF], namely:

1. Selecting the collections in which performing the search. 2. Processing the documents on the selected collections. 3. Merging the results from the selected collections.

The second step is well known, as it does not differ from classical IR. The third step might contain difficulties, especially when the measure used to produce the results on each source are not directly comparable. This is often the case in distributed CBIR where different collections may not use the same indexing techniques [START_REF] Berretti | Merging results for distributed content based image retrieval[END_REF]. However, the first step is, to our minds, the more challenging. The ever growing number of sources forbids the exhaustive propagation of the query to each collection: Relevant sources must be identified so as to optimize the use of available resources. Typical problems involve optimal routing to minimize bandwidth waste and correct distribution of the processing tasks among the computational resources. Multi-agents system have proved to be highly efficient for these tasks specific to distributed systems. Multi-agents systems are often used to parallel processes or to add robustness (by adding redundancy). In our work, we focus on Mobile Agents, a particular subset of MAS with nice properties for information retrieval. Mobile agents are autonomous computing software with the ability to migrate its executable code from one peer of the network to another and to continue its execution there [START_REF] Lange | Mobile objects and mobile agents: The future of distributed computing?[END_REF]. Mobiles agents have been the focus of many researches in the late 1990s. There are good reasons to use mobile agents for information retrieval [START_REF] Lange | Seven good reasons for mobile agents[END_REF], such as the absence of a global structure in the network, the natural discovery of new collections, the automatic paralleling of the processing, etc. Recently, search engines based on mobile agents have been built [START_REF] Volker Roth | A distributed contentbased search engine based on mobile code[END_REF][START_REF] Revel | Web-agents inspired by ethology: a population of "ant"-like agents to help finding user-oriented information[END_REF][START_REF] Brazier | Agent-based information retrieval: Legal and technical considerations in a simple case[END_REF][START_REF] De Groot | Issues in a mobile agent-based multimedia retrieval scenario[END_REF].

To further improve these agent based search engine, the next step is the introduction of swarm intelligence algorithms. Ant Colony Optimization [START_REF] Dorigo | Ant colony optimization artificial ants as a computational intelligence technique[END_REF] is an optimization strategy inspired by the behavior of ants while foraging. By modifying the environment, agents contribute to a collaborative solving of the problem [START_REF] Deneubourg | Collective patterns and decision-making[END_REF]. It has been shown to be efficient in various optimization problems like Quadratic Assignment Problem, Traveling Salesman Problem [START_REF] Dorigo | Ant colony system: A cooperative learning approach to the traveling salesman problem[END_REF], with applications to network routing, for instance [START_REF] Caro | AntNet: a mobile agents approach to adaptive routing[END_REF]. In the case of information retrieval, many agents try to collectively find relevant documents during a search session leading to a better routing of the query, like in [START_REF] Revel | Web-agents inspired by ethology: a population of "ant"-like agents to help finding user-oriented information[END_REF]. As there are many users of the network, the interaction of different sets of session related agents shall lead to further improvement.

In the specific case of distributed CBIR based on relevance feedback scheme, the three steps defined at the beginning of this section have to be done at each round. We expect the use of ACO like algorithm to be able to boost the source selection step by merging the information gathered by many agents (owned by several users) regarding the relevant hosts.

Intra-session learning strategy

In the hereby section, we recall the first system addressing distributed CBIR we developed [START_REF] Picard | Image retrieval over networks : Active learning using ant algorithm[END_REF]. The design is based on the relevance feedback scheme of classical CBIR tools, with the use of ant-like agents to handle the step 1 of distributed retrieval.

Selection strategy

To address the problem of the selection of sources, we introduce the relevance r i of a host i, which is the number of relevant images it contains over the number of images in its collection. Thus, a collection with only relevant images has a relevance of 1, whereas a collection with no relevant image has a relevance of 0. The strategy we proposed consists in selecting a higher number of images from hosts with a high relevance. However, the relevance of each host cannot be known prior to the query, as we do not have the information of which image is relevant or not. Thus, we proposed to learn the relevance of the host in interaction with the user, using the relevance feedback loop. Let us define the approximate relevance ri of host i as the number of images from i which were labeled relevant by the user over the number images from i that were labeled by the user (regardless their labels). In fact, as the number of labels increases, the approximate relevance tends to the real relevance. During the relevance feedback loop, we select images from the hosts with a high approximate relevance, thus returning a higher number of relevant images.

The global strategy within a search session can be sum up as follows:

1. Let A(n) be the training set of images {x j } n and their respective labels {y j } n at iteration n of the relevance feedback loop. 2. According to A(n) the approximate relevance ri and the relevance function f A(n) are computed. 3. Using f A(n) and ri , I images {x j } n+1 are selected, with a number of images proportional to ri selected from i, ∀i.

The training set for the next iteration is built as

A(n + 1) = A(n) ∪ {x j , y j } n+1
, where y j are the labels given by the user to the I selected images {x j } n+1 .

System overview

Figure 1 describes our system. The user begins the query by giving an example or a set of examples to an interface [START_REF] Berretti | Merging results for distributed content based image retrieval[END_REF]. A similarity function based on these examples is built (2). To build the similarity, visual features are extracted from the examples (distributions of colors and textures obtained by quantization of color and texture spaces over a set of training images), and machine learning techniques such as SVM are used [START_REF] Cortes | Support-vector networks[END_REF][START_REF] Tong | Support vector machine active learning with applications to text classification[END_REF]. Mobile agents are then launched with a copy of this similarity function [START_REF] Callan | Distributed information retrieval[END_REF]. Every host of the network contains an agent platform in order to be able to receive and execute incoming mobile agents. These agents travel through the network according to movement rules related to numerical markers present on each host reflecting the relevance of the hosts (see below 3.3) (4). On each platform, an agent indexing the local images is run. The incoming mobile agent sends the similarity function to the index agent which returns the most informative images.

As soon as they receive the answer of the index agent, the mobile agents return to the user's computer [START_REF] Chen | Scalable image retrieval with optimal configuration for p2p network database[END_REF] and the results are displayed on the interface [START_REF] Cord | Image retrieval using long-term semantic learning[END_REF]. The user can label these results (1: relevant, -1: irrelevant), and the similarity function is updated consequently (7a) as well as the relevant paths of the network (7b). As the similarity function we use is based on SVM analysis [START_REF] Cortes | Support-vector networks[END_REF], the update stage only consists in adding the results and their labels to the training set and to train a new SVM. Mobile agents are then relaunched with the improved similarity function. The interactive loop consists in several launching of mobile agents and labeling of the results [START_REF] Deneubourg | Collective patterns and decision-making[END_REF]. At the end of the interaction, mobile agents are launched for a very last time in order to retrieve the best results from each host [START_REF] Dorigo | Ant colony optimization artificial ants as a computational intelligence technique[END_REF]. The number of retrieved images is proportional to the level of the markers leading to this host. In combination with the ant-algorithm, this assures that most of the best retrieved images are provided by relevant hosts.

Learning the relevance of the hosts

The main key point of the introduced strategy relies on the estimation of the relevance of each host of the network at each relevance feedback round. As the number of hosts increases, it is not possible to visit them exhaustively to compute the approximate relevance anymore. Instead, we propose a stochastic exploration of the network, where relevant hosts are prioritized using and adaptation of ACO. Each host of the network is provided a marker (a numerical value) which acts as the pheromone used in ant-like strategies. Let us denote m i the marker associated with host i. Then, the probability for an agent to move from host s to host i is

P s→i = m i k∈dest m k (1)
Where dest is the set of possible destinations from s. Thus, the higher the value of the marker, the higher the probability for an agent to move there.

Markers are reinforced each time an agent returns to reflect the relevance of hosts, using the following rules:

m i ← αm i + βa i + γu i (2)
Where a i = 1 if i contains an image collection (0 if not), and u i = 1 if the image the agent has returned is labeled relevant (0 if not). 0 ≤ α < 1, β ≥ 0 and γ ≥ 0 are parameters of the system. With these reinforcements of markers, the probability for an agent to move to a host is directly linked with its approximate relevance (see section 5).

Inter-sessions learning strategy

As stated in the introduction, classical CBIR tools lack the reuse of the information injected in the system by the user through the relevance feedback loop. For instance, suppose several users have searched for images of cars, mountains or sporting events, each session totalizing 100 pairs of images and associated labels (in the form of either relevant or irrelevant). If we assume that different users have a consistent definition of the categories they are searching (i.e. they consider the same images as being relevant when searching for the same category), then the use of these previous labels can be a precious boost to the learning strategies involved in the retrieval of these three categories for later sessions.

Yet the problem is difficult. Since we have no other indication on the subject of a session than the set of labels gathered during the feedback loop, we have no a priori knowledge on which previous labels could be used for a new session. This weakly supervised learning problem has not been widely studied. The main development in this direction have been done regarding the update of the similarity between images to match our perception of similarity better. In the case of kernel based similarity, it can be done by learning the similarity matrix [START_REF] Heisterkamp | Building a latent semantic index of an image database from patterns of relevance feedback[END_REF][START_REF] Cord | Image retrieval using long-term semantic learning[END_REF]. To our knowledge, there has been no work on long-term distributed CBIR.

Thus, we propose to improve the source selection stage using long-term learning: within a search session, paths leading to relevant images are learned using relevance feedback. We intend to reuse previously learned paths for later sessions, so as to speed up the time taken to interactively learn the location of relevant images.

As there might be several categories of images the users can be looking for, a single marker on each host is not sufficient to match the relevance of hosts for all searched category. We propose to store P markers on each host, each one being related to a category. This forms a vector of dimension P , called m i for host i. We call the set of all markers {m i [c], i ∈ N } of the network N associated with a category c a plane. Let us denote p c the plane related to concept c, and P the total number of planes. The goal of long term learning is then to find values for each vector, such that each component of the vector reflects the relevance of the host regarding the corresponding category (as in figure 2).

With such an architecture, the retrieval involves three learning problems:

1. Selecting the plane corresponding to the searched category. 2. For the selected plane, improving the marker values so as to match the relevance of hosts. 3. Learning the relevance function.

The first and the third steps have to be done during a search session, whereas the second step can be done over many sessions by many users.

R b =     0.1 0.2 0.9 0.2     b c d e f a R c =     0.1 0.8 0.3 0.1     R d =     0.1 0.1 0.2 0.8     R e =     0.1 0.3 0.3 0.9     R f =     0.6 0.9 0.2 0.1    

Learning strategies

We focus on the first two learning problems. The third one is exactly the same as for the previously presented system, and is not detailed here. The selection of a plane and the learning of markers problems are interdependent. In fact, it is only possible to select a relevant plane if the markers have been learned and match the relevance of hosts regarding the considered categories. But is is also only possible to learn the markers if a plane has been selected. To tackle this dependence, we propose an iterative system that improves both stages at every step of the relevance feedback.

Let us first consider the plane selection, and suppose that markers have been correctly learned over past sessions. We define a selection function ψ s that given a marker vector m i returns the component p corresponding to category s:

ψ s : R P ′ → R (3)
m i → m i [p]
To produce a function ψ s , we assign a weight w j , 0 ≤ j ≤ P to each component of the markers vector space. The component p is sampled using the multinomial law M(1; w 1 , ..., w P ). As we have no a priori about which component is relevant to the searched category, we initialized the weights to 1/P . We then propose to learn the weights w j thanks to the relevance feedback loop. Each time the user labels an image retrieved using the plane p, we update w p as follows:

w p ← w p + ε(u -w p ) ( 4
)
Where u is as defined in 3.3, and ε is the learning rate. A new selection function is sampled each time an agent is launched in order to explore different planes before focusing on the most relevant. The learning rate is set to ensure convergence of the selection within a few iterations of relevance feedback.

Let us now consider the learning of markers, and suppose the relevant plane has been selected. As we have only one value per host, we have an optimization problem similar to the one presented in section 3 (see equation 2). Thus, we can use the same reinforcement rules so as to match the values of the selected plane with the relevance of the corresponding hosts regarding the searched category. The only difference with the previous system is that the markers are now updated over several sessions (issued by different users), improving the approximate relevance of the hosts.

Relevance feedback detail

The detail of an iteration of the relevance feedback loop can be described as follows:

1. Let A(n) be the training set of images {x j } n and their respective labels {y j } n at iteration n.

A selection function ψ A(n) is generated with the help of

A(n), that selects the plan p. 3. Thanks to p and A(n), the approximate relevance ri is computed based on the markers m i [p] of plane p.

A relevance function f

A(n) is trained upon A(n). 5. f A(n)
and the approximate relevance ri are used to select I images {x j } n+1 , such that the number of images retrieved from i is proportional to ri . 6. The next training set is defined by A(n + 1) = A(n) ∪ {x j , y j } n+1 , where y j are the labels given by the user to the retrieved images x j .

At each step of the relevance feedback, all the three problems (namely the selection of plane, the reinforcement of markers and the learning of the relevance function) are improved. The long-term improvement comes from the reinforcement of the markers m i [p] over several session, leading to a better approximation of the relevance of hosts. This improves the source selection stage of the distributed retrieval problem.

Theoretical Aspects

The three learning problems involved in our system are entangled, since they are needed to perform a single iteration of the relevance feedback loop. Moreover, the searched categories tend to a competitive specialization of the available planes due to the lack of prior knowledge on the location of categories. Thus, the overall dynamics are very complex. However, we can theoretically study the simpler case of a single plane used for a single category. In that case, we can show that the system converges to the reinforcement of paths leading to the relevant images regarding the category, with a close relation to the approximate relevance of hosts. We derive the following theorem: Theorem 1. Let m i (n) be the marker of host i at time n, then, it converges in probability to E[m i ]:

∀ε, ∀δ, ∃N | ∀n ≥ N ⇒ P (|m i (n) -E[m i (n)]| > ε) < δ (5)
To prove the theorem, we start by using Markov inequality:

∀∆ > 0, P (Y > ∆) ≤ E[Y ] ∆ (6)
on variable err defined by :

err = |m i (n) -E[m i (n)]| (7) then ∀ε, P (err > ε) ≤ E[err] ε (8) ≤ E[m i (n) -E[m i (n)]] ε (9) ≤ E[α n-1 m i (0) + n-1 0 α n-1-k βa i (k) + γu i (k) -E[m i (n)]] ε (10) ≤ α n-1 m i (0) + n-1 0 α n-1-k βE[a i ] + γE[u i ] -E[m i (n)] ε (11)
We remark that ∀n,

n-1 0 α n-1-k < 1 1 -α (12)
thus

P (err > ε) < α n-1 m i (0) + βE[a i ]+γE[u i ] 1-α -E[m i (n)] ε ( 13
)
From equation 2, we can express E[m i (n)] as:

E[m i (n)] = α n-1 m i (0) + βE[a i ] n-1 0 α n-1-k + γE[u i ] n-1 0 α n-1-k (14) = α n-1 m i (0) + βE[a i ] n-1 0 α k + γE[u i ] n-1 0 α k (15) = α n-1 m i (0) + ( 1 -α n-2 1 -α )(βE[a i ] + γE[u i ]) (16)
Replacing the expression of E[m i (n)], we obtain:

P (err > ε) < α n-2 βE[a i ] + γE[u i ] ε(1 -α) (17)
then, ∀δ, one can always choose N such that:

α N -2 < ε(1 -α) βE[a i ] + γE[u i ] δ ( 18
)
it follows that ∀n > N :

P (err > ε) < α N -2 βE[a i ] + γE[u i ] ε(1 -α) (19)
P (err > ε) < δ (20)
Thus we have shown that:

lim n→∞ P m i (n) = βE[a i ] + γE[u i ] 1 -α = 1 (21)
We can also express the approximate relevance of host i using u i . In fact, as the approximate relevance is the ratio of positive labels over the total number of label from i, it is directly equal to E[u i ]. Thus, using equation 21 for the special case β = 0, the probability of movement after a sufficient evolution of all markers is:

P s→i = m i k∈dest m k (22)
≈ γE[u i ] 1 -α 1 -α k∈dest E[u k ] (23)
≈ E[u i ] k∈dest E[u k ] (24)
Which is a normalized value of the relevance of host i. As many agents are launched (with the goal of retrieving a fixed number of images), the total number of images retrieved has a distribution over the hosts proportional to their relevance. Hence, the higher probability of retrieving images is from the most relevant hosts.

Experiments

In the hereby section, we present experiments made on custom networks of computers hosting images taken from the TrecVid'051 keyframes dataset. These networks have a low connectivity, which is also often the case of real world peer-to-peer networks. These experiments aim at testing the intersession system. A comparative experiment of the intra-session system (which measures the gain of using the location of the relevant data) can be found in [START_REF] Picard | Image retrieval over networks : Active learning using ant algorithm[END_REF]. We first introduce the setup used for the experiments, and then evaluate the system's overall performances. We further investigate the dynamics of our system.

Experimental setup

The dataset used consists in about 70000 images taken from the TrecVid'05 challenge. Images are extracted from videos of TV shows and are classified as various categories such as objects (bus, airplanes, ...), scenes (mountains, urban, ...), or more abstract concepts (explosion and fire, entertainment, charts, ...). The features we use consist in vectors containing 32 bins of colors and 32 bins of textures as described in [START_REF] Picard | Image retrieval over networks : Active learning using ant algorithm[END_REF].

We set two different configurations for our experiments, with different networks and category distribution. The first setup, noted A, tests the performances of the system. The second setup, noted B, investigates the evolution of the markers.

Setup A

Setup A is made of five hosts. The first computer is the starting point of the query, where agents are launched and retrieved. The four other computers are hosting image collections. Their contents are chosen so as to be visually similar. Only 10 categories are used for this experiment.

The parameters of this setup are as follows :

• For each retrieval session, feedback loops are conducted until 100 labels are gathered.

• At each new retrieval session, the search category is randomly selected. In total, 70 search sessions are made for each category.

• At each feedback loop, 8 agents are launched, with the goal of retrieving 2 images.

• 8 planes are used.

There are 10 categories in this setup, but as there are only four hosts, we assume that 8 planes are sufficient to match the distribution of the categories over the network. Hence, a plane might well be associated with two different categories having exactly the same distribution on the network.

Setup B

Setup B consists in only three hosts containing an image collection, plus the computer initiating the queries. Three categories, namely airplanes, maps and explosion-fire, are used as search categories and each is hosted on a specific computer. These categories do not share any image, hence no confusion about the location of the category can be made while retrieving a positive label. A fourth set contains 4000 images from the category entertainment, which has major visual variations in its content, and thus could be visually associated with any of the other categories. It is used as additive noise to the specialization of the categories to reflect the difficulties to find the relevant images in a collection containing varying topics. It is uniformly distributed among the three other hosts.

For this setup, parameters are the following :

• For each retrieval session, feedback loops are conducted until 100 labels were gathered.

• At each new retrieval session, the search category is randomly selected. In total, 70 search sessions are made for each category.

• At each feedback loop, 8 agents are launched, with the goal of retrieving 2 images.

• 6 planes are used.

As there are only three hosts, each one hosting a single searchable category, we assume 6 planes are sufficient to match the distribution of the categories.

Overall performances

In this test, we evaluate the overall performances of the system. For this purpose, we use the setup A. At the end of each session, we measure the recall on the images retrieved (number of relevant images retrieved over the number of available relevant images). Results are shown on figure 3, and compared to results obtained without using long-term learning, as described in [START_REF] Picard | Image retrieval over networks : Active learning using ant algorithm[END_REF].

We can see a significant improvement as high as 100% of the recall due to the better learning of the localizations of the categories. The complexity of the category (which can be evaluated by the absolute value of the recall) has no effect over the improvement of the long-term learning.

Markers evolution

In order to analyze the system better, we measure the evolution of the markers during the search sessions using setup B. We first compute the average probability over all search sessions of each plane to lead to one of the three destinations. Results are shown on figure 4. As one can see, the planes are specialized to one destination. For instance, the first plane has a higher probability to lead to host one, while the second plane has a higher probability to lead to host 3. As the values of these probabilities are clearly above 0.5, we consider the learning of the localization as successful.

We then observe the evolution over time of the probabilities of movement by plotting them at the end of each session. On figure 5, we introduce a visualization where each mark shows the probability of movement of the corresponding plane, projected on three axes given the following equation:

(x j , y j ) = ( 2 i=0 m i [j] • cos( i • 2π 3 ), 2 i=0 m i [j] • sin( i • 2π 3 )) (25)
With (x j , y j ) being the coordinate of the considered mark. As seen on figure 5, some planes are specialized during all sessions (for instance plane 1), while some migrate their specialization from one host to another (for instance, plane 3), explaining their lower average value on figure 4.

We then investigate the dynamics of the markers evolution. for that purpose, we plot the value of a marker on a particular host at an instant t + 1 against its value at time t. Such plots are shown on figure 6 for the three hosts.

We can see that the evolution are close to the diagonal, which means that changes are smooth. There are oscillations around a fixed point (for instance (0.8, 0.8) for the first plane on the first host), proving experimental stability of the association between planes and markers. Some planes (namely 3 and 5) take a longer time to reach a stable association, but end oscillating around a high probability value on one host.

Conclusion

In this article, we introduced an application of swarm intelligence to distributed content based image retrieval. The hereby presented system relies on mobile agents with ant-like behavior for optimizing their route through the network in search of relevant images. A relevance feedback loop is used to improve both the relevance function and the paths to relevant image collections. We tackle the problem of using previous search sessions to improve future sessions by adding several markers on the hosts, each one being associated with a category. This multiple markers strategy raises a three layered learning problem, namely:

1. Selecting the relevant set of markers regarding the searched category. 2. Optimizing the selected markers so as to match the distribution of relevant images. 3. Learning the relevance function.

As these problems are interdependent, the resulting system has complex dynamics. We introduced new learning rules dealing with this complexity. Theoretical results on the convergence of these rules have been derived for a simple case.

We also carried out experiments on custom networks hosting images taken from the TrecVid'05 dataset. The long-term learning strategy results in a high improvement over classical distributed CBIR. We investigated the evolution of the markers, and showed that the association of a plane with a category was correctly learned. Furthermore, we found these associations are stable and the transitions are smooth.

Perspectives on this work include testing on web-scale networks. The challenges of these large networks is on one hand the scaling of the reinforcement based learning algorithm (despite ACO has been shown to scale well). On the other hand, it is necessary to keep the system performing in real-time, which is needed for the relevance feedback scheme.

Figure 1 :

 1 Figure1: Functional description of our system showing the user in interaction with the relevance feedback loop (launching of agents, retrieval, display and labeling).

Figure 2 :

 2 Figure 2: Example of network with 6 hosts: the user's computer (a), 3 hosts with an image collection (b, e and f ) and two routing hosts (c and d). The system has P = 4 planes available. For instance, agents using the fourth plane (bold values) have more chance to be routed to host d and to retrieve images from host e.

Figure 3 :

 3 Figure 3: Recall obtained for the experiments of setup A. The long-term improves the recall for all categories by a significant margin.

Figure 4 :

 4 Figure4: Average of the probability of leading to each host for each plane in setup B. For instance, the plane 2 has a higher probability to lead to host 3.

Figure 5 :

 5 Figure 5: Distribution of the markers on the three hosts at the end of each session in setup B. Each plane has specialized towards a specific destination for the major part of the experiment.

  Evolution of the markers between each sessions for host 1. Marker of the first plane converges to (0.8, 0.8) and oscillates around this point, whereas other markers converge and oscillate around (0.1, 0.1). Evolution of the markers between each sessions for host 2. Markers of the planes 3, 4 and 5 converge slowly to (0.8, 0.8).

Figure 6 :

 6 Figure 6: Evolution of of markers of the six planes for the three hosts. For each of these hosts, one or more plane converges to (0.8, 0.8) and oscillate around this point.

see http://www-nlpir.nist.gov/projects/tv2005/tv2005.html

Arnaud Revel is a Graduate Engineer of the Ecole Nationale Supérieure de l'Electronique et de ses Applications (ENSEA) de Cergy-Pontoise (graduated in computer science) and received the Ph.D. degree from the University of Cergy-Pontoise, France, in 1997 and his Qualification to Research Direction in 2007 from the same University. He has currently a full professor position at the La Rochelle University. His research interests are to develop neural architectures and learning algorithms inspired by biology and psychology in order to control autonomous agents (either robots, software or in virtual reality). He is particularly interested in modeling and implementing interaction capacities in robotic and virtual agents in order to develop intuitive a human machine interface and provide new therapeutic tools for psychiatry. He has also been developing multi-agent systems for information retrieval for several years.


David Picard
email: picard@ensea.fr

Matthieu Cord
email: matthieu.cord@lip6.fr

Arnaud Revel
email: revel@ensea.fr

Image Retrieval over Networks : Active Learning using Ant Algorithm

In this article, we present a framework for distributed content based image retrieval with online learning based on ant-like mobile agents. Mobile agents crawl the network to find images matching a given example query. The images retrieved are shown to the user who labels them, following the classical relevant feedback scheme. The labels are used both to improve the similarity measure used for the retrieval and to learn paths leading to sites containing relevant images. The relevant paths are learned in an ethologically inspired way. We made experiments on the trecvid 2005 keyframe dataset showing that learning both the similarity function and the localization of the relevant images leads to a significant improvement. We also present an extension with the re-use of learned paths for later sessions leading to a further improvement.

I. INTRODUCTION.

.

As far as data mining in multimedia documents (image, audio, video, ...) is concerned, web search engines usually give poor results. Most of them use the contextual web page, or the meta information

attached to the multimedia objects. The text used for the indexing process is often far from the semantic meaning that the user usually attaches to the content of the document. Hence, the results of web search engines are far from expected regarding the semantics of the documents. Content Based Image Retrieval (CBIR) has been recently proposed in order to give an answer to this problem [START_REF] Veltkamp | Content-based image retrieval system: A survey[END_REF]. The main idea is to build a representation of the image based on its content, and then to find a relation between this representation and the semantic we associate to the image. Machine learning techniques have been successfully adapted to this framework. The best improvement was done with the introduction of relevance feedback [START_REF] Wood | Iterative refinement by relevance feedback in content-based digital image retrieval[END_REF], [START_REF] Huang | Image retrieval with relevance feedback: From heuristic weight adjustment to optimal learning methods[END_REF] into the process.

The processing cost introduced by these techniques makes them difficult to use with large amounts of images such as what we can find on the Internet. Moreover, classical CBIR tools are designed for a unique collection. In this paper, we adapt machine learning techniques such as active learning in order to deal with image retrieval distributed over a network. We propose to learn both the path leading to the collection containg the relevant images and the similarity between images. We introduce a scheme that efficiently implements this two-step learning combination by using an ant-like behavior algorithm. The resulting system will constitute a smart solution for distributed CBIR.

In the next section, bibliographical context is discussed, and our methodological and technological choices of mobile agents are motivated (Sect. III). Then, we detail the ant-like reinforcement learning algorithm used by the agents in section IV. The section V contains the description of our distributed interactive learning strategy. Finally, we present and discuss the experiments and results we obtained using our system on the trecvid2005 keyframe dataset 1 .

II. DISTRIBUTED CONTENT BASED RETRIEVAL

A. Content Based Image Retrieval

The main idea of content based image retrieval (CBIR) is to retrieve within large collections images matching a given query thanks to their visual content analysis. Visual features, such as color, texture or shape, are extracted from the images and indexed. These features can be global or extracted from regions or points of interest [START_REF] Carson | Blobworld: A system for region-based image indexing and retrieval[END_REF], [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] and then compiled into a index or signature. A basic way to perform retrieval consists in computing a similarity function for comparing the query index to one of the images in the collection [START_REF] Niblack | The QBIC project: Querying images by content, using color, texture, and shape[END_REF]. Such systems give unsatisfying results due to the well known semantic gap [START_REF] Santini | Emergent semantics through interaction in image databases[END_REF].

To fill the gap, the similarity function may be updated on-line, using an interaction with the user called "relevance feedback". In this process, some images are proposed to the user for labeling. These labels (usually relevant or irrelevant) are used to update the similarity function.

In this context, machine learning techniques such as Bayes classification [START_REF] Vasconcelos | Bayesian models for visual information retrieval[END_REF] or support vector machines [START_REF] Chapelle | Svms for histogram based image classification[END_REF] have been recently introduced to build the similarity function from a set of labeled samples. To boost this online learning, active learning strategies have been proposed: the goal is to select the examples to be labeled that will enhance the most the similarity function [START_REF] Tong | Support vector machine active learning with applications to text classification[END_REF]. At the end of the interactive session, a ranking of all images given their similarity is shown to the user. Most of these techniques come from the text categorization community [START_REF] Sebastiani | Machine learning in automated text categorization[END_REF] and were adapted to image classification.

There are lots of CBIR systems, and an overview can be found in [START_REF] Smeulders | Content-based image retrieval at the end of the early years[END_REF].

B. CBIR in distributed collections

The major part of the CBIR computation is dedicated to the processing of all the feature vectors in order to produce the final ranking. Then, the fact that images are distributed over many sources should be more an advantage than a drawback since the processing of every image could be naturally paralleled. To our knowledge, there are only few researches on distributed image retrieval (despite being noted as further improvement to CBIR in [START_REF] Smeulders | Content-based image retrieval at the end of the early years[END_REF]). In a context such as the Internet, the common idea is to keep up-to-date an index of the feature vectors. The indexes are stored on a few well identified machines hosting a CBIR search tool. These servers are entry points for the distributed CBIR system. The distributed CBIR system propagates the queries to the entry points and efficiently merges their results (see [START_REF] Berretti | Merging results for distributed content based image retrieval[END_REF]). In peer-to-peer networks, it is not possible to identify entry points anymore. Instead, each peer must index its own images and queries must be propagated from one peer to another. In DISCOVIR [START_REF] King | Distributed content-based visual information retrieval system on peer-to-peer networks[END_REF], King proposes an algorithm for selecting links between peers based on the content of their shared images. The queries are more likely to be propagated to peers which are known to host similar images. With this method, they achieve to improve the retrieval and reduce the network load.

In the systems presented above, interaction and active learning are not taken into account. Thus, the question about efficiently performing active learning in a distributed context is still open.

C. Mobile agents

Among the strategies allowing to perform the needed parallelization of feature vector processing, we have chosen to use mobile agents. A mobile agent is an autonomous computer software with the ability to migrate from one computer to another and to continue its execution there. While mobile agents have motivated many researches in the late 90's, it seems that they did not made their way in the information [START_REF] Park | On-line learning by active sampling using orthogonal decision support vectors[END_REF] DRAFT retrieval community. However, they have shown good performances in the case of information retrieval with mobile devices where the network capabilities are unreliable in nature [START_REF] Jiao | Performance analysis of mobile agents in mobile distributed information retrieval system -a quantitative case study[END_REF]. There are good reasons for using mobile agents in the distributed CBIR context, such as the reduction of the network load (the processing code of the agent being very small in comparison to the feature vector indexes) and the massive parallelization of the computation. Some of these advantages are described in [START_REF] Lange | Seven good reasons for mobile agents[END_REF].

The resulting scenario of CBIR using mobile agents is to launch several mobile agents with a copy of the query. They crawl the network in search of image collections. When an agent gets to a site, a dialog with a local agent is established. The local agent indexes the images and performs the processing [START_REF] Roth | A distributed content-based search engine based on mobile code[END_REF].

D. Ant-like agents

In addition to the computational interest of mobile agents, we suggest that they can also participate to the learning process. Software agents following ant-like behaviors have been used, for instance, in several domains including network routing, traveling salesman problem or quadratic assignment problem [START_REF] Bonabeau | The social insect paradigm for optimization and control[END_REF] following the model of the ethologist J. L. Deneubourg [START_REF] Deneubourg | The dynamics of collective sorting: Robot-like ants and ant-like robots[END_REF]. In the case of distributed retrieval, ant-agents crawl the network to find the relevant documents. They move from one peer to another and mark the visited hosts (by changing a numerical value locally stored on these hosts, called marker). These markers can be viewed as a collective memory of paths leading to the relevant sites. This behavior-based mapping of the network is well adapted to inconsistent networks such as peer-to-peer networks, since the marked paths evolve with the global trend of the agent movements [START_REF] Revel | Web-agents inspired by ethology: a population of "ant"-like agents to help finding user-oriented information[END_REF], [START_REF]From robots to web-agents: Building cognitive software agents for web-information retrieval by taking inspiration from experience in robotics[END_REF]. In our distributed CBIR context, we have to do several travels between the user's computer and the information sources. Ant-algorithm seems to be a good solution for learning the relevant paths through the dynamics of active learning.

III. ARCHITECTURE OF OUR SYSTEM

Fig. 1 describes our system. The user starts his query by giving an example or a set of examples to an interface [START_REF] Cho | Impact of search engines on page popularity[END_REF]. We build a similarity function based on these examples [START_REF] Veltkamp | Content-based image retrieval system: A survey[END_REF]. Mobile agents are then launched with a copy of this similarity function [START_REF] Wood | Iterative refinement by relevance feedback in content-based digital image retrieval[END_REF]. Every host of the network contains an agent platform in order to be able to receive and execute incoming mobile agents. These agents travel through the network according to movement rules described in the next section (4). These rules allow our system to learn the paths leading to relevant images. images will have a high level of marker, whereas hosts with no relevant images will have a low level of markers (as described in section IV). The local selection stage is done by an active learning strategy adapted to the mobile agents context and based on uncertainty sampling, as described in section V. A scenario of this distributed active learning process is shown on Fig. 2.

As soon as they receive the answer of the index agent, the mobile agents return to the user's computer [START_REF] Carson | Blobworld: A system for region-based image indexing and retrieval[END_REF] and the results are displayed on the interface [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF]. The user can label these results (1: relevant, -1:

irrelevant), and the similarity function is updated consequently (7a) as well as the good paths of the network (7b). As the similarity function we use is based on SVM analysis [START_REF] Cortes | Support-vector networks[END_REF], the update only consists in adding the results and their labels to the training set and to train a new SVM. Mobile agents are then relaunched with the improved similarity function. The interactive loop consists in several launching of mobile agents and labeling of the results [START_REF] Santini | Emergent semantics through interaction in image databases[END_REF]. At the end of the interaction, mobile agents are launched for a very last time in order to retrieve the best results from each host [START_REF] Vasconcelos | Bayesian models for visual information retrieval[END_REF]. The number of retrieved images is proportional to the level of the markers leading to this host. In combination with the ant-algorithm, this assures that most of the best retrieved images are provided by relevant hosts.

IV. ANT-LIKE ALGORITHM

Agents move following an ant-inspired algorithm as described in [START_REF] Dorigo | The ant system: Optimization by a colony of cooperating agents[END_REF], [START_REF] Bonabeau | Inspiration for optimization from social insect behaviour[END_REF]. We improved the classical reinforcement rules by adding a semantic-oriented reinforcement taking into account the interaction with the user.

A. Algorithm description

Let c be the host currently executing the agent and S the set of possible destinations from c. Each host i of S contains a marker ph i which is used by the agent to determine the next move. Just like ants with pheromones, the higher the level of marker ph i the higher the probability P i to move to the host i:

P i = ph i k∈S ph k (1)
While homing with retrieved images, agents increase the level of the marker on the visited hosts, given the following rule:

∆ph i ∆t = +β • a(t) (2)
December 20, 2007 DRAFT with a(t) (agent reinforcement) being 1 when the agent has found a collection and 0 else, and t increasing if and only if the marker of the concerned host is changed. Therefore, t is a time only related to the concerned host. The system reinforces paths leading to informative hosts, since this increase of markers will also increase the probability of these hosts to be visited later.

While searching for images, agents decrease the level of the marker of the destination, with the following rule:

∆ph i ∆t = -α • ph i (t) (3)
This allows to forget the non informative paths. Compared to real ants, this rule models the evaporation of pheromones.

B. Our implementation

As a marker is only updated when an agent moves towards the host holding it, an increase of time t represents a travel of an agent along a specific path. Thus, the time t is local to a host of the network, depending on how many agents are moving through it. If no agent moves along a path, the local time is frozen and markers do not evolve anymore. On the contrary, if a lot of agents move along another path, the related time flies very fast and markers are updated very quickly. One of the main consequence is that there is no correlation between the dynamics of the times of two hosts that are not bound to each other. The system does not forget a path just because no agent travels through it. One main advantage of a local time is that the system does not need to synchronize all the hosts of the network with an universal clock. Each host has its internal clock based on the frequency of agent visits.

Each time the user labels an image, the levels of markers on the path taken to retrieve this image are also increased as follows:

∆ph i ∆t = +γ • u(t) (4)
Where u(t) is the reinforcement signal given by the user (user reinforcement): 1 if the label is positive, 0 otherwise. Thanks to this rule, the paths leading to hosts containing images the user is looking for are reinforced. The global equation may be written as follows:

∆ph i ∆t = -α • ph i (t) + β • a(t) + γ • u(t) (5)
When the variations of ph i tend to zero, the estimation ph i of the marker's level is:

December 20, 2007 DRAFT ph i = β • â + γ • û α (6)
With â and û being the estimation of a and u respectively. In that case, the level of markers tends to zero if the host does not lead to a collection, and is not null on the contrary. The highest level is obtained for a host with high values of û (which implies â = 1), that is on a path leading to a collection containing a lot of relevant images.

C. Re-use of marker -long term learning

We have also implemented a very simple way to keep in memory the previously learned collection selection. In this case, we do not reset the markers at the beginning of each new search session. The markers evolve from a query to another leading to a reinforcement of the collections which gave the greatest number of positive images over all the sessions. If a collection contains too few positive images and is exhausted before the end of the current session, its markers will be very small for the next search.

Thus, only collections with large sets of positive images will be reinforced with this strategy. However, these small veins of positives images are not lost: they may be rediscovered by an agent at any time, due to the stochastic behavior of our system.

V. DISTRIBUTED ACTIVE LEARNING

A. Local images selection

Each time an agent gets to a site containing a collection, it has to choose some examples to add to the training set. Given a set of images {x k } and their corresponding labels {y k }, let us denote a training function τ giving the label y to the image x. The aim of active learning is to choose the unlabeled image

x that will enhance the most the relevance function when added to the previous set {x k }. The label τ (x)

is correspondingly added to the previous labeling set {y k }. We use uncertainty-based sampling, which is the most used active strategy in image retrieval [START_REF] Tong | Support vector machine active learning for image retrieval[END_REF]. This strategy aims at selecting an unlabeled image that the training function τ is most uncertain about. The first solution is to compute a probabilistic output for each image, and select the unlabeled images with the probabilities of being relevant closest to 0.5 [START_REF] Lewis | Heterogenous uncertainty sampling for supervised learning[END_REF]. Similar strategies have been also proposed with SVM classifier [START_REF] Park | On-line learning by active sampling using orthogonal decision support vectors[END_REF], where the similarity function is the distance to the hyperplane, and the most uncertain documents have an output close to 0.

As many agents reach the same host with the same relevance function, the active strategy should not answer in a deterministic way, otherwise all these mobile agents will get the same answers, and thus act December 20, 2007 DRAFT as one single agent. We recently proposed an active learning scheme [START_REF] Cord | Stochastic exploration and active learning for image retrieval[END_REF] to boost the retrieval in one single collection. We propose here to extend our active learning framework in order to handle datamining over a network. We rank images given their distance to the boundary. We divide the selection of I images into I selections of a single image. Each of these selections are done over a set of images with ranking between 1 and n using an uniform distribution. The selected image is then removed from the set. To fix the width of the set to n for the i-est selection, we add the image ranked n + i -1 to the selection pool.

Let us denote p = 1 n the probability of an image x in the set at round i of being selected, and q = 1p. P i (x) the probability for the image x with rank r x to be exactly selected at round i follows a specific geometric distribution depending on the round where it happened:

P i (x) =                    p i-1 j=1 q , 1 ≤ r x ≤ n p i-rx+n-1 j=1 q , n + 1 < r x < n + i 0 , n + i ≤ r x (7)
P i (x) =          pq (i-1) , 1 ≤ r x ≤ n pq (i-rx+n-1) , n + 1 < r x < n + i 0 , n + i ≤ r x (8)
The probability of an image being selected after I rounds is the sum of the probabilities of being selected at each round from the round where it has entered the set:

P (x) =                  I i=1 pq (i-1) , 1 ≤ r x ≤ n I i=rx-n+1 pq (i-rx+n-1) , n < r x < n + I 0 , n + I ≤ r x (9)
Which can be rewritten using the geometric series of parameter q as :

P (x) =          1 -q I , 1 ≤ r x ≤ n 1 -q (I-rx+n) , n < r x < n + I 0 , n + I ≤ r x (10)
The probability P follows an uniform distribution for images with ranking between 1 and n. For images with ranking between n and n + I, it decreases exponentially with parameter q = 1 -

B. Collection selection

In our context, the relevant category is very little in front of the available data. Thus, a relevant image might often be considered as more informative than an irrelevant one. We consider a good collection selection strategy the one that selects the collections containing mainly relevant images. Our collections selection strategy is performed by the ant algorithm. At the very beginning, all collections have an equal chance of being visited by an agent (all markers are set to 1). After a few rounds, thanks to the user's reinforcement u(t) (Cf. Section IV), the highest probability of selecting images will be obtained for the collection that returned the largest set of positively labeled images.

In case of a collection with only few positive images, this strategy will at first reinforce the selection on this collection. But as soon as the vein is exhausted, no more positive labels will reinforce the marker, and the probability will decrease quickly. This shows how the strategy adapts through the dynamics of active learning.

VI. EXPERIMENTS.

A. Experiment setup

While we have only made simulations of the network on the COREL dataset in [START_REF] Picard | Cbir in distributed databases using a multi-agent system[END_REF], we did a real implementation of our system for the experiments presented hereby. To test our system in quasi "realistic" conditions, we performed the experiments on the intranet of our lab. In a previous work it has been tested that, given the path reinforcement strategy, no matter the complexity of the network is, it is reduced, after learning, to a simple connexion graph with only informative paths remaining (in accordance with [START_REF] Dorigo | The ant system: Optimization by a colony of cooperating agents[END_REF]).

Indeed, as our algorithm reinforces the shortest path to the information sites, it can then be considered only a small number of directions (some of which leading to relevant images), no matter how many December 20, 2007 DRAFT computers are in these directions. We made our experiments with four directions, each one consisting of a single computer. For the data, we used the set of keyframes of the trecvid ′ 05 competition for a total of about 75000 images. We used as ground truth the high level features given by CMU. We divided these images into four collections, each hosted by a bi-opteron 275 with 8 GB of RAM. These hosts were the possible destinations for our mobile agents. The links between the hosts of the network were 100Mbps, and therefore the time taken by the agents to migrate was negligible.

For the agent framework, the Jade2 platform was used. As Jade had little support for agent mobility between several platforms, we implemented our own mobility service using Java serialization and ACL messaging. As the agent code was common to all platforms, the serialization of an agent resulted in a string containing only its internal fields. The size of the messages containing a serialized agent was about 10kB. The size of the similarity function depended on the number of examples in the training set, and varied from less than 1kB to 30kB. This made the serialized agents as light as a typical web page with few images, such as the page containing the results of a google search.

B. Network learning

The main assumption for learning paths to relevant images together with the relevance function is that the images belonging to the concept are well localized on the network. In other words, there are hosts that contain a lot of relevant images and hosts that do not contain any or few relevant images. To simulate this, we hosted in a first case all the relevant images on the first destination, while the other computers did not contain any relevant image. We called this setup strong localization. In a second case, we put only 80% of the relevant images on the first host, the remaining being equally distributed on the other hosts, in order to simulate what we called a weak localized setup. In order to deal with a realistic retrieval where the relevant images are hidden in a mass of irrelevant images, we added to each host about 15000 irrelevant images randomly selected. 100 search sessions were made for each category, and for each new query, the markers were reset. Due to the ant-algorithm, we expected at the end of the retrieval session the levels of marker being high on the first host compared to the other ones. Fig. 3 shows the level of markers for each host for the case where relevant image are localized at 100% on the first destination.

As we can see, we were able to learn the good path, with relative success from a category to another.

Actually, as the learning process depends on the user's reinforcement û, it is directly linked with the number of relevant images found during the interaction, which is very dependent on the category.

For the weak localization, Fig. 4 shows that learning the relevant path is also a success even if there are some non-zero value of û for the other hosts. Nevertheless, this is less pronounced than for the strong localization setup.

C. Similarity learning

In order to evaluate the influence of path learning on category learning, we also ran experiments of our active learning strategy as described in section V-A on a single bi-opteron 275 containing the whole image collection. Due to the lack of parallelization, this setup took a much longer time than our mobile-agents system. This setup will be referred as centralized setup in the following. Fig. 5 shows the recall@500 (number of relevant images retrieved for 500 total images retrieved) per setup for each category. In order to compute the recall, the number of the best images retrieved from each host were proportional to the level of marker. For instance, if the levels were {0.80, 0.10, 0.05, 0.05}, we retrieved {400, 50, 25, 25}

images from each host respectively. In the case of the centralized setup, the recall was made among the 500 best images of the whole collection.

We can see that the distributed system outperforms the centralized one in all cases, but especially for difficult categories (low recall values, for instance 'road' or 'urban'). The standard deviations for these varied from 1% for difficult categories (less than 10% in recall) to about 5% for easy categories (more than 20%).

D. Re-use of markers

As explained in Section IV-C, We ran the same experiments without resetting the markers level at the beginning of a search. For each category, the initialization of the markers was made only once for the first query. Fig. 6 shows the levels (mean over the sessions) of markers for each category. The levels of paths leading to the irrelevant hosts are negligible, which means that almost all agents move towards the first host (but not all due to the algorithm non-determinism).

The recall@500 of the Fig. 7 shows that this setup is a further improvement. For easy categories (for instance 'charts' or 'maps'), the gain is up to about 100%. For difficult categories ('road'), the gain can be as high as about 1000%. As this strategy focuses even more on adding relevant images to the training set (by keeping in memory their localization over many sessions), this can explain the boost obtained with difficult queries. This is shown on Fig. 8, where the number of positive labels per session per category is clearly higher than for the other setups, even if the standard deviation is high (about 10 labels). December 20, 2007 DRAFT These experiments validated our path learning algorithm by showing that the path leading to the relevant host has the highest level of marker. We then presented results showing that taking in account the localization of the relevant images in the learning process leads to an improvement of 75% in mean.

Moreover, in a setup where the markers were not initialized at the beginning of each new search but kept for the next session, our system had an improvement of about 155% in mean.

VII. CONCLUSION.

In this article, we presented a new active learning strategy for searching images over networks. We introduced a new reinforcement based learning scheme for learning the localization of relevant images.

We carried out a smart cooperation between these two strategies in a global architecture based on mobile agents with an ant-like behavior. We made a working implementation of our system and tested it on a real network using the trecvid keyframe dataset. It shows that our system is definitively an improvement to distributed CBIR.

We are now working on an extension of our system for managing different markers, each one related to a specific concept. Concurrent queries of different concepts will involve different markers. With an efficient management of many concept-dependant markers, we believe the improvement shown in the re-use of markers setup can be widely used.

Fig. 1 .

 1 Fig.1. Functional description of our system showing the user in interaction with the relevance feedback loop (launching of agents, retrieval, display and labeling).

  1 n . It is null otherwise. This selection strategy combines the uncertainty based sampling with a diversity introduced December 20, 2007 DRAFT by the distribution P . It is also very fast to compute (one ranking of all images plus I random sampling following a uniform distribution) using the following algorithm: 1) Rank all images given their distance to the hyperplane 2) Add the n first to an empty pool 3) for i from 1 to I do Randomly select an image from the pool using uniform distribution Remove it from the pool Add the image n + i to the pool 4) done

Fig. 2 .Fig. 3 .Fig. 4 .Fig. 5 .Fig. 6 .Fig. 7 .Fig. 8 .

 2345678 Fig. 2. Example of distributed active learning with two collections A (bright green color) and B (dark red color). A contains many relevant objects, whereas B has very few. Plain symbols denote labeled images, whereas hollow symbols denote unlabeled images. The initial query contains two relevant images (circles) and two irrelevant images (triangles) equally chosen from A and B. The collection selection algorithm will choose A since the active learning returns more positive labels on A.

see http://www-nlpir.nist.gov/projects/tv2005/ December

20, 2007 DRAFT

http://jade.tilab.com December 20, 2007 DRAFT


David Picard

Nicolas Thome

Matthieu Cord

AN EFFICIENT SYSTEM FOR COMBINING COMPLEMENTARY KERNELS IN COMPLEX VISUAL CATEGORIZATION TASKS

Recently, increasing interest has been brought to improve image categorization performances by combining multiple descriptors. However, very few approaches have been proposed for combining features based on complementary aspects, and evaluating the performances in realistic databases. In this paper, we tackle the problem of combining different feature types (edge and color), and evaluate the performance gain in the very challenging VOC 2009 benchmark. Our contribution is three-fold. First, we propose new local color descriptors, unifying edge and color feature extraction into the "Bag Of Word" model. Second, we improve the Spatial Pyramid Matching (SPM) scheme for better incorporating spatial information into the similarity measurement. Last but not least, we propose a new combination strategy based on ℓ1 Multiple Kernel Learning (MKL) that simultaneously learns individual kernel parameters and the kernel combination. Experiments prove the relevance of the proposed approach, which outperforms baseline combination methods while being computationally effective.

INTRODUCTION

Image categorization consists in predicting, in a given image, the presence/absence of an example of a pre-defined class. Combining descriptors for improving categorization performances has extensively been studied in the last decade. Multiple Kernel Learning (MKL) is appealing for that purpose, since it offers the possibility to jointly learn the weighting of the different channels and the classification function. Some recent MKL studies [START_REF] Vedaldi | Multiple kernels for object detection[END_REF][START_REF] Yan | A comparison of l1 norm and l2 norm multiple kernel svms in image and video classification[END_REF] provide evaluations in complex datasets such as VOC challenge [START_REF] Everingham | The PASCAL Visual Object Classes Challenge 2009[END_REF]. However, they use redundant descriptors (various SIFT or HoG variants), that only capture a single image modality (edge). Other approaches [START_REF] Gehler | On feature combination for multiclass object classification[END_REF] use complementary features, but do not provide evaluations on such challenging databases.

In this paper, we consider the problem of learning combinations of complementary descriptors to make the categorization task more efficient. The proposed approach is schemed in figure 1. There are three main areas of novelty: extracting complementary informative descriptors (section 2.1), building an image representation from each feature (section 2.2), and learning a category-specific combination between them so that improving categorization performances (section 2.3).

PROPOSED METHOD

Unified extraction of local descriptors

In this paper, we propose to represent each image modality by a "Bag Of Word" model [START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF]. Regarding image categorization, this representation proves to reach state of the art performances when dealing with complex images , and significantly outperforms global image signatures. In this paper, we propose to apply the "Bag Of Word" model for all extracted descriptors. We focus here on edge and color features, but the method naturally extends to other descriptors (e.g. texture).

We choose to extract the different descriptors on a regular grid over the image (dense sampling point strategy). Around each patch with its associated scale, a set of descriptors is computed over a local neighborhood. An offline clustering strategy (k-means) is performed to compute a visual codebook. In this paper, we use K = 4000 visual words for all descriptors. Each image modality is thus represented by a histogram of visual words, with incorporated spatial information (section 2.2). The most successful strategy for computing the histograms is a "semi-soft assignment" that assigns for each descriptor a vote of 1 to its N = 10 closest visual words [START_REF] Van Gemert | Visual word ambiguity[END_REF].

Edge descriptors

We used opponentcolorSIFTs (oc-SIFTs) [START_REF] Van De Sande | Evaluating color descriptors for object and scene recognition[END_REF] as local edge descriptors, a variant the well known SIFT descriptors [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF]. oc-SIFT histogram is a concatenation of three 1-D SIFT histograms based on the channels of the opponent color space O1, O2, O3:

0 @ O1 O2 O3 1 A = 0 @ R-G √ 2 R+G-2B √ 6 R+G+B 3 1 A (1)
where R, G, B refers to the standard color space. oc-SIFT leads thus to a descriptor of dimension 128 × 3 = 384. Due to the SIFT normalization, oc-SIFTs are invariant to changes in light intensity (see [START_REF] Van De Sande | Evaluating color descriptors for object and scene recognition[END_REF]).

Color descriptors

We choose the Hue Saturation Value (HSV) space for extracting a local color descriptor, since HSV is known to be perceptually appropriate. Thus, at each grid position with its associated scale, we compute a color histogram over the region using a quantization of the HSV space. We quantify H with 8 bins, S with 6 bins, and V with 3 bins. This leads to a descriptor of dimension 8×6×3 = 144. Note that some recent works [START_REF] Van De Sande | Evaluating color descriptors for object and scene recognition[END_REF] propose to extract local color descriptors and to build visual dictionaries from them. However, all proposed color descriptors (e.g. RGB histograms) consider the different color axes independently by concatenating 1-d histograms. We claim that our representation, a 3d histogram, is a more powerful description of each patch by its capacity to encode correlations between axes.

Channel kernel similarity: adapted SPM scheme

In order to take into account the spatial information for each extracted image descriptor, we propose to adapt the "Spatial Pyramidal Matching" (SPM) introduced in [START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF]. The SPM works as follows: at a specific scale l, the image is divided following a regular grid, and a histogram of visual words is computed on each resulting region. In the last PASCAL VOC Challenge [START_REF] Everingham | The PASCAL Visual Object Classes Challenge 2009[END_REF], the most common scheme of partitioning the image used three decomposition scales: a histogram over the entire image (scale 0), a 2 × 2 grid resulting in 4 histograms (scale 1), and a 3 × 1 grid resulting in 3 horizontal band histograms (scale 2). We propose here a decomposition strategy with two scales, keeping the global histogram at scale 0. At scale 1, however, we use a decomposition of 3×3 overlapping windows. Each window corresponds to a quarter of the image, with an overlap of half the window size. For each of the 10 regions r previously defined and for each descriptor channel c, we defined the similarity kc,r(xi, xj) between two images xi and xj as the following Gaussian kernel:

kc,r(xi, xj) = e -γc d χ 2 " x (c,r) i ; x (c,r) j " (2)
Where x (c,r) denotes the histogram of visual words for x associated with descriptor c and region r, and d χ 2 (•, •) is the χ 2 distance. The similarity Kc(xi, xj), for channel c, between images xi and xj is thus defined as a weighted linear combination of local similarities kc,r(xi, xj), as in [START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF]:

Kc(xi, xj) = 10 X r=1 wr kc,r(xi, xj) (3)
where wr weights are set proportional to the size of the considered regions.

Combining the kernels

Different strategies can be carried out to perform the combination of different features types.

Baseline early fusion -product kernel

The simplest way of combining Nc channels is to merge the corresponding signatures into a single vector by concatenating the associated feature spaces. This approach is called early fusion. In our SPM context, the early fusion is to be done for each histogram of the pyramid. The resulting major kernel is the following:

K prod (xi, xj) = 10 X r=1 wre - Nc P c=1 γc d χ 2 " x (c,r) i ; x (c,r) j " (4)
K prod (xi, xj) can be further decomposed as follows:

K prod (x i , x j ) = P r wr Q c e -γc d χ 2 " x (c,r) i ; x (c,r) j " = P r wr Q c kc,r(x i , x j ).
Hence, an early fusion scheme with Gaussian kernels is equivalent to a product of kernels in each pyramid region.

Baseline intermediate fusion -weighted sum kernel

An other way of combining the Nc different channel specific kernels is to compute a weighted sum over them:

Ksum(xi, xj) = Nc X c=1 βcKc(xi, xj) = Nc X c=1 βc 10 X r=1 wrkc,r(xi, xj) (5) If βc = 1
Nc ∀c, Ksum is a simple averaging kernel Kavg. Otherwise, βc can be further optimized using a cross-validation procedure. However, this brute-force strategy rapidly becomes intractable when Nc increases.

Using the explicit inner product of induced space, we have

kc,r(x i , x j ) =< φ(x (c,r) i ), φc(x (c,r) j ) >. Therefore, Ksum(x i , x j ) = P r wr P c βc < φc(x (c,r) i ), φc(x (c,r) j
) >. The weighted sum combination can thus be interpreted as an intermediate fusion of channels, by the concatenation of the signatures in the induced space.

Learning a non-sparse combination via ℓ1 MKL

The problem of learning a linear combination of different kernels has recently been formalized as Multiple Kernel Learning [START_REF] Francis | Multiple kernel learning, conic duality, and the smo algorithm[END_REF]. In this case, the combination weights β and the support vector weights α are learned together in a joint optimization. The goal is to find the optimal classification function f defined as follows:

f (x) = X i αiyi X m βmkm(x, xi) -b (6)
Recent works attempting at using MKL on image dataset for combining different channels [START_REF] Vedaldi | Multiple kernels for object detection[END_REF][START_REF] Gehler | On feature combination for multiclass object classification[END_REF] use MKL optimization algorithms based on ℓ1 norm to regularize the kernel weights, like Sim-pleMKL [START_REF] Rakotomamonjy | SimpleMKL[END_REF]. Since this leads to sparse solutions, most studies report that MKL is often outperformed by simple baseline methods (product or averaging) when dealing with complementary and informative kernels [START_REF] Vedaldi | Multiple kernels for object detection[END_REF][START_REF] Gehler | On feature combination for multiclass object classification[END_REF]. In our case, we do not want to select either the SIFT or the color channel, but we aim at finding a proper weighting between them. Except [START_REF] Yan | A comparison of l1 norm and l2 norm multiple kernel svms in image and video classification[END_REF], very few approaches use ℓ2 MKL optimization schemes to find a non-sparse combination of complementary descriptors.

In this paper, we propose a hybrid strategy that does not lead to ignore informative image modalities during training. Importantly, our algorithm learns individual kernel parameters (γ in the Gaussian case) and the kernel combination coefficients (βm) simultaneously. Other approaches like baseline methods (section 2.3.1) or ℓ2 MKL use a two-step procedure: optimal γ is first determined by crossvalidation, and combining the kernels is then performed for a fixed γ. This leads to a sub-optimal parameter estimation with respect to our global optimization scheme. As we verify experimentally (section 3), the proposed algorithm leads to an accurate parameter estimation while being computationally efficient. Thus, for each channel c, we form a set of M kernels Kc,γ, and use a ℓ1 MKL strategy to select the relevant γ parameter. The sparse solution output by ℓ1 MKL algorithms is therefore used as an option to cross-validation. (see [START_REF] Rakotomamonjy | SimpleMKL[END_REF]). Our adapted MKL problem formulation leads to find the optimal function of the form:

f (x) = Ne X i=1 αiyi Nc X c=1 γ M X γ=γ 1 βc,γkc,γ(x, xi) -b (7)
where the joint optimization is performed on αi (Ne parameters) and βc,γ (Nc × M parameters).

EXPERIMENTS AND RESULTS

We evaluate the proposed approach on the PASCAL VOC2009 challenge. This dataset is now accepted as being the most publicly available difficult benchmark for object image classification, due to multiple object viewpoints, large scale range, complex background, etc.

Setup

We used the train subset for training the classifier (about 3500 images) and the val subset for testing (about 3500 images). We evaluate the categorization performances for the individual edge and color descriptors, and different combination methods: baseline methods, (averaging & product), weighted sum kernel, and our adapted MKL approach. Not that except for MKL, the γ parameters for the individual kernels are optimized individually on the val subset. Table 1 presents the Average Precision (AP) for different combination strategies, and for the 15 VOC categories where adding color increases performances (for the 5 remaining categories, performances are similar to the use of the SIFT descriptor alone).

Evaluation of descriptors and baseline combinations

Regarding individual descriptor performances, the approach only using oc-SIFT is the run we submitted for the VOC2009 Challenge, ranked 6 among 20 engaged groups. Thus, oc-SIFT alone not surprisingly performs far better than the color descriptor (MAP of 47.8% vs 29.5%, column 1 and 2 of table 1). Indeed, in such object image database, edge is a much more powerful feature than color. However, we want to stress that a random classifier would achieve a MAP around 7%: our proposed color descriptor contains thus a significant amount of information for the categorization task.

Contrarily to recent works [START_REF] Vedaldi | Multiple kernels for object detection[END_REF][START_REF] Gehler | On feature combination for multiclass object classification[END_REF], we notice that combining edge and color using baseline methods gives very disappointing results: MAP of 45.8% & 47.5% for product & averaging, respectively (column 3 and 4 of table 1). These combination strategies yield thus performances worse than using only oc-SIFT. In [START_REF] Vedaldi | Multiple kernels for object detection[END_REF], redundant edge descriptors are used whereas complementary features are merged in [START_REF] Gehler | On feature combination for multiclass object classification[END_REF]

Evaluation of learning-based combination strategies

The performances of the weighted sum kernel (equation 5) depend on the weights βi between color and edge kernels. Column 5 of table 1 presents results of the best weighting, learned by crossvalidation, that we denote BS ("Best Sum"). BS almost always performed better than the best performing kernel (oc-SIFT): the mean gain is about 2.3% (MAP from 47.8% to 50.1%). This confirms the soundness of combining edge and colors descriptors using a weighted sum kernel. Indeed, although color descriptor performance is limited, this proves that a category-specific weighting with the edge descriptor can significantly improve performances. On the category potted-plant, the gain reaches more than 8% of MAP, which corresponds to more than 30% improvement. Let alone for the categories bicycle, boat, bottle, cat, dinning-table, motorbike, potted-plant and sofa, the mean gain is about 4% of MAP.

The main drawback of the weighted sum kernel is its computational cost. Indeed, it requires to first determine γ for each channel, and then the weights β of the combination. This brute-force strategy is feasible for few channel kernels (here Nc = 2), but rapidly becomes intractable when Nc increases. Our adapted MKL approach (section 2.3.3) offers an elegant alternative to this problem by jointly learning γ and β. We use 5 kernels with variable γ for each channel, leading to a 10 kernel weighted sum. The learning is performed using the SimpleMKL algorithm [START_REF] Rakotomamonjy | SimpleMKL[END_REF], and is very fast: in our experiments, the gradient based optimization always converges very quickly, and learning for a category can be performed in a few minutes. Categorization performances using MKL are shown in the last column of table 1. As we can see, MKL gives results similar to BS kernel, leading to a MAP of 49.8%. Therefore, Contrarily to [START_REF] Vedaldi | Multiple kernels for object detection[END_REF][START_REF] Gehler | On feature combination for multiclass object classification[END_REF], we notice that MKL significantly outperforms baseline methods (product and averaging). This is because the ℓ1 algorithm (o) tv-monitor Fig. 2. Analysis of the weighting regarding performances of the weighted sum kernel. Each curve represent Average Precision for each category, versus the weight β col of the color kernel. β col = 0 corresponds to using oc-SIFT only, whereas β col = 1 corresponds to using color only. The mark denotes AP for the proposed MKL approach, with respect to the sum of weights corresponding to the color kernels.

directly used in [START_REF] Vedaldi | Multiple kernels for object detection[END_REF][START_REF] Gehler | On feature combination for multiclass object classification[END_REF] with complementary kernels leads to a spare solution that discard informative channels from the combination. At the opposite, our approach keeps all informative image modalities for performing the combination.

Figure 2 shows the influence of the weights for the sum combination. Let us denote β col the weight of the color kernel, and (1-β col ) the weight of the SIFT kernel. The MAP is shown against β col , normalized to the value obtained for β col = 0, for each category. As we can see, the optimal combination is dependent on the category, but always resides in low β col values, except for potted-plant, for which the color descriptors were almost as good as the SIFT descriptors. We also draw a mark corresponding to the MAP of the MKL method against the weights obtained by the color kernels after the optimization. We can notice that MKL selects a β col parameters close to the optimal value determined by BS. Note that regarding β learning, BS represents an "ideal" kernel since the parameters are determined by maximizing AP on the val subset. In that sense, the performances for BS (and identically for other individual descriptor kernels and baseline combination methods regarding γ) are over-estimated with respect to MKL. Therefore, the fact that MKL reaches performances close to BS illustrates the effectiveness of the conjoint learning of β and γ parameters, that is better-founded than the two-step optimization used with the other approaches. For four categories (see table 1), MKL outperforms BS, proving the efficiency of the joint learning.

CONCLUSION

In this paper, we propose an efficient strategy for combining complementary features using the kernel framework. The kernel combination is based on an adaptation of a ℓ1 MKL algorithm that do not lead to ignore any informative image modality during learning. We evaluate the proposed learning-based approach on the challenging VOC'09 dataset, and show that it significantly outperforms baseline combination methods. Moreover, our algorithm is computationally effective, and provides a promising alternative to cross-validation by its capacity to simultaneously learn individual kernel parameters and the kernel combination.

Fig. 1 .

 1 Fig. 1. Approach Overview.

Table 1 .

 1 . However, in both cases, the different descriptors have comparable categorization abilities. Therefore, baseline methods seem inappropriate for combining complementary descriptors with significant variations regarding categorization performances. VOC 2009: (M)AP for different combination strategies.

	category	SIFT Color	Prod Avg	BS	MKL
	bicycle	46.9	25.5	44.7 48.6	50.2	50.2
	boat	61.4	39.9	59.7 61.3	64.4	62.9
	bottle	17.6	13.7	19.7 18.7	19.7	20.0
	bus	71.4	34.3	65.5 67.5	71.4	71.9
	car	49.7	29.2	48.0 47.6	50.6	50.3
	cat	54.8	34.8	50.9 54.4	56.1	56.4
	chair	43.3	28.1	42.9 42.8	44.9	44.9
	dining-table	35.9	21.4	33.6 32.8	37.5	36.4
	motorbike	46.3	30.8	47.9 51.6	52.0	51.9
	person	82.0	68.6	80.0 81.3	82.4	82.4
	potted-plant	23.0	21.7	27.8 30.6	31.5	31.2
	sheep	33.0	11.1	27.5 29.7	35.0	33.0
	sofa	32.6	12.6	26.8 28.3	34.1	34.1
	train	68.2	41.1	63.5 66.1	68.4	68.6
	tv-monitor	51.6	29.5	48.1 50.8	52.6	52.3
	MAP	47.8	29.5	45.8 47.5	50.1	49.8