Julien Ah-Pine

Jean-Michel Renders

Marie-Luce Viaud
email: mlviaud@ina.fr

A Continuum between Serendipitous Browsing and Query-based Search for Multimedia Information Access

This paper deals with information seeking in a multimedia database. In such a context, we assume that the search process is complex, dynamic and multi-faceted. We suppose moreover, that the information need with respect to a topic, can change during a same search session, going from a simple lookup search to a thorough discovery of connected subtopics. We propose a system that aims at addressing these challenges. It couples serendipitous browsing and query-based search in a smooth manner. The main features of our proposal that we want to underline are the following ones. The system offers two levels, global and local, of visualizing the context of the information seeking task and it also allows to view and search the data using either monomodal or cross-modal similarities. Furthermore, the system integrates a new relevance feedback model that takes into account the multimodal nature of the data in a flexible way and a combination of two parameters, the locality and forgetting factors, that allows to design adaptive metrics in the interactive search process. These functionalities are aimed at offering tools to the user in order to solve information seeking tasks efficiently. A preliminary user-centered evaluation of our system, that we also present in this paper, gives encouraging results.

Introduction

In the Information Seeking field (see for example [START_REF] Marchionini | Exploring search: from finding to understanding[END_REF]), we can distinguish different strategies for accessing and exploring multimedia databases, in order to acquire and discover knowledge to solve some user tasks. One strategy is browsing and navigation: the aim is to browse a large digital library in order to have a general overview of the different themes and the underlying structure using a tool that groups together similar objects and visualize the similarity relations between them; the user can then explore these clusters, by zooming into particular areas, visiting specific documents and jumping to their neighbors. Another strategy is query-based search: the aim is to quickly find relevant objects with respect to a given query using a tool that takes into account the user feedback to bridge the semantic gap between the user's query and the multimedia objects. In this use case, the key features rely on avoiding redundancy and visualizing the similarity relationships between the retrieved objects so that the user can have a more rapid understanding of the different subtopics. But a more general "mixed-strategy" scenario happens when the user wants to have a mix between serendipitous search and query-based search. Indeed, it is often very hard for the user to formulate an unambiguous query, which is the direct translation of her information needs. It also happens that the user does not know exactly what she is looking for: she has a general question in mind, but absolutely no idea of the answer and in which direction she has to search. The ideal process the user wants to be involved in is a discovery process, where she could incrementally precise her requirements depending on what the system is able to propose her interactively, where she could understand the direction she is currently investigating with respect to the global picture, and where she can go back to explore new directions, being aware of the boundaries of this discovery process.

The system we propose in this paper exactly aims at addressing these complex needs, with a "mixed-strategy" approach. It offers some continuum between the browsing behavior and the query-based search behavior. In this paper, we focus on digital libraries that contain multimedia objects that are constituted of texts and/or images, even if most of the proposed methods and tools could be extended to other modes (speech, music, . . . ), once adequate monomodal similarity measures have been defined. The context of this paper is also related to information fusion in multimedia information processing and, especially, crossmedia techniques that can combine visual and textual aspects in order to bridge the gap between these two modes when exploring, exploiting and searching in databases of hybrid objects.

The rest of this paper is organized as follows. In section 2, we give an overview of the global architecture and the main novelties of our system and we detail each component. In section 3, we present some results of a preliminary user-centered evaluation based on the Cognitive Walkthrough method. Then, in section 4, we analyze some related works before concluding in section 5.

Description of the System

Global Architecture and main functionalities of the system

The architecture of the system we propose is depicted in Fig. 1. It consists of several interlinked components: the Graphical User Interface, the monomodal Search Engines, the Ranker/Scorer and the Graph Layout Map Builders. These components combined together allow to achieve the following functionalities that we think, are valuable for multimedia information seeking tasks:

• interlinked multi-scale visualization and navigation: the system offers (at least) two levels of visualizing the context of the information seeking task. One visualization is the 2D global map of the whole multimedia corpus, emphasizing the underlying structure of this corpus The structure is typically charac-terized by different clusters and sub-clusters, with mutual positions indicating how these clusters relate to each other. The second map, called the local map, synthesises the history of the current session, by representing all objects the user has to interact with, on a single 2D map that again emphasizes the underlying structure of this set of objects (clusters), as well as their mutual similarity relationships. These two maps are processed by the Graph-Layout Map Builders component that we detail in subsection 2.4. Objects of the local map are linked to their counterpart in the global map; the latter clearly indicates what are the areas that are represented on the local map. Having at least two maps makes it easier for the user to be aware of the boundaries of her search, to understand the different landscapes at different scales, and to better control the exploration (global visualization) and exploitation (local development) phases.

• multimodal views of the data: on the global map, the user can have different views of the data: she can switch to purely textual, purely visual or hybrid similarities, so that there are actually 3 static maps that co-exist. This allows the user to change the global map according to the modality she is interested in at each step of the session.

• flexible multimodal relevance feedback: on the local map, the user can label the text and the image part of a same multimedia object differently. In that way, she can associate relevant texts with relevant images that best correspond to her current multimodal information need.

• adaptable search/development metrics: our relevance feedback technique implemented in the Ranker/Scorer component described in subsection 2.3), contain several parameters that allow the user to design metrics that adapt to her information need at each iteration. First, after giving feedback, the user will typically promote different kinds of similarity for the next step: her search can rely on textual, visual or hybrid similarities. The Graph-Layout Map Builders component takes this into account so that on the local map, the metrics that define local neighbors around some nodes could be visual, while being textual or hybrid around other nodes. Next, as the system aims at providing the user with a continuum between a browse-based search and a query-based search, it allows the user to tune a suitable combination of a locality factor and a forgetting factor, that will weight accordingly all the accumulated information3 in the current session. More particularly, locality allows some selected objects to have more weight than others, in order to "develop" the similarity graphs locally and to give a new direction to the search. The forgetting factor assumes that the user is naturally more prone to give more importance to what she interacts with recently, rather than what she developed initially4 . On the map, objects impacted by the forgetting factor are indicated by their fading level or by their decreasing size. Before detailing each component, let us introduce the following definition: a session is a sequence of interactions between a user and the system, that corresponds to the same information need or task 5 . These interactions include visualizations and proposals from the system side, query formulation and/or object selection and/or relevance feedback from the user side.

The Graphical User Interfaces

The GUIs performing the global and local maps contain 3 parts (see Fig. 2 and Fig. 3). The central part represents the maps, the left part shows some detailed view of the data: when the mouse is located on an item, the associated text and image are displayed. However, the right part of the interface is different for both maps:

• For the global map, the right part includes two standard query interfaces (one for textual query such as depicted in Fig. 2, one for image query) that are typically used at the beginning of the session, in order to generate an interesting subset of objects for further developments as the "page zero" of the local map. The search engines are standard ones, typically returning the k nearest neighbors of a given query (the latter objects are then highlighted on the global map). Note that the use of query forms is optional6 as the user can simply select one or more objects of the global map to "develop" them in the local map.

• For the local map, the right part is dedicated to the parameter settings of the adaptable search/development metrics (feedback, modality, locality and forgetting factors) as it is shown in Fig. 3. Labeling of the retrieved elements (the text and/or the image of elements more precisely) is done by selecting the corresponding items with the mouse and by clicking on the "+" or "-" button of the right panel (see Fig. 3). "+" and "-" respectively represent relevant and irrelevant labels. The items which are neither annotated "+" nor "-" are considered as neutral. They have a null weight and they remain displayed on the local map with a grey color. We assume that they can be of interest for the user but not immediately. Hence, the user can label those neutral objects positively or negatively later on in a session. Then, the type of modality is a value to set among textual, visual or hybrid mode and the locality and forgetting factors are real numbers to set between 0 and 1.

The user can zoom in/out or move the map panels with the mouse roll. To launch a local map, the user selects one or several objects of the global map by clicking on them with the mouse and activates the adequate menu item. A new window appears and the local discovery/search process can start. On the local map, chosen positive items are put in red whereas negative items are first put in green but finally disappeared at the next iteration. Once the items have been labeled, clicking on the "submit" button launches the retrieval process with feedback. Results appear instantaneously on the local map and the corresponding items are highlighted on the global map.

The Ranker/Scorer Component

The Ranker/Scorer component is the core of the system: it generates at each iteration a ranked list of objects, that are considered to have the largest probability of being relevant, given the information accumulated7 up to that moment and the different search/discovery parameters8 of the current iteration. This component has also to deal with the issue of fusing the textual and visual modes, when needed; in what we propose, this could be partly realized by defining a crossmedia similarity measure based on a mix of real and pseudo-relevance feedback 9 .

We propose the formula given in eq. 1 for computing a new relevance score for each (unlabeled) object, x, of the database based on the accumulated feedback information and the control parameters chosen at the current iteration t. It can be seen as a non-trivial extension of Rocchio's method [START_REF] Rocchio | Relevance feedback in information retrieval[END_REF] to the more general case of interactive multimedia information seeking.

f t+1 (x) = (1)
γ t T      y∈T t + α t T (y) y ∈T t + α t T (y )      ST (y, x) + λT z∈B t T (y) ST (y, z)SI (z, x) z ∈B t T (y) ST (y, z )      - y∈T t - β t T (y) y ∈T t - β t T (y )      ST (y, x) + δT z∈B t T (y) ST (y, z)SI (z, x) z ∈B t T (y) ST (y, z )           +γ t I      y∈I t + α t I (y) y ∈I t + α t I (y )      SI (y, x) + λI z∈B t I (y) SI (y, z)ST (z, x) z ∈B t I (y) SI (y, z )      - y∈I t - β t I (y) y ∈I t - β t I (y )      SI (y, x) + δI z∈B t I (y) SI (y, z)ST (z, x) z ∈B t I (y) SI (y, z )          
In eq. ( 1), f t+1 (x) is the new relevance score of the (unlabeled) multimedia object x provided at iteration t + 1. The subscripts T and I respectively correspond to text and image modality. S T and S I are then the textual and visual similarity matrices.

Let denote mod t the search modality(ies) chosen by the user at iteration t. mod t can take the value T or I or H (hybrid: T and I). In the sequel, we introduce the notations with respect to the text modality only. However, since text and image play symmetric role, one can deduce the corresponding definition for the image part by simply replacing the subscript T with I, the set notation T with I and "text" with "image" in the text (and vice-versa).

γ t T reflects the weight given by the user to the text modality at iteration t. More precisely, we have γ t T = 0 if mod t = I and c T10 otherwise. T t + is the set of objects whose textual part was labeled as relevant by the user up to step t. On the contrary, T t -is the set of texts that were labeled as irrelevant up to iteration t. α t T and β t T are weights that give the importance of texts within T t + and T t -in order to compute the new relevance scores vector f t+1 . These weights take into account different parameters. First, the user can select a special subset of the items annotated at the current step t. These selected texts, S t T , correspond to the text part of the nodes of the graph around which the system should develop new elements. In comparison to other labeled items, the selected objects are given an extra weight loc t T ∈ [0, 1[ specified by the user. The greater the locality value, the more the user wants to focus on the newly selected objects. Second, the user can also explicitly mention to the system what is the importance to be given to previously annotated items. This is the forgetting factor f org t T ∈ [0, 1]. With such a factor, we assume that the weight of an annotated item will decrease with time. Thus, the older the labeling of an object (its text or image part), the lower its weight. This effect is even stricter as the forgetting factor increases. The "recentness" of the labeling is something not so trivial. Let assume that, at the current iteration t, the user decides to go back to the results provided at iteration t < t and select some of these items. This might mean that the user wants to pursue another direction in her information seeking. Therefore, we assume that the objects that were annotated from step t + 1 up to t -1 are not important anymore. Hence, we give a null weight to these items 11 . More formally, we compute the weight vectors for the annotated objects as follows 12 . Note that by default, we take ∀y ∈ T t = T t + ∪ T t -: β t T (y) = α t T (y), since this setting works better according to some preliminary experiments. ∀y ∈ T t + , we have the following definition:

α t T (y) =    1 1-loc t if y ∈ S t T (1 -f org t T ) m T (y) if y / ∈ S t T and mT (y) ≥ 0 0 if y / ∈ S t T and mT (y) = -1 (2)
where:

mT (y) =      t -dateT (y) if S t T = ∅ min z∈D t T (y) (dateT (z) -dateT (y)) if S t T = ∅ and D t T (y) = ∅ -1 if S t T = ∅ and D t T (y) = ∅ (3)
where date T (y) is the iteration number when the text of object y was annotated and D t T (y) = {z ∈ S t T : date T (z) ≥ date T (y)}. In other words, given y ∈ T t , D t T (y) is the set of selected texts z that were annotated after y. Notice that a locality factor loc t T equal to 0 amounts to give no extra weight to selected objects 13 . On the contrary, a locality factor very close to 1 will result in discarding non-selected items. Indeed, when this factor tends to 1, the nonnull contributions in the different terms of eq. ( 1) come only from the selected objects, due to the weighted average effect.

With respect to eq. ( 1), positive and negative text pseudo-relevance feedback are respectively introduced through the terms weighted by λ T and δ T . To be more precise, it is a trans-media pseudo-relevance feedback which considers as relevant the visual part of texts that are very similar to the texts fed back as relevant by the user; but this feedback mechanism discounts a pseudo-relevant object by the factor λ T and by the specific (normalized) textual similarity between the pseudo-relevant text and the corresponding labeled texts whose it is the neighbor. Accordingly, we denote B t T (y), the set of texts that haven't been annotated yet and which are the nearest neighbors of (the text part of) y. Similarly, the system considers as irrelevant the visual part of texts that are very similar to the texts fed back as non-relevant by the user. Likewise, this dual negative view of the pseudo-feedback mechanism consists of the terms weighted by the discount factor δ T in eq. (1). To be consistent, neighbors of labeled objects that are themselves labeled are never considered as pseudo-relevant objects.

The Graph-Layout Map Builders

This component is the one that produces as outputs the different maps for visualizing globally or locally the objects of interest.

Global maps are computed off-line. We first apply a sequence of several force directed layout algorithms to generate the maps, we then use the LinLog energy model [START_REF] Noack | Visual clustering of graphs with nonuniform degrees[END_REF] as the final stage. The basic material consists of thresholded similarity matrices 14 . A standard agglomerative hierarchical clustering algorithm is then applied to identify clusters in the 2D space. Cluster naming techniques allow then to extract the most representative keywords of each cluster.

The local map layout is a dynamic process: results are appended to the map at each "interactive query" performed by the user. Regarding dynamic representations, one additional constraint has been established by the visualization community: the problem of preserving the user's mental map [START_REF] Misue | Layout adjustment and the mental map[END_REF]. The objective is not to loose the user by constantly changing the map layout from one iteration to the next one: new objects are added by slightly perturbing the previous layout and using the similarity metrics promoted by the user at the current iteration, while already present objects keep their mutual similarity relations, as a result of all previous interactions. This is realized by increasing the inertia of existing nodes and by using the Fruchterman-Rheingold layout algorithm [START_REF] Fruchterman | Graph drawing by force-directed placement[END_REF], that appears to be the most adequate for this kind of task. Optionally, a clustering algorithm could be applied as well in the 2D local map, in order to avoid redundancy in the results given at the next iteration and to favor quick local exploration: only the most relevant objects of each cluster will be displayed on the map (see for example [START_REF] Ah-Pine | XRCE's participation to ImageCLEF[END_REF]). This could be considered as an indirect way of realizing diversity-based re-ranking and can be particularly valuable during the early stages of the search process.

Preliminary Evaluation of the System

Evaluation Methodology

It is difficult to assess an interactive information seeking system. Indeed, as the system is mainly designed to improve the efficiency of user feedback, traditional retrieval measures such as precision and recall are not really interesting here; other measures based on satisfaction and increase in work efficiency to solve the task are more important. Previous works already conducted user-centered evaluations in similar contexts [START_REF] Urban | An adaptive technique for content-based image retrieval[END_REF]. It has been shown that interactive methods are well-appreciated by regular user of information retrieval systems. In the following study, our goal is to have a preliminary user-based evaluation of our main contributions in multimedia information seeking namely, the interlinked multiscale and multimodal visualization and navigation and the flexible multimodal searching and relevance feedback.

To this end, we chose the Cognitive Walkthrough Inspection methodology [START_REF] Huart | Evaluation of multimedia applications using inspection methods: the cognitive walkthrough case[END_REF][START_REF] Polson | Cognitive walkthroughs: a method for theory-based evaluation of user interfaces[END_REF] to perform the evaluation. This method involves an experimented user and an evaluator and allows to observe the user behavior during the realization of a complex task. The evaluator has pre-specified scenarios and tasks to be realized, while the user 15 is already familiar with similar tasks and already using standard retrieval tools and graphical user interfaces. The procedure is the following one: the evaluator explains the goals of the task and the functionalities associated to the different sub-components of the GUI (maps, buttons, parameters,...). The user has then to choose the sequence of elementary actions in order to solve the task. But, during the evaluation, the evaluator manipulates himself the tool and asks for the functional action to be executed at the next step: the reason for this is to get rid of specific ergonomic aspects (design of buttons, choice of colors,...) and to solely focus on addressing the following points: achievability (is the set of elementary functions sufficient to solve the task?), efficiency (does the system promote the most efficient paths?), predictability (is the user able to predict the effect of the launched action?), obviousness (how intuitive is it?), proactivity (after the action, is the feedback good enough to encourage her to continue?) and, finally, confidence (is the user more confident about the obtained results?). What is eventually measured is (i) that the user is able to understand the link between the sequence of actions and the final goal of the task, and (ii) that she is able to memorize the corresponding actions and settings. At the end of the evaluation, the user is asked extra questions, related to the comparison with her existing tools, in terms of complementary or new possibilities.

Design of the Evaluation Scenarios

The multimedia collection used for the experimentation consists of text/image objects extracted from a subset 16 of pages from the French Wikipedia that are related to the general theme "Tourism in France". From each selected Wikipedia page, we extracted several multimodal objects, namely the images present in the page with their associated texts (image caption if any, text of the surrounding paragraph and sequence of titles and subtitles leading to this paragraph). Note that, due to our construction mechanism, the relationship between an image and its associated text could be noisy or very vague. This collection 17 is made of more than 50,000 text/image objects.

A task consists in solving two subtasks related to a same topic: a specific search (closed problem) and a discovery analysis (open problem). The specific search subtasks were designed in such a way that it is very unlikely to obtain the information directly by a single textual query and that combining both modalities in a flexible way is essential. The different topics presented to the user were related to: Eiffel Tower, surfing, old stamps, Charles de Gaulle and Nantes.

Description of a Particular Evaluation Scenario

In this subsection, we report some retrieval results for the Eiffel Tower scenario. For this topic, the user had to retrieve old pictures representing the Eiffel Tower and dating from the beginning of the 20th century (closed subtask). She also had to explore the collection in order to gather different multimedia objects that cover all potential subtopics related to the Eiffel Tower, as if she wanted to find as much material as possible to make a multimedia presentation on that topic (open subtask). The evaluator let the user free to solve these subtasks sequentially or in parallel, but the user actually found it more efficient to solve them simultaneously.

The user started with a general textual query "Eiffel Tower" using the basic text search engine, whose results were highlighted on the global map (see Fig. 2). She observed that a lot of items were surrounded and their distribution spread all over the global map. After a quick observation, the user mentioned that many of the highlighted objects were not relevant for the specific task. The reason is that the Eiffel Tower is often used as a generic French emblem. After zooming in some particular areas presenting a high density of highlighted results, the user picked an object whose image represents the Eiffel Tower, even if not completely relevant to the search subtask (drawing instead of picture). The latter is the black and white drawing of the Eiffel Tower in the center of Fig. 3. From this chosen element, the user started a local deployment with the "hybrid modality". The user asked to set the forgetting factor to 0.2. After 8 iterations during which 12 objects were labeled relevant and 20 irrelevant, the user obtained the results presented in Fig. 3. During this sequence, the user used the locality feature that allows to deeper focus on a set of selected objects. To be more precise, this focus was deployed on the bottom left corner of Fig. 3 which shows technical drawings of the Eiffel Tower. This resulted in a first set of objects, relevant to the second subtask but not to the first one. Next, the feedback provided by the Fig. 3. Local map for the "Eiffel Tower" topic user gave rise to the right branch which shows landscape pictures of Paris with the Eiffel Tower; once again, this set of objects was considered as relevant to the second subtask, but not to the first one. But the branch deployed on the upper left part of the map appeared to be more related to some historical events with a certain relationship with the Eiffel Tower: postcards from the 1900 universal exhibition, portrait of an engineer, etc. Among the objects that constituted this branch, the user finally found what she was looking for regarding the first subtask: two pictures of the monument with a blue and white sky on the upper left, which correspond to pictures of the Eiffel Tower dating from the beginning of the 20th century. The user noticed here that the effect of the forgetting factor was effective since the strong visual contribution of the first drawing (the item around which the user originally chose for local deployment) was progressively lowered iteration after iteration. To conclude the second subtask, the user further analyzed the global map and particularly areas presenting a strong density of results for the textual query "Eiffel Tower"; this resulted in the discovery of 3 other interesting clusters, that are relevant to the task. Fig. 4 shows an example of cluster displayed on the global map not covered by the local search: it displays portraits of famous scientists whose names are written on the Eiffel Tower.

First Conclusions drawn out of the User Evaluation

Based on the user's reactions collected during the evaluation (including global comments at the end), we address the different points raised in subsection 3.1 according to the Cognitive Walkthrough Inspection methodology:

• Achievability and predictability: in general, the user succeeded in finding satis- fying results for the search and discovery parts of each task. She had no trouble to perform the list of actions needed to obtain the results. However, some local deployments were very noisy. This is often due to the wrong association between text and image in the multimedia collection18 that can be encountered in some cases 19 . In those cases, the user would have liked to mark a positive feedback only on a selected portion of the text rather than on the whole text. Besides, the user's comments on the parameter settings, are balanced. The control on the local deployment is rich, innovative and interesting but more training is needed to really understand all its possibilities. In fact, it is not obvious to anticipate the results when using the forgetting factor, especially when both modalities are involved with different values.

• Efficiency, obviousness and proactivity: regarding the use and the selection of different modalities, it appeared that this new feature was very useful for the search in general and for cases where the image is not well-described by its associated text in particular. The use of textual queries for generating a "page zero" and initiating a search process even with objects without any text associated is particularly valuable. With respect to the use of two linked maps, the user exploited both of them for all tasks. The connection between the local and global maps during the search process turned out to be very intuitive and helpful: this feature allows to have a better perception of the content of the corpus.

Regarding the usability, the user was globally comfortable with using the maps. Navigating in the global map results appeared easy, especially with the display of the text and image in the left part of the panel just by moving the mouse on the items. Selection and launch of the local map was also easy. But, the local map parameters' setting was not obvious. The selection and labeling of the texts and/or images were all right. The use of the focus mode was intuitive.

We can formulate the following preliminary conclusions from this evaluation: • Using different modalities and particularly cross-media techniques that allow to combine visual and textual information efficiently is necessary. It allows to provide faster ways to achieve relevant results particularly when the information need is difficult to express in terms of queries and when the different modalities of the same object do not match from a semantic viewpoint20 . In that perspective, the possibility to change from one modality to the other one for visualizing and searching is interesting.

• Using one global map and one local map jointly allows the user to better control the exploitation/exploration trade-off. The local map allows the user to express her information need more precisely while the global map allows her to better understand the different boundaries of her search and discover nonexpected subtopics.

• While using the local map, the user can progressively express her information need by selecting relevant texts and/or images and discarding negative examples, in a flexible manner. As far as our multimodal feedback technique is concerned, this flexibility provides efficient ways to achieve interesting results since the user is really free to associate relevant texts with relevant images that best correspond to her multimodal information need.

• The use of extra features that are integrated in our feedback model such as forgetting and locality factors are encouraged though we should not loose the user by asking him to tune a lot of parameters. The locality factor clearly allows to have a continuum between browse-based and query-based search since the user can discover many subtopics related to a broader topic and focus on some of them at any time of a session. The forgetting factor also allows to achieve this continuum as it models the fact that the user is more aware of her last annotations rather than her first ones. Furthermore, the forgetting factor allows to decrease the importance of texts and images with different rates; this feature appeared to be particularly interesting in our evaluation scenarios.

Related Work

The literature covering interactive multimedia retrieval is very vast. However, our proposal particularly concerns information seeking in a text/image corpus. In that context, the paper [START_REF] Lu | Joint semantics and feature based image retrieval using relevance feedback[END_REF] presents a relevance feedback approach which integrates semantic (keywords) and low-level feature in the context of image retrieval. Their method is an extension of the Rocchio technique [START_REF] Rocchio | Relevance feedback in information retrieval[END_REF] which relies on a semantic network derived from the keywords associated to the images. However, their system only targets basic query-based search and the semantic network is updated using the feedback provided by the user, with no possibility to judge independently texts and images. Focusing on text/image collections, there have been many works in the context of ImageCLEFPhoto evaluation campaigns in multimodal retrieval. Particularly, the paper [START_REF] Rahman | Multi-modal interactive approach to imageCLEF 2007 photographic and medical retrieval tasks by CINDI[END_REF] tackles such a task in the case of interactive search. Their combination method is based on a hierarchical late fusion approach which is different from our technique [START_REF] Clinchant | XRCE's participation to ImageCLEF[END_REF]. Systems addressing video retrieval are also related to our proposal. Particularly, the work presented in [START_REF] Bruno | Design of multimodal dissimilarity spaces for retrieval of video documents[END_REF] shows several common aspects with our work. The authors use a multimodal similarity (or dissimilarity) space for representing the multimedia objects; they then propose to apply a one-class SVM in order to learn a classifier that separates relevant from non-relevant examples.

Concerning the visualization part of the system, a state of the art of visualization methods and tools developed for multimedia information is given in [START_REF] Goëau | State of the art on advanced visualisation methods[END_REF]. Some systems propose a multi-scale view of objects for browsing and interactively searching within a multimedia corpus. The most closely related work to our proposal is the following one [START_REF] Nguyen | Interactive access to large image collections using similarity-based visualization[END_REF]. The projection methods employed are distinct. In [START_REF] Nguyen | Interactive access to large image collections using similarity-based visualization[END_REF], they use non-linear embedding algorithms whereas we rather use graph-layout methods. Then, the main difference between the two systems is that we propose not only a multi-scale but also a multimodal view of the data.

Finally our proposal is also very close to the Ostensive Model introduced initially in [START_REF] Campbell | The ostensive model of developing information needs[END_REF]. This approach considers the information retrieval process as dynamic and it is a relevance feedback model that integrates a temporal notion to relevance. In fact, the forgetting factor that we have introduced acts exactly the same as the so-called ostensive relevance. More specifically, our system shares many common points with the following work [START_REF] Urban | An adaptive technique for content-based image retrieval[END_REF], which addresses contentbased image retrieval from a multimodal perspective and using the Ostensive Model. However, some important differences with our approach are the following ones: first, in our system there are two interlinked multi-scale maps whereas in [START_REF] Urban | An adaptive technique for content-based image retrieval[END_REF] only one map is employed; second, the multimodal nature of the data is not emphasized in the feedback and the search processes in [START_REF] Urban | An adaptive technique for content-based image retrieval[END_REF]; third, our system explicitly allows the user to annotate many candidates at each step whereas in [START_REF] Urban | An adaptive technique for content-based image retrieval[END_REF] the user is asked to select only one relevant candidate; last, the combination of textual and visual information are different in both systems.

Conclusion

In this paper, we have introduced the architecture and the key components of a system for accessing information in a multimedia digital library. The general aim of our proposal is to design a system that offers some continuum between serendipitous browsing and query-based search. We have detailed the key features and algorithms of our proposal, namely the multi-scale and multimodal navigation and the adaptive multimodal relevance feedback technique. The next steps of this work will consist in better evaluating the performances of our system from the user viewpoint since the study we have presented is a preliminary, yet encouraging, evaluation. Then, we would like to further investigate the joint use of multi-scale maps in information seeking tasks.

Fig. 1 .

 1 Fig. 1. Architecture of the proposed system

Fig. 2 .

 2 Fig. 2. Global map (with objects relevant to "Eiffel Tower" highlighted)

Fig. 4 .

 4 Fig. 4. Zoom on the Global map (with objects relevant to "Eiffel Tower" highlighted)

Mainly the initial query, if it exists, and all proposed objects that the user labeled as relevant or not relevant

The Ostensive Model introduced in[START_REF] Campbell | The ostensive model of developing information needs[END_REF] makes the same assumption. See section 4 for further details.

A task is constituted of two subtasks, a closed problem and an open problem. See subsection 3.2 for more details.

Dotted arrows on the diagram indicates that the textual and visual search engines are optional and that they are typically used only for iteration 0.

Relevance feedback labels and potential initial query.

Modality(ies) selected for searching, forgetting factor value, locality factor value

Our proposal is an interactive extension of the trans-media pseudo-relevance feedback introduced in[START_REF] Clinchant | XRCE's participation to ImageCLEF[END_REF][START_REF] Ah-Pine | XRCE's participation to ImageCLEF[END_REF][START_REF] Ah-Pine | Crossing textual and visual content in different application scenarios[END_REF] for the non-interactive case.

cT being a strictly positive pre-defined constant.

This case corresponds to the third case in eq. (3).

As mentioned beforehand, we define the weights for the text modality only but the ones corresponding to the image modality are similar.

In this case, it does not make sense to select any object.

With a user-adjustable threshold.

In our case, she is an expert archivist who is used to seek information in a multimedia database with classical systems.

The selection is based upon the categories of Wikipedia.

This collection was constructed for the purpose of the Infom@gic project. See the acknowledgments section.

This is a side effect of the way we pre-processed the French Wikipedia corpus.

In the case of the "Eiffel Tower" topic for instance, objects corresponding to other monuments appeared because there is a Wikipedia page that lists the most visited monuments in Europe, so that the same text is associated to very different images.

For example, images that have poor or noisy textual descriptions.

Acknowledgments. This work was funded by the Infom@gic project, part of the "Pôle de compétitivité Cap Digital de Paris".


Julien Ah-Pine
email: julien.ah-pine@xrce.xerox.com

Normalized kernels as similarity indices

Keywords: Kernels normalization, similarity indices, kernel PCA based clustering

Measuring similarity between objects is a fundamental issue for numerous applications in data-mining and machine learning domains. In this paper, we are interested in kernels. We particularly focus on kernel normalization methods that aim at designing proximity measures that better fit the definition and the intuition of a similarity index. To this end, we introduce a new family of normalization techniques which extends the cosine normalization. Our approach aims at refining the cosine measure between vectors in the feature space by considering another geometrical based score which is the mapped vectors' norm ratio. We show that the designed normalized kernels satisfy the basic axioms of a similarity index unlike most unnormalized kernels. Furthermore, we prove that the proposed normalized kernels are also kernels. Finally, we assess these different similarity measures in the context of clustering tasks by using a kernel PCA based clustering approach. Our experiments employing several real-world datasets show the potential benefits of normalized kernels over the cosine normalization and the Gaussian RBF kernel.

Introduction

Measuring similarity between objects is a fundamental issue for numerous applications in data-mining and machine learning domains such as in clustering or in classification tasks. In that context, numerous recent approaches that tackle the latter tasks are based on kernels (see for example [START_REF] Scholkopf | Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond[END_REF]). Kernels are special dot products considered as similarity measures. They are popular because they implicitly map objects initially represented in an input space, to a higher dimensional space, called the feature space. The so-called kernel trick relies on the fact that they represent dot products of mapped vectors without having to explicitly represent the latter in the feature space. From a practical standpoint, kernel methods allow one to deal with data that are not easy to linearly separate in the input space. In such cases, any clustering or classification method that makes use of dot products in the input space is limited. By mapping the data to a higher dimensional space, those methods can thus perform much better. Consequently, many other kinds of complex objects can be efficiently treated by using kernel methods. We have mentioned previously that kernels are generally introduced as similarity measures but as underlined in [START_REF] Vert | A primer on kernel methods[END_REF], dot products in general do not necessarily fit one's intuition of a similarity index. Indeed, one could find in the literature several axioms that clarify the definition of a similarity index and in that context, any kernel does not necessarily satisfy all of them. As an example, one of these conditions that a dot product, and thus a kernel, does not always respect, is the maximal self-similarity axiom which states that the object to which any object should be the most similar, is itself.

In this paper, we are interested in designing kernels which respect the basic axioms of a geometrical based similarity index. In that context, kernels normalization methods are useful. Basically, the most common way to normalize a kernel so as to have a similarity index, is to apply the cosine normalization. In that manner, maximal self-similarity for instance, is respected unlike for unnormalized kernels. In this work we propose a new family of kernel normalization methods that generalizes the cosine normalization. Typically, the cosine normalization leads to similarity measures between vectors that are based upon their angular measure. Our proposal goes beyond the cosine measure by refining the latter score by using another geometrical based measure which relies on the vectors' norm ratio in the feature space. We give the following example in order to motivate such normalized kernels. Let us take two vectors which are positively colinear in the feature space. In that case, their cosine measure is 1. However, if their norms are not the same ones therefore, we cannot conclude that these two mapped vectors are identical. Accordingly, their similarity measure should be lower than 1. Unlike the cosine normalization, the normalization approaches that we introduce in this paper aim at taking into consideration this point.

The rest of this paper is organized as follows. In section 2, we formally introduce new normalization methods for kernels. Then, in section 3, we give several properties of the resulting normalized kernels in the context of similarity indices. We show that using normalization methods allows one to make any kernel satisfy the basic axioms of a similarity index. Particularly, we prove that these kernel normalizations define metrics. In other words, we show that normalized kernels are kernels. In section 4, we illustrate the benefits of our proposal in the context of clustering tasks. The method we use in that regard, relies on kernel PCA based k-means clustering which can be understood as a combination between kernel PCA [START_REF] Schölkopf | Nonlinear component analysis as a kernel eigenvalue problem[END_REF] and k-means via PCA [START_REF] Ding | K-means clustering via principal component analysis[END_REF]. This two step approach is a spectral clustering like algorithm. Using several datasets from the UCI ML repository [START_REF] Asuncion | UCI machine learning repository[END_REF], we show that different normalizations can better capture the proximity relationships of objects and improve the clustering results of the cosine measure and of another widely used normalized kernel, the Gaussian Radial Basis Function (RBF) kernel. We finally conclude and sketch some future works in section 5.

Kernels and normalization methods

We first recall some basic definitions about kernel functions and their cosine normalization. We then introduce our new kernel normalization methods.

Kernel definition and the cosine normalization

Let denote X the set of objects, represented in an input space, that we want to analyze.

Definition 1 ((Positive semi-definite) Kernel). A function K : X ×X → R is a positive semi-definite kernel if it is symmetric, that is, K(x, y) = K(y, x) for any two objects x, y in X and positive semi-definite, that is:

n i=1 n i =1 c i c i K(x i , x i ) ≥ 0 (1)
for any n > 0, any choice of n objects x 1 , . . . , x n in X and any choice of any numbers c 1 , . . . , c n in R.

In the sequel, we will simply use the term kernel instead of positive semidefinite kernel. We have the following well-known property.

Theorem 1. For any kernel K on an input space X , there exists a Hilbert space F, called the feature space, and a mapping φ : X → F such that for any two objects x, y in X :

K(x, y) = φ(x), φ(y) (2)
where ., . is the Euclidean dot product.

When the objects of X are vectors represented in an input space which is an Euclidean space then, we can mention the following two well-known types of kernel functions:

-Polynomial kernels: K p (x, y) = ( x, y + c) d , with d ∈ N and c ≥ 0.

-Gaussian RBF kernels:

K g (x, y) = exp -x-y 2 2σ 2
, where . is the Euclidean norm and σ > 0.

After having recalled basics about kernels, we recall the definition of the cosine normalization of a kernel K, denoted K 0 .

K 0 (x, y) = K(x, y) (K(x, x)K(x, y)) (3)
Since we have K(x, x) = φ(x) 2 , it is easy to see that:

K 0 (x, y) = φ(x) φ(x) , φ (y) φ(y)
Moreover, we have K 0 (x, x) = 1 for all objects in X . This means that the objects in the feature space are projected on an unit hypersphere. In addition, we have the following geometrical interpretation from the feature space representation viewpoint:

K 0 (x, y) = cos(θ(φ(x), φ(y))) (4)
with θ(φ(x), φ(y)) being the angular measure between the vectors in the feature space. In order to simplify the notations, we will denote θ for θ(x, y) and cos θ for cos(θ(φ(x), φ(y))), thereafter.

Kernel normalization of order t

The main purpose of this paper is to introduce a new family of kernel normalization approaches that generalizes the cosine normalization. Our approach amounts to integrating another geometrical based measure that allows us to refine the cosine measure K 0 . This additional feature is related to the difference between the norms of the two vectors in the feature space. These normalization procedures involve generalized mean (also known as power mean) operators which generalize the classical arithmetic mean. Given a sequence of p values {a i } p i=1 = {a 1 , a 2 , . . . , a p }, the generalized mean with exponent t is given by:

M t (a 1 , . . . , a p ) = 1 p p i=1 a t i 1 t (5)
Famous particular cases of ( 5) are given by t = -1, t → 0 and t = 1 which are respectively the harmonic, geometric and arithmetic means.

Definition 2 (Kernels normalization of order t > 0). Given a kernel function K, the normalized kernel of order t > 0 for any two objects x and y of X , is denoted K t (x, y) and is defined as follows:

K t (x, y) = K(x, y) M t (K(x, x), K(y, y)) (6)
Similarly to the cosine normalization, K t (x, x) = 1 for all x ∈ X . As a result, those normalization methods also amount to projecting the objects from the feature space to an unit hypersphere. However, this family of normalized kernels goes beyond the cosine measure since it extends the latter which actually corresponds to the limit case t → 0.

In order to better interpret such measures, let us equivalently formulate K t (x, y) with respect to the following norm ratio measures, φ(x) φ(y) and φ(y) φ(x) . We can easily show that:

K t (x, y) = cos θ M t φ(x) φ(y) , φ(y) φ(x) (7)
This formulation expresses K t (x, y) according to geometrical based measures. However, let us introduce the following notation as well:

γ(φ(x), φ(y)) = max φ(x) φ(y) , φ(y) φ(x) = max( φ(x) , φ(y) ) min( φ(x) , φ(y) ) (8)
γ(φ(x), φ(y)) lies within [1, +∞[ and is related to the difference between the norm measures of φ(x) and φ(y). γ(φ(x), φ(y)) = 1 means that φ(x) = φ(y) and the greater the difference between the norms' value, the higher γ(φ(x), φ(y)).

Similarly to the angular measure, we will denote γ for γ(φ(x), φ(y)) in order to simplify the notations. Using γ, we have the different formulations below:

K t (x, y) = K t (θ, γ) = cos θ M t (γ, γ -1 ) = cos θ 2 1/t γ (1 + γ 2t ) 1/t (9)
The latter relation expresses K t (x, y) as a multiplication between two factors. On the one hand, we have the cosine index cos θ and on the other hand, we have the following term which is only dependent on γ,

2 1/t γ (1+γ 2t ) 1/t .
Following [START_REF] Filippone | A survey of kernel and spectral methods for clustering[END_REF], we observe that ∀θ : cos θ ∈ [-1, 1] and ∀t > 0, ∀γ ≥ 1 :

2 1/t γ (1+γ 2t ) 1/t ∈]0, 1]. As a result, one can see that ∀t > 0, ∀(x, y) ∈ X 2 : K t (x, y) ∈ [-1, 1].
In what follows, we detail the roles the geometrical parameters θ and γ play with respect to the introduced normalized kernels of order t. First, since ∀(φ(x), φ(y)) ∈ F 2 : γ ≥ 1; K t (θ, γ) is clearly a monotonically increasing function with respect to cos θ1 . Then, using (9), we can better underline the effect of the norm ratio γ on K t (θ, γ). Indeed, by computing the first derivative with respect to this parameter, we obtain:

∂K t ∂γ = cos θ   2 1/t (1 + γ 2t ) 1/t 1 -2γ 2t (1+γ 2t ) (1 + γ 2t ) 2/t   (10)
With the following conditions, γ ≥ 1, t > 0, one can verify that in the numerator of the second term of [START_REF] Tuytelaars | Unsupervised object discovery: A comparison[END_REF], the first factor is positive but the second one,

1 -2γ 2t (1+γ 2t ) , is negative since 2γ 2t (1+γ 2t ) ∈ [1, 2[
. Consequently, the sign of ∂K t ∂γ is the same as -cos θ. Therefore, for t > 0, K t (θ, γ) is monotonically decreasing with respect to γ providing that cos θ > 0 whereas, K t (θ, γ) is monotonically increasing with respect to γ as long as cos θ < 0 (see Fig. 1).

Intuitively, when t > 0, the norm ratio measure aims at refining the cosine measure considering that the latter is less and less "reliable" for measuring proximity, as the difference between the vectors' norms becomes larger and larger. Thereby, regardless the sign of the cosine index, the greater γ, the closer to 0 K t (θ, γ). More formally, we have: ∀t > 0, ∀θ, lim γ→+∞ K t (θ, γ) = 0.

Notice that for t < 0, we observe the opposite effect since the sign of the derivative ∂K t ∂γ is the same as cos θ. Thus, in that case, when cos θ > 0 for example, K t (θ, γ) is monotonically increasing with respect to γ. This is not a suitable behavior for a similarity measure, that's the reason why we define K t (θ, γ) for t > 0 only.

In more general terms, the sign and the value of t respectively express the nature and the degree of the influence of γ on K t (θ, γ). First, when t is negative, it defines a coefficient which is not appropriate for measuring similarity. On

θ = 1 K 0 K 1 K 10 K 100 K +∞
the contrary, when t is positive it allows one to refine the cosine measure in an appropriate way. Second, assuming that t > 0, when the latter increases, it makes γ have a more and more important impact on K t (θ, γ). In that context, it is worthwhile to mention the two following limit cases: when t → 0 we obtain the cosine index which is independent of γ, whereas when t → +∞ we have the following index2 :

K +∞ (x, y) = cos θ max φ(x) φ(y) , φ(y) φ(x) = cos θ γ (11)
To illustrate these points, we plotted in Fig. 1, the graphs corresponding to K t (θ, γ) for different values of t namely the limit when t → 0, t = 1, t = 10, t = 100 and the limit when t → +∞. In the left-hand side graph, we fixed cos θ = -1 and in the right-hand side graph, cos θ is set to 1. While the cosine measure is fixed, γ varies from 1 to 2 (the horizontal axis). The goal of these graphs is to represent the effects of the norm ratio parameter γ on the normalized kernel value (the vertical axis) for different values of t and depending on the sign of the cosine measure. For example, when cos θ = 1 and γ = 2, we can observe that, in comparison with the case t → 0 for which the normalized kernel gives 1, the value drops to 0.85 when t = 1 and it drops further to 0.5 when t → +∞.

Properties of normalized kernels as similarity indices

In this section, we want to better characterize the family of normalized kernels that we have introduced. To this end, we give some relevant properties that they respect. First, we show that K t (x, y) with t > 0 satisfies the basic axioms of geometrical based similarity indices. Second, we show that the normalized kernels of order t > 0 are kernels. This result is the main theoretical contribution of this paper.

Basic properties of K t

We start by giving some basic properties of K t (x, y) with respect to the general definition of similarity indices defined in a metric space (see for example [START_REF] Santini | Similarity measures[END_REF]). ∀(x, y) ∈ X 2 , we have:

1 ∀t > 0 : |K t (x, y)| ≤ 1 2 ∀t > 0 : K t (x, x) = 1 3 ∀t > 0 : K t (x, y) = K t (y, x) 4 ∀t > 0 : x = y ⇔ K t (x, y) = 1
According to property 1, K t (x, y) is bounded by -1 and 1 which is a common axiom required for a similarity index. Notice that unnormalized kernels do not respect this axiom in general.

Properties 2 and 3 respectively state that the normalized kernel of order t respects the maximal self-similarity axiom3 and the symmetric axiom.

According to property 4, the situation K t (x, y) = 1 corresponds to the case where the vectors are strictly identical in the feature space. Indeed, considering (9), we can see that the normalized kernel value is 1 if and only if cos θ = 1 and γ = 1 which is the same as φ(x) = φ(y). Note that property 4 is not true for the limit case t → 0 for which we only have φ(x) = φ(y) ⇒ K 0 (x, y) = 1. Since for this case the norm ratio plays no role, it is only sufficient for the vectors to be positively colinear to obtain the maximal similarity value 1. Once again, this shows that the normalized kernels of order t > 0 are similarity measures that are more discriminative than the cosine measure. It is also worth mentioning in that context, the two other particular cases: both vectors are completely opposite to each other when we observe K t (x, y) = -1 (cos θ = -1 and γ = 1) and they are geometrically orthogonal when K t (x, y) = 0 (cos θ = 0).

In what follows, we focus on the different relationships between normalized kernels of two distinct orders t and t . 5 ∀t ≥ t > 0 : sign(K t (x, y)) = sign(K t (x, y))

6 ∀t ≥ t > 0 : K t (x, y) ≤ K t (x, y) if cos θ > 0 K t (x, y) ≥ K t (x, y) if cos θ < 0 7 ∀t ≥ t > 0 : |K t (x, y)| ≤ |K t (x, y)|
Property 5 states that the sign of the similarity measure is independent of t. More precisely, the sign is only dependent on the angular measure. This is a consequence of (9) since M t (γ, γ -1 ) is strictly positive.

Properties 6 and 7 must be put into relation with the comments we made in section 2 and Fig. 1. Accordingly, these properties formally claim that as t grows, K t (x, y) makes the cosine measure less and less "reliable". We previously mentioned that, all other things being equal, the greater the difference between the vectors' norms in the feature space, the closer to 0 the normalized kernel value. These properties express the fact that this convergence is faster and faster as t grows.

These aforementioned properties are direct consequences of the following relations between generalized means, ∀0 < t ≤ t < ∞:

1 ( p i=1 a i ) 1/p > 1 M t ({a i } p i=1 ) ≥ 1 M t ({a i } p i=1 ) > 1 max({a i } p i=1 )
To complete the analysis of the basic properties that K t (x, y) respects with regards to the general axioms required for a similarity index, we need to better characterize the metric properties of the latter. We address this issue in the following subsection.

Metric properties of K t

In this paragraph we denote K t the similarity matrix of objects in X .

Theorem 2. The similarity matrix K t with t > 0 and general term given by ( 6) is positive semi-definite. In other words, any normalized kernel K t with t > 0 is a positive semi-definite kernel.

Proof (Proof of Theorem 2).

The proof of this result is based on Gershgorin circle theorem. Let A be a (n×n) complex matrix with general term A ii . For each row i = 1, . . . , n, its associated Gershgorin disk denoted D i is defined in the complex plane as follows:

D i = {z ∈ C : |z -A ii | ≤ i =i |A ii | Ri } = D(A ii , R i )
Given this definition, Gershgorin circle theorem (see for example [START_REF] Horn | Matrix analysis[END_REF]) states that all eigenvalues of A lies within i D i . Accordingly, if the norms of off-diagonal elements of A are small enough then the eigenvalues are not "far" from the diagonal elements. In other words, the lower the R i quantities, the closer to the diagonal elements the eigenvalues. Now, let us consider normalized kernel matrices of order t > 0 of objects of {x i ; i = 1, . . . , n}. Let denote K t ii = K t (x i , x i ). We first suppose the limit case t → 0. We know that K 0 is the cosine similarity matrix. As a consequence, K 0 is positive semi-definite and its eigenvalues are all non negative. Next, let us denote

R t i = i =i |K t ii |.
Then according to properties 2 and 7 given in subsection 3.1, we have:

-∀t > 0 and ∀i = 1, . . . , n :

K t ii = 1, -∀t > t > 0 and ∀i = 1, . . . , n : R t i ≤ R t i .
Therefore, when t grows, (6) defines a continuous and differentiable operator for which the absolute value of off-diagonal elements of K t , and consequently the quantities R t i ; i = 1, . . . , n, are lower and lower while the diagonal entries of K t remain equal to 1. Thus, applying Gershgorin theorem, we can see that when t increases, the spectrum of K t is closer and closer to the vector of ones with dimension n. As a consequence, since the eigenvalues of K 0 are non negative then so are the eigenvalues of K t with t > t > 0 as the latter are closer to 1 than the former. Finally, for t > 0, K t is symmetric and has non negative eigenvalues. These properties are equivalent to the conditions mentioned in Definition 1 thus, for t > 0, we can conclude that K t are positive semi-definite kernels.

Finally, a corollary of Theorem 2 [START_REF] Gower | Metric and euclidean properties of dissimilarity coefficients[END_REF], is that the related distance D t (x, y) = 2(1 -K t (x, y)) respects the triangle inequality axiom, ∀(x, y, z) ∈ X 3 :

8 ∀t > 0 : D t (x, y) ≤ D t (x, z) + D t (z, y)

Applications to clustering tasks

In order to illustrate the potential benefits of our proposal, we tested different normalized kernels of order t > 0 in the context of clustering tasks. The clustering algorithm we used is based on kernel Principal Component Analysis (kernel PCA) and the k-means algorithm. Our experiments concern 5 real-world datasets from the UCI ML repository [START_REF] Asuncion | UCI machine learning repository[END_REF]. Our purpose is to show that the normalized kernels that we have introduced, can better capture the proximity relationships between objects compared with other state-of-the-art normalized kernels.

Kernel PCA based k-means clustering

Our clustering approach is a spectral clustering like algorithm (see for example [START_REF] Filippone | A survey of kernel and spectral methods for clustering[END_REF]). First, from a kernel matrix K t , we proceed to its eigen-decomposition in order to extract from the implicit high dimensional feature space F, an explicit and proper low dimensional representation of the data. Then, we apply a k-means algorithm in that reduced space in order to find a partition of the objects.

Principal Component Analysis (PCA) is a powerful and widely used statistical technique for dimension reduction and features extraction. This technique was extended to kernels in [START_REF] Schölkopf | Nonlinear component analysis as a kernel eigenvalue problem[END_REF]. Formally, let denote λ 1 ≥ λ 2 ≥ . . . ≥ λ k-1 the leading k -1 eigenvalues of K t and v 1 , v 2 , . . . , v k-1 the corresponding eigenvectors. The low dimensional space extracted from K t that we used as data representation for the clustering step is spanned according to:

( √ λ 1 v 1 , √ λ 2 v 2 , . . . , λ k-1 v k-1
). When applying dimension reduction techniques prior to a clustering algorithm, an important issue is the number of dimensions that one has to retain. In this paper, since we aim at using the k-means algorithm as the clustering method, we follow the work presented in [START_REF] Ding | K-means clustering via principal component analysis[END_REF] that concerns the relationship between k-means and PCA. Accordingly, if k is the number of clusters to find then we retain the k -1 leading eigenvectors.

With regards to related works, we can cite the following papers that use Kernel PCA based clustering in the contexts of image and text analysis respectively, [START_REF] Tuytelaars | Unsupervised object discovery: A comparison[END_REF][START_REF] Minier | Kernel PCA based clustering for inducing features in text categorization[END_REF].

Experiments settings

The datasets that we used in our experiments are the following ones [START_REF] Asuncion | UCI machine learning repository[END_REF]:

-Iris (150 objects, 4 features in the input space, 3 clusters) -Ecoli (336 objects, 7 features in the input space, 8 clusters) -Pima Indian Diabetes (768 objects, 8 features in the input space, 2 clusters) -Yeast (1484 objects, 8 features in the input space, 8 clusters) -Image Segmentation (2310 objects, 18 features in the input space, 7 clusters)

For each data set, we first normalized the data in the input space by centering and standardizing the features. Next, we applied different kernels K namely, the linear kernel K l (x, y) = x, y which is simply the dot product in the input space, and the polynomial kernel K p (x, y) = ( x, y + 1)

2 . For each type of kernels, we computed different normalized kernels K t by varying the value of t: t → 0, t = 1, t = 10, and the limit t → +∞. To each of those similarity matrices, we applied the kernel PCA clustering method described previously. Since the kmeans algorithm is sensitive with respect to the initialization, for all cases we launched the algorithm 5 times with different random seeds and took the mean average value of the assessment measures.

Since we deal with normalized kernels that amount to projecting the objects on an unit hypersphere, we also tested the kernel PCA based k-means clustering with the Gaussian RBF kernel which presents the same property. This case is our first baseline. However, when using such a kernel, one has to tune a parameter σ. In this paper, to get rid of this problem, we applied the approach proposed in [START_REF] Zelnik-Manor | Self-tuning spectral clustering[END_REF] which suggests to use the following affinity measure:

K g (x, y) = exp - x -y 2 σ x σ y (12)
where σ x is set to the value of the distance between x and its 7th nearest neighbor. Besides, as our purpose is to show that taking into account the mapped vectors' norm ratio in addition to the cosine measure can be beneficial, we took the case t → 0, which simply corresponds to the cosine index, as a baseline as well.

The assessment measure of the clustering outputs we used is the Normalized Mutual Information (NMI) introduced in [START_REF] Strehl | Cluster ensembles -a knowledge reuse framework for combining partitionings[END_REF]. Let denote U the partition found by the kernel PCA clustering and V the ground-truth partition. This evaluation measure is denoted NMI(U, V ) and is given by: where N is the contingency table between U and V and n the total number of objects. NMI(U, V ) lies in [0, 1] and the higher the measure, the better the clustering output U .

NMI(U, V ) = k u=1 k v=1 N uv log nNuv Nu.N.v k u=1 N u. log Nu. n k v=1 N .v log N.v n (13)

Experiments results

In Fig. 2, we report the results we obtained for each dataset. On the left-hand side we give the results related to the linear kernel whereas on the right-hand side, the NMI values correspond to the polynomial kernel. In both graphs, the results provided by the Gaussian RBF kernel are shown (1st bar). Compared to this baseline we can see that the cosine measure and the normalized kernels all perform better on the datasets used in these experiments.

In comparison with the other baseline K 0 , we can observe that in most cases there are normalized kernels of order t > 0 which can lead to better NMI values. When using the linear kernel, this is true for all K t except for the Image Segmentation dataset. Furthermore, for the Iris, Ecoli and Yeast datasets, as t grows the performances are consistently better. This shows that taking into account the vectors' norm ratio in the feature space in order to refine the cosine measure, is beneficial.

In the case of polynomial kernel, not all normalization techniques are interesting since many normalized kernels do not outperform the cosine measure. However, when using this kernel, it seems that taking K 1 p as a normalization method is a good choice. Particularly, K 1 p leads to the best performances for the Iris and the Pima Indian Diabetes datasets. Besides, concerning the Image Segmentation dataset, we can see that unlike the linear kernel, the normalized polynomial kernels can outperform the cosine index since the best result is obtained with K 10 p .

Conclusion and future work

We have introduced a new family of normalization methods for kernels which extend the cosine normalization. We have detailed the different properties of such methods and the resulting proximity measures with respect to the basic axioms of geometrical based similarity indices. Accordingly, we have shown that normalized kernels are "proper" similarity indices that amount to projecting the data on an unit hypersphere. We have, in addition, proved that these normalized kernels are also kernels. From a practical standpoint, we have also validated the utility of normalized kernels in the context of clustering tasks using several realworld datasets. However, one remaining issue is the choice of the order t when normalizing a kernel. We have shown from a theoretical and a practical point of view that the norm ratio measure can make the normalized kernel more efficient but still, the weight one should give to this parameter in comparison with the angular measure is not straightforward to set. In our future work we intend to further investigate this problem.

Fig. 1 .

 1 Fig. 1. Curves respectively representing different values of K t (-1, γ) and K t (1, γ) for different t

Fig. 2 .

 2 Fig.2. NMI measures for the different datasets with different kernels (K l on the left and Kp on the right) and different normalizations (t → 0,t = 1,t = 10,t → +∞)

Or a monotonically decreasing function with respect to θ as cos θ is a monotonically decreasing function of θ.

Since we have, limt→+∞ M t (a1, . . . , ap) = max(a1, . . . , ap)

Since property 1 states that 1 is the maximal similarity value. Note that this axiom is also called minimality when dealing with dissimilarity rather than similarity[START_REF] Santini | Similarity measures[END_REF].