SYSTEM AND METHOD FOR INFORMATION SEEKING IN A MULTIMEDIA COLLECTION

[0001] This application claims the benefit of U.S. Provisional Application Ser. No. 61/243,780, filed Sep. 18, 2009, entitled SYSTEM AND METHOD FOR INFORMATION SEEKING IN A MULTIMEDIA COLLECTION, by Julien Ah-Pine, et al., the disclosure of which is incorporated herein by reference in its entirety.

[0002] The following co-pending applications, the disclosures of which are incorporated herein by reference in their entireties, are mentioned:

[0003] U.S. application Ser. No. 12/080,414, filed Apr. 2, 2008, entitled MODEL UNCERTAINTY VISUALIZATION FOR ACTIVE LEARNING, by Loïc Lecerf;

[0004] U.S. application Ser. No. 12/364,885, filed Feb. 3, 2009, entitled ADAPTIVE GRAND TOUR, by Loïc Lecerf, et al.;

[0005] U.S. application Ser. No. 12/479,972, filed Jun. 8, 2009, entitled SYSTEM AND METHOD FOR ASSISTED DOCUMENT REVIEW, by Caroline Privault, et al.;

[0006] U.S. application Ser. No. 12/233,135 filed Sep. 18, 2008, entitled QUERY TRANSLATION THROUGH DICTIONARY ADAPTATION, by Stephane Clinchant and Jean-Michel Renders; and

[0007] U.S. application Ser. No. 12/233,978, filed Sep. 19, 2008, entitled CROSS-MEDIA SIMILARITY MEASURES THROUGH TRANS-MEDIA PSEUDO-RELEVANCE FEEDBACK AND DOCUMENT RE-RANKING, by Stephane Clinchant and Jean-Michel Renders.

[0008] The exemplary embodiment relates to the information seeking field. It finds particular application in connection with serendipitous browsing combined with query-based searching in multimedia collections and will be described with particular reference thereto.

[0009] Information retrieval systems provide a user-friendly interface by which a user can retrieve documents from a database that are relevant to or match a query. Typically, an information retrieval system ranks a “top N” documents that best match the query. An example of such a system is an Internet search engine.

[0010] Many information retrieval systems are text-based. That is, the information retrieval system receives a textual query and searches textual content of documents for similarities with the textual query, such as the same or similar words or terms, common semantic content (based, for example, on derivation of semantically related words determined using an on-line thesaurus), and the like. In a more complex approach, language models may be developed to represent the query and documents to be searched, and the information retrieval is based on similarity of query and document language models.

[0011] Digital information repositories enable storage and processing of information in different media types or “modalities,” such as text, images (single images or video), audio, and the like. It is not unusual for a single document (or, more generally, an “object”) to include content of two or more different media types or modalities. In view of this, there is interest in information retrieval systems that are capable of retrieving documents based on non-textual (visual) content. Similarity between images, for example, may be based on extracted features that are expected to have semantic significance, that is, to be discriminative of the subject matter depicted in the image. Extracted features may be based on color, shape, face recognition techniques, and the like. An information retrieval system can then use a similarity measure between a query image and stored images to retrieve a subset of the stored images which may be responsive to a user's query.

[0012] Systems have also been developed which consider one or both of text similarity and image similarity in querying multimedia collections. For example, pseudo-relevance feedback may be used. In this approach, text content of multimedia documents which have been retrieved in response to an image based query may be used to enrich the query for retrieving additional documents. Trans-media similarity methods are disclosed, for example, in S. Clinchant, J.-M. Renders, and G. Csurka, “XRCE's Participation to ImageCLEF 2007,” in Working Notes of CLEF'07 Workshop (2007); and in J. Ah-Pine, C. Cifarelli, S. Clinchant, G. Csurka, and J. Renders, “XRCE's Participation to ImageCLEF 2008,” in Working Notes of CLEF'08 Workshop (2008).

[0013] Information seeking differs from the more standard information retrieval techniques in that it does not rely solely on a query to a search engine. While information retrieval is useful for finding an answer to a specific question, such the date of birth of a particular famous person, information seeking is frequently directed more generally towards a topic, such as seeking events in the life of the famous person. Various strategies have been developed for accessing and exploring multimedia databases, in order to acquire and discover knowledge through information seeking. 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 visualizes 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 searching: the aim is to find relevant objects with respect to a given query quickly 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 case, visualizing the similarity relationships between the retrieved objects allow the user to have a more rapid understanding of the different topics and sub-topics.

[0014] A more general “mixed-strategy” approach occurs when the user wants to have a mix between serendipitous searching and query-based searching. This is often because it is hard for the user to formulate an unambiguous query, which is the direct translation of the user's information needs. It may also be the case that the user does not know exactly for what he or she is looking. It would thus be advantageous for the user to engage in a discovery process, where the user could incrementally specify more precisely the user's requirements depending on what the system is able to propose as responsive objects and for this to occur interactively, where the user could understand the direction currently being investigated with respect to the global picture, and where the user can go back to explore new directions, being aware of the boundaries of this discovery process.

[0015] The following references, the disclosures of which are incorporated herein by reference in their entireties, are mentioned:

[0016] U.S. Pat. No. 7,099,860, issued Aug. 29, 2006, entitled IMAGE RETRIEVAL SYSTEMS AND METHODS WITH SEMANTIC AND FEATURE BASED RELEVANCE FEEDBACK, by Wen-Yin Liu, et al., discloses an image retrieval system which performs both keyword-based and content-based image retrieval. A user interface allows a user to specify queries using a combination of keywords and example images.

[0017] U.S. Pub. No. 2008/0249999, published Oct. 9, 2008, entitled INTERACTIVE CLEANING FOR AUTOMATIC DOCUMENT CLUSTERING AND CATEGORIZATION, by Jean-Michel Renders, et al., discloses a method in which documents are clustered or categorized to generate a model associating documents with classes. Outlier measures are computed for the documents indicative of how well each document fits into the model. If an outlier document is annotated with a label class, a possible corrective label class is identified if the annotated document has higher similarity with the possible corrective label class under the model than with the annotated label class.

[0018] In accordance with one aspect of the exemplary embodiment, a computer-implemented method for information seeking in a multimedia collection of objects is provided. The method includes providing for a user, through a graphical user interface, to select a subset of objects from a multimedia collection. At least some of the objects in the collection include first and second modalities. Representations of objects in the subset are displayed on a local map. At each of a plurality of iterations the method includes: a) providing for the user to annotate a modality of an object represented in the local map with a relevance label, whereby an object's first modality and second modality are able to be labeled independently, b) optionally, providing for the user to select at least one of the first and second modalities, c) optionally, providing for the user to select a forgetting factor for at least one of the first and second modalities, d) optionally, providing for the user to select a locality factor for at least one annotated object, e) computing relevance scores for unlabeled objects in the collection, each relevance score taking into account labels applied to other objects, computed similarity measures between the unlabeled object and the other objects in the collection, and optionally, at least one of i) the user selected at least one modality, ii) the locality factor, and iii) the forgetting factor, the forgetting factor affecting a weight applied to at least some of the labeled objects based on the iteration in which the label was applied, f) modifying the local map based on the computed relevance scores, and g) displaying the modified local map on a visual display.

[0019] In accordance with another aspect, an apparatus for information seeking in a multimedia collection of objects includes memory which stores a multimedia collection of objects, at least some of the objects in the collection comprising first and second modalities, and similarity matrices for the objects in the collection for the first and second modalities. A graphical user interface is configured for displaying a global map and a local map of objects in the multimedia collection, the local map including representations of a subset of objects in the multimedia collection. The graphical user interface is configured for inputting parameters for relevance scoring selected from a modality parameter, a locality parameter, and a forgetting factor, and for inputting relevance labels for objects, whereby an object's first modality and second modality are able to be labeled independently. A ranking component computes relevance scores for unlabeled objects in the collection based on labels applied to other objects, the selected parameters, and the similarity matrices. A graph layout component is provided for modifying the local map based on the computed relevance scores.

[0020] In accordance with another aspect, a method which allows serendipitous browsing and query based search of a multimedia collection is provided. The method includes storing a multimedia collection of objects in computer-readable memory, storing similarity matrices for text portions and image portions of the objects in the collection in computer-readable memory, receiving an input user query selected from a text query, an image query, and a combination thereof, retrieving a subset of the objects in the collection, based on the user query, and displaying representations of the retrieved objects in the subset in a two-dimensional local map on a display. The method further includes providing access to an underlying object of a user-selected object representation displayed in the local map, providing for the user to label at least one of the text part and the image part of the selected object with a relevance label, whereby the image part and text part of a multimedia object are able to be independently labeled with different relevance labels, computing relevance scores for unlabeled objects in the collection, each relevance score being a function of user-applied relevance labels to other objects in the collection and respective similarity measures retrieved from the similarity matrices, optionally reranking the relevance scores to increase diversity, and modifying the local map based on the optionally reranked relevance scores.

[0026] Aspects of the exemplary embodiment relate to an interactive apparatus embodying a system for information seeking in a multi-modal collection of objects, and to a method and computer program product for information seeking in a multi-modal collection of objects.

[0027] An “object” is used herein to mean an electronic (e.g., digital) recording of information. In its electronic form, an object may include different modalities, such as text content, image data, audio data, or a combination thereof. Text content may be computer generated from a predefined character set and can be extracted, for example, by optical character recognition (OCR) or the like. Image data may include graphics, photographs, video content, or the like and may be stored as bitmaps such as PDF, TIFF, JPEG files or the like. In the case of video content, the image data can be stored as embedded video content or as linked files, for example linked *.mov, *.mpg, *.rm, or *.mp4 files. Audio content can be stored as embedded audio content or as linked files, for example linked *.wav, *.mp3, or *.ogg files. Other media modalities are also contemplated, such as graphical animation content, computer-aided design (CAD) content, and the like. A multimedia object includes content selected from two or more media types (modalities). In the illustrative embodiments set forth herein, the modalities include text content and image content.

[0028] A “multimedia collection” refers to one or more information sources or digital libraries that contain multimedia objects and may also be referred to as a database. In the exemplary embodiment, each object in the collection includes text and/or image content and at least some or all the objects include both text and image content (hybrid objects). For example, an image and a caption or short paragraph describing the image may form a single object. In a multimedia object, the text may be linked to the image, e.g., as metadata, HTML file, or the like. As another example, a multimedia document may be stored as a single file containing both text and embedded images. The exemplary method and system may be extended to other modes (such as speech, music, and the like), by defining adequate monomodal similarity measures for these modalities.

[0029] A “session” is a sequence of interactions between a user and the system that correspond to the same information need (i.e., the same task). These interactions include visualizations and proposals from the system side and query formulation and/or object selection and/or relevance feedback from the user side.

[0030] In one aspect, a multimedia information seeking apparatus is provided that couples both serendipitous browsing and query-based search in a flexible and smooth way. The architecture of the exemplary apparatus and system it hosts offer a double perspective on the task by providing a global view and a local view of the collection, the two views being consistent and linked. This allows the user to navigate in the multimodality database, to understand its underlying structure and boundaries, and to control better the discovery process.

[0031] In another aspect, a method is provided that allows the user to perform contextual searching by introducing parameters, such as forgetting and locality factors, as well as a cross-media similarity measure that combines pseudo-relevance feedback and real relevance feedback. Tools and algorithms are provided which allow the user to judge separately the relevance of the different modes of an object and to interactively switch metrics (monomodal or multimodal metrics) in order to obtain similarity measures that adapt themselves locally to the user's needs.

[0032] The apparatus and system aim at addressing these complex needs, with a “multi-strategy,” flexible approach. This offers some continuum between pure browsing behavior and query-based search behavior, which unlike conventional methods is not memoryless. The cross-media techniques disclosed herein 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 (multimodal) objects.

[0033] As illustrated in FIG. 1, a multimedia information seeking apparatus is illustrated by way of example. A set of multimedia objects 10, such as exemplary documents 12, 14, 16 are input to the apparatus and are processed to define a multimedia collection 18. As will be appreciated, the collection 18 may include fifty or more and in some cases, hundreds of such objects. The apparatus hosts an information seeking system 20, which causes a global and/or local representation of objects in the collection to be displayed on a display 22, such as a computer monitor or screen. The exemplary system 20, illustrated in greater detail in FIG. 2, is in the form of software stored in main memory 24 of a computing device 26, and is executed by an associated computer processor 28. The processed multimedia collection 18 may be stored in memory 30 of the same or a linked computing device. Components 24, 28, 30 of the computing device 26 are linked to each other by a data/control bus 32. Wired or wireless link(s) 34 (e.g., a local area network (LAN), wide area network (WAN), or the Internet) link the system 20 to the display 22, and to a user input device 36, via an input/output interface 38. User input device 36 can be, for example, a keyboard or touch or writable screen, for inputting text, and/or a cursor control device, such as mouse, trackball, or the like, for communicating user input information and command selections to the processor 28. Computer 26 may be in the form of one or more general purpose computing device(s), e.g., a desktop computer, laptop computer, server, and/or dedicated computing device(s).

[0034] The digital processor 28 executes instructions for performing the method outlined in FIG. 3 and may serve as the computer's CPU. The processor 28 can be variously embodied, such as by a single-core processor, a dual-core processor (or more generally by a multiple-core processor), a digital processor and cooperating math coprocessor, a digital controller, or the like.

[0035] The computer memories 24, 30 may represent any type of tangible computer readable medium such as random access memory (RAM), read only memory (ROM), magnetic disk or tape, optical disk, flash memory, or holographic memory. In one embodiment, the memory 24, 30 comprises a combination of random access memory and read only memory. In some embodiments, the processor 28 and main memory 24 may be combined in a single chip.

[0036] The term “software” as used herein is intended to encompass any collection or set of instructions executable by a computer or other digital system so as to configure the computer or other digital system to perform the task that is the intent of the software. The term “software” as used herein is intended to encompass such instructions stored in storage medium such as RAM, a hard disk, optical disk, or so forth, and is also intended to encompass so-called “firmware” that is software stored on a ROM or so forth. Such software may be organized in various ways, and may include software components organized as libraries, Internet-based programs stored on a remote server or so forth, source code, interpretive code, object code, directly executable code, and so forth. It is contemplated that the software may invoke system-level code or calls to other software residing on a server or other location to perform certain functions.

[0037] It is assumed that the objects 12, 14, 16 forming the collection 18 are processed and similarity measures computed between them, which are stored in memory. In particular, features are extracted from the text and image content of the set of objects 10 forming the processed collection 18. This may be performed with an image feature extractor 40 and a text extractor 42, which extract image features and text features, respectively, from the objects of the multimedia collection. The extracted features may be selected to be discriminative of semantic content and can be used to compute similarity measures between the text and image content of different objects by a similarity measure component 44. Methods for extracting features from text and images and computing similarity measures based thereon are well known and are described, for example, in above-mentioned U.S. application Ser. Nos. 12/233,135 and 12/233,978, incorporated herein by reference in their entireties. As one example, the image features extractor 40 extracts Fisher vectors representative of the images and the text extractor 42 extracts a bag-of-words representation of the text. A monomodal similarity measure indicative of the similarity of image content or text content of two objects can be computed based on the extracted features. This pairwise similarity measure may be precomputed for each object with respect to every other object in the collection for each modality, and stored, e.g., as respective text and image similarity matrices 46, in memory, such as memory 30. In other embodiments, similarity measures may be computed at runtime.

[0038] Typically, a multimedia object 12, 14, 16 has related image(s) 48 and text 49 (FIG. 1), both of which relate to the same general subject matter. For example, a multimedia document including an image of a famous person or architectural feature will also include related text, and vice versa. Thus, the exemplary embodiment takes advantage of this in pseudo-relevance cross-modality feedback, described in greater detail below.

[0039] FIG. 2 illustrates components of the exemplary system 20, which are described in greater detail below and mentioned only briefly here. In particular, a graphical user interface (GUI) 50 includes several linked components including a textual query form 52, for accepting user input text queries, an image query form 54, for accepting user input image queries, a global map 56, a local map 58, selection and relevance labeling tools 60, for user-selection of an object and applying a label, and search and discover control parameters 62, which are user selectable, such as modality, locality, and forgetting (recency) parameters. Additionally, the system 20 includes a ranker/scorer 64, optionally, a diversity based reranker 65, a graph-layout algorithm 66 for visualization of the global and local maps 56, 58, as well as standard, monomodal text searching and image searching engines 68, 70. These components implement the following functionalities: multi-scale visualization and navigation, flexible multimodal relevance feedback and adaptable search/development metrics.

[0040] The components of exemplary system provide some or all of the following features:

[0041] 1. An architecture and a set of algorithms that couple both serendipitous browsing and query-based search (with relevance feedback) in a flexible and smooth way. This architecture offers a double perspective on the task (global and local), the two views being consistent and linked. This allows the user to navigate better in the database, to understand its underlying structure and boundaries, and to control better the discovery process (exploration of new area vs. local development around some queries or selected objects);

[0042] 2. A method and a set of tools that allow the user to do a contextual search by introducing parameters such as a forgetting factor (weight of the present interactions with respect to the previous ones in the current session) and a locality factor (weight of some selected objects with respect to other objects already labeled as relevant or non-relevant);

[0043] 3. A method that defines a cross-media similarity measure that combines pseudo-relevance feedback and real relevance feedback;

[0044] 4. Tools and algorithms that allow the user to judge separately the relevance of the different modes of an object (the user can label the image part of an object independently of its textual part) and to interactively switch metrics (mono-modal or multimodal metrics) in order to obtain similarity measures that adapt themselves locally to the user needs.

[0045] The combination of some or all of these features (algorithms, methods and tools) provides a unique system which facilitates multimodal searching.

[0046] FIG. 3 illustrates a computer-implemented method for interactive information seeking which may be performed with the apparatus and system of FIGS. 1 and 2.

[0047] The method begins at S100 and assumes the existence of a pre-processed multimodal database 18 and precomputed similarity matrices 46 as described above.

[0048] At S102, at iteration t=0 of the session, a user query may be received via the text and/or image query forms 52, 54 of the GUI 50. The query may be a text query, formed by inputting query words, an image-based query, e.g., by inputting an image of the type the user is interested in, or a query which includes both text and image.

[0049] At S104, the database may be queried based on the user's query, using the appropriate text search engine 68 for a text query and/or image search engine 70 for an image based query. In particular, a bag-of-words representation of the text query may be generated, or a fisher vector or other features based representation extracted from a query image.

[0050] At S106, a group of the objects in the database 18 is retrieved by the search engine 68, 70 as being responsive to the query. Representations 78 of the objects are generated graphically in two dimensions to be displayed in the local map 58 on the display 22 (see, e.g., FIG. 4). The representations may take the form of thumbnails which show a reduced resolution version of all or part of the underlying object, or may be simple tiles of any suitable size and shape. The represented objects in the local map 58 are also highlighted or otherwise identified in the global map 56 (see, e.g., FIG. 5).

[0051] As an alternative or in addition to inputting a query, at S107, the user may select a group of represented objects from the global map 56 and, e.g., drag and drop them onto the local map 58. These objects are still represented on the global map as well. Step S107 may take place at any time during the method and may be repeated at one or more of the following iterations. The objects represented on the local map at any one time form a subset (i.e., fewer than all) of the objects in the multimedia collection. The displayed subset may vary over time due to objects being added or removed from the displayed subset.

[0052] The following steps S108-S116 are repeated for one or more iterations t=1, 2 . . . n until the user decides to stop labeling objects or there are no more objects in the local map 58 to label.

[0053] At S108, the user reviews the local map 58 and selects an object to review, for example, by clicking on one of the object representations 78 in the local map, which opens up the underlying object 12 for inspection.

[0054] At S110 the user may decide to label the text content and/or image content of the object 12 using the selection and relevance tools 60. In one embodiment, the user may select between three labels: responsive (+), non responsive (−), and unsure (?), indicating that the user is not yet ready to label that object. Text and image content may be labeled independently, such that, for example, an object 12 may have its text labeled as relevant by the user and its image labeled as non-relevant, or vice versa. The user may also decide not to label the object at all. The user may also assign a locality label to the object, described in detail later. The labels may be in any suitable format which links the information to the object, such as a list, metadata, file header, or the like. In the local and global maps 58, 56, the labeled object representations 78 may be modified, e.g., by a change in color, shape, size, border, or the like, which is indicative of the applied label. The user may chose to label only a single object, or may label two or more objects, at each iteration.

[0055] At S112, the remaining unlabeled objects in the collection 18 are scored by the ranker/scorer 64 according to an algorithm which applies a relevance scoring function (an equation) which takes into account the previously applied object labels. As described in further detail below, the relevance scoring function takes into account a number of factors including the search modality selected by the user at the current iteration (e.g., text or image), a forgetting factor, which place more weight on objects which have been labeled in a recent iteration than in a less recent iteration, and a locality factor. The unlabeled objects are ranked, based on their scores.

[0056] At S114, a diversity-based re-ranking may be performed by reranker 65.

[0057] At S116, the visualization component 66 generates updated local and global maps based on the scores generated at S112 as optionally modified by the reranker at S114. The object representations 78 are arranged in 2D with features such as size, shape, borders, color, proximity, linking lines, and the like to emphasize their user applied labels, relevance score and/or similarity. (In FIG. 4, by way of example, the borders of the labeled objects are shown differently, for ease of illustration).

[0058] At S118, which may occur at any time during the method, the user may decide to set or change one or more control parameters, for the next iteration via selection boxes 92 displayed on the screen (FIG. 4). The selected parameters are factored into the scoring of unlabeled objects. For example, the user may select one or more of: a modality (text, image, or hybrid); text and/or image forgetting factor parameters to modify the weight placed on more recent labels; and a locality factor for a selected object. Some of the parameters may have default values which are set by the system. Some of parameters may be set directly, for example by inputting a numerical value or selecting a value from a drop down box. In other embodiments, a user clicks on a sliding scale or the like which is variable between maximum and minimum permitted settings.

[0059] At S120, if there are more unlabelled objects and if the user chooses to continue labeling, the method may proceed to S108 for a further iteration.

[0060] The method ends at S122.

[0061] The method illustrated in FIG. 3 may be implemented in a computer program product that may be executed on a computer by a computer processor. The computer program product may be a computer-readable recording medium on which a control program is recorded, such as a disk, hard drive, or the like. Common forms of computer-readable media include, for example, floppy disks, flexible disks, hard disks, magnetic tape, or any other magnetic storage medium, CD-ROM, DVD, or any other optical medium, a RAM, a PROM, an EPROM, a FLASH-EPROM, or other memory chip or cartridge, or any other tangible medium from which a computer can read and use. Alternatively, the method may be implemented in a transmittable carrier wave in which the control program is embodied as a data signal using transmission media, such as acoustic or light waves, such as those generated during radio wave and infrared data communications, and the like.

[0062] The exemplary method may be implemented on one or more general purpose computers, special purpose computer(s), a programmed microprocessor or microcontroller and peripheral integrated circuit elements, an ASIC or other integrated circuit, a digital signal processor, a hardwired electronic or logic circuit such as a discrete element circuit, a programmable logic device such as a PLD, PLA, FPGA, Graphical card CPU (GPU), or PAL, or the like. In general, any device, capable of implementing a finite state machine that is in turn capable of implementing the flowchart shown in FIG. 3, can be used to implement the information seeking method.

[0063] The exemplary system 20 integrates the following functionalities:

[0064] The system 20 offers (at least) two levels of visualizing the context of the information seeking task. One is the 2D global map 56 of the whole multimedia corpus, emphasizing the underlying structure of this corpus, from different modal perspectives. The user can switch to purely visual, purely textual, or a hybrid view so that, in fact, three static maps co-exist. The structure is typically characterized by different clusters and sub-clusters, with mutual positions indicating how these clusters relate to each other.

[0065] The second, local map 56, synthesizes the history of the current session, by representing all objects the user has to interact with (which may be based on the user's query) on a single 2D map that once again emphasizes the underlying structure of this set of objects (clusters), as well as their mutual similarity relationships. By default, the user does not impose a particular modal perspective, although the user can select to do so via selection box 90. Unless a mode is selected, the system 20 reflects the history of the search by having different metrics depending on the previous interactions in the same session as discussed below. Objects in the local map are linked to their respective counterparts in the global map 56; the latter indicates clearly what is (or what are) the area(s) of the global map 56 that are represented on the local map 58. The global map 56 not only provides the user with a clear context of the current search status, but also with a way to drastically change the search area by favoring exploration rather than exploitation of the current search results. Presenting objects on a map allows the user to perform serendipitous browsing, see G. Marchionini. Exploring search: From Finding to Understanding, Communications of the ACM, 49:41-46, 2006, and, consequently, to focus on the recall (and not necessarily the precision) with respect to the user's information need. Having at least two maps (one global, one local) makes it easier for the user to be aware of the boundaries of the user's search, to understand the different landscapes at different scales, and to control better the exploration and exploitation (local development) phases, by switching from one map to the other.

[0066] The user can provide qualitative judgments on the different results that the system 20 proposes. The user feedback can be expressed in a flexible way: given a multimodal object, the user can give different judgments to the image part and to the textual part of the same object at S110.

[0067] For example, the user can give a positive feedback to the image and a negative feedback to the text (or vice versa). It may be noted that, unlike the previous functionality, relevance feedback aims more at improving the precision of the system. Furthermore, since the user can go back and forth between the global and the local maps, the user can discover relevant (or irrelevant) objects in the former that were not displayed in the latter. For example, the user can drag and drop objects from the global map 56 to the local map 58 that the user may find interesting to label.

[0068] The user can promote different kinds of similarity for searching. The search can rely on textual similarities, visual similarities, or hybrid text and visual similarities. The user can switch this modality at any time during a search session. The 2D local map 58 takes this into account so that, around some nodes 94, the metrics that define local neighbors could be visual, while being textual or hybrid around other nodes 96. The same map 58 can then include different similarity metrics. The objective of this approach is not to lose the user by constantly changing the local map layout from one iteration to the next one. Rather, 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.

[0069] The system aims at providing the user with a continuum between a pure browsing behavior (serendipitous search, guided by similarity links) and a query-based search with relevance feedback. This is done by using a suitable combination of a locality factor and a forgetting factor, that will weight accordingly all the accumulated information in the current session (mainly the initial query at t=0, if it exists, and all proposed objects that the user labeled as relevant or not relevant). More particularly, the locality factor allows some selected objects to have more weight than others, in order to “develop” the similarity graphs locally. The forgetting factor assumes that the user is naturally more prone to give more importance to what the user interacts with recently, rather than what developed initially. Indeed, it is often the case that, at the early stage of the session, the user has only a vague knowledge of what the user is looking for and that the needs become increasingly more precise as the user interacts with the system.

[0070] In one embodiment, at each iteration of the session, the system 20 tries to promote diversity when proposing new objects to be judged as relevant or not by the user. This may be based on an implicit clustering (e.g., the MMR (Maximum Marginal Relevance) method or an explicit clustering. Avoiding redundancy is realized by a re-ranking phase, where objects very similar to (or in the same cluster as) objects with better relevance scores, are downgraded.

[0071] The general system architecture has been described with respect to FIGS. 1 and 2 above. Some aspects of the system 20 are now described in greater detail.

[0072] A. The Graphical User Interface:

[0073] The GUI 50 includes two standard query interfaces 52, 54 (one for textual query, one for image query) that are typically used at the beginning of the session (iteration t=0), in order to generate an interesting subset of objects for further development as the “zero page” on the local map 58 (with corresponding highlighting on the global map 56). The search engines 68, 70 may be standard ones, typically returning the k nearest neighbors of a given query (textual or visual). The query is therefore considered as a non-static relevant object, which is then integrated in the ranking algorithm as any other static object. Note that the use of query forms is optional as the user can simply select one or more objects of the global to “develop” them in the local map.

[0074] The GUI also allows the user to select objects (or sets of objects such as clusters) from both the global and the local maps 56, 58, for further local expansion; to label objects (or sets of objects) as relevant or non-relevant for each mode independently, and to control the search process for the next iteration by setting the modality, locality and forgetting factors that are used by the ranker/scorer component 64. More specifically, given a multimodal item, the user can give different judgments for the visual and textual parts of this object. For example, where color is used to denote relevance, the corresponding negatively labeled part is then color-reversed in the map. After giving feedback, the user will typically promote different kinds of similarity for the next step. The search can rely on textual, visual or hybrid similarities (independently from the modalities of the feedback). The 2D local map takes this into account so that, around some nodes, the metrics that define local neighbors could be visual, while being textual or hybrid around other nodes. Finally, as the system aims at providing the user with a continuum between a pure browsing behavior (serendipitous search, guided by similarity links) and a query-based search with relevance feedback, it allows the user to tune a suitable combination of a locality factor and a forgetting factor, that will weight accordingly all the accumulated information in the current session (mainly the initial query, if it exists, and all proposed objects that the user labeled as relevant or not relevant). More particularly, locality allows some selected objects to have more weight than others, in order to “develop” the similarity graphs locally. The forgetting factor assumes that the user is naturally more prone to give more importance to what the user interacts with recently, rather than what the user developed initially. On the map 56, 58, objects impacted by the forgetting factor are indicated by their fading level (or alternatively, by their decreasing size).

[0075] B. The Ranker/Scorer Component 64: Multimodal Relevance Feedback

[0076] At each iteration, Ranker/Scorer component 64 generates a ranked list of objects that are considered to have the largest probability of being relevant, given the information accumulated up to that moment (based on relevance feedback labels and potential initial query) and the different search/discovery parameters of the current iteration (local development around some one or more nodes, modality and forgetting factor to be given to objects annotated at previous interactions). This component also accommodates the fusing of the textual and visual modes, when needed. In the exemplary embodiment, this may be partly realized by defining a cross-media similarity measure based on a mix of real and pseudo-relevance feedback.

[0077] Table 1 lists parameters which are utilized in the algorithm applied by the ranker/scorer. It is assumed that the user performs several labeling operations t=1, 2 . . . n, on a set of objects, the highest positive value of t corresponding the most recently applied label.

[0078] In what follows, the shortcuts “image” and “text” are used to refer respectively to visual part and textual part of some multimedia object.

TABLE 1
NOTATION	MEANING
Y	A labeled object in the collection
ST	Textual similarity matrix- may be stored in memory and include pre-computed
	similarity measures between all pairs of the text parts of the objects
SI	Image similarity matrix- may be stored in memory and include pre-computed
	similarity measures between all pairs of the image parts of the objects
modt	Modality variable (type of similarity chosen by the user at step t);
	could take 3 values: text (T), Image (I), or Hybrid (H)
γTt	Weight given to the textual mode according to the modality(ies) chosen by
	the user
γIt	Weight given to the visual mode according to the modality(ies) chosen by
	the user
ft+1 (x)	Relevance score of a multimedia object x at step t + 1
T+t	Set of objects whose textual part has been labeled as relevant by
	the user up to step t
αTt	Weight vector given to the objects whose textual part was
	labeled as positive (relevant) and which depends on t. The
	weight vector has the effect of decreasing importance of a text
	part that was annotated at the very beginning of the session.
	This vector takes into account the locality factor and the
	forgetting factor at current iteration t
T−t	Set of objects whose textual part has been labeled as non-relevant
	by the user up to step t
βTt	Weight vector given to the objects whose textual part was
	labeled as negative (non-relevant) and which depends on t
	(through the locality and forgetting factors)-analogous to αTt
I+t	Set of objects whose visual part has been labeled as relevant by the user
	up to step t
αIt	Weight vector given to the objects whose visual part was labeled
	as positive (relevant) and which depends on t
I−t	Set of objects whose visual part was labeled as non-relevant by
	the user up to step t
βIt	Weight vector given to the objects whose visual part was labeled
	as negative (non-relevant) and which depends on t (through the
	locality and forgetting factors).
λT	Global weight of the (text to image) pseudo-relevance feedback
	(PRF) component (that implements cross-media similarities)
	(PRF applied to positive examples)
δT	Global weight of the (text to image) pseudo-relevance feedback
	(PRF) component (that implements cross-media similarities)
	(PRF applied to negative examples)
λI	Global weight of the (text to image) pseudo-relevance feedback
	(PRF) component (that implements cross-media similarities)
	(PRF applied to positive examples)
δI	Global weight of the (text to image) pseudo-relevance feedback
	(PRF) component (that implements cross-media similarities)
	(PRF applied to negative examples)
T0t	Set of objects whose textual part has been labeled as neutral by the
	user up to step t. Typically they are the texts that appear on the local
	map and which are not labeled as relevant nor irrelevant by the user.
I0t	Set of objects whose image part has been labeled as neutral by the
	user up to step t. Typically they are the images that appear on the
	local map and which are not labeled as relevant nor irrelevant by the
	user.
At	Set of all already annotated objects:
	T+t ∪ T−t ∪ T0t ∪ I+t ∪ I−t ∪ I0t.
KT(y)	Set of nearest neighbors of an object y according to the textual
	similarity vector ST(y,:)
KI(y)	Set of nearest neighbors of an object y according to the visual
	similarity vector SI(y,:)
BTt(y)	Set of textual nearest neighbors of object y that have not yet
	been annotated, BTt(y) = KT(y) − At,
BIt(y)	Set of textual nearest neighbors of object y that have not yet
	been annotated BIt(y) = KI(y) − At,
T	Current iteration number
dateT(y)	Iteration number when text of object y was annotated (it is the
	most recent one, in the case when the user has labeled it more
	than once.
dateI(y)	Iteration number when image of object y was annotated.
forgt	Forgetting factor: forgt ∈[0.1]
STt	Set of selected texts (for locality). STt ⊂ Tt
SIt	Set of selected images (for locality). SIt ⊂ It
loct	Locality factor for objects of interest chosen by the user at
	iteration t, loct ∈[0.1].
Tt	Set of objects whose textual part has been labeled:
	Tt = T+t ∪ T−t
It	Set of objects whose visual part has been labeled: It = I+t ∪ I−t
DTt(y)	Given an object y in Tt, it is the set of selected texts z that was
	annotated after y, such that dateT(z) ≧ dateT(y).
DIt(y)	Given an object y in It, it is the set of selected images z that was
	annotated after y, such that dateI(z) ≧ dateI(y).

[0079] In one embodiment, the ranking algorithm uses similarity matrices and cross-media similarities. Equation 1 provides a basic formula for computing, at each iteration, a new relevance score f^t+1(x) for each unlabeled object, of the database, based on the accumulated feedback information and the control parameters the user has chosen for the current iteration t.

$\left(\mathrm{Eqn}.1\right)$ $f^{t+1}\left(x\right)=\hspace{1em}{\gamma }_T^t\left[\begin{array}{c}\sum _{y\in T_{+}^t}\frac{{\alpha }_T^t\left(y\right)}{\sum _{y^{\prime }\in T_{+}^t}{\alpha }_T^t\left(y^{\prime }\right)}\left(S_T\left(y,x\right)+{\lambda }_T\frac{\begin{array}{c}\sum _{z^{\prime }\in B_T^t\left(y\right)}\\ S_T\left(y,z\right)S_I\left(z,x\right)\end{array}}{\sum _{z^{\prime }\in B_T^t\left(y\right)}S_T\left(y,z^{\prime }\right)}\right)-\\ \sum _{y\in T_{-}^t}\frac{{\beta }_T^t\left(y\right)}{\sum _{y^{\prime }\in T_{-}^t}{\beta }_T^t\left(y^{\prime }\right)}\left(S_T\left(y,x\right)+{\delta }_T\frac{\begin{array}{c}\sum _{z\in B_T^t\left(y\right)}\\ S_T\left(y,z\right)S_I\left(z,x\right)\end{array}}{\sum _{z^{\prime }\in B_T^t\left(y\right)}S_T\left(y,z^{\prime }\right)}\right)\end{array}\right]\begin{array}{c}\leftarrow A\\ \leftarrow B\end{array}+{\gamma }_I^t\left[\begin{array}{c}\sum _{y\in I_{+}^t}\frac{{\alpha }_I^t\left(y\right)}{\sum _{y^{\prime }\in I_{+}^t}{\alpha }_I^t\left(y^{\prime }\right)}\left(S_I\left(y,x\right)+{\lambda }_I\frac{\begin{array}{c}\sum _{z\in B_I^t\left(y\right)}\\ S_I\left(y,z\right)S_T\left(z,x\right)\end{array}}{\sum _{z^{\prime }\in B_I^t\left(y\right)}S_I\left(y,z^{\prime }\right)}\right)-\\ \sum _{y\in I_{-}^t}\frac{{\beta }_I^t\left(y\right)}{\sum _{y^{\prime }\in I_{-}^t}{\beta }_I^t\left(y^{\prime }\right)}\left(S_I\left(y,x\right)+{\delta }_I\frac{\begin{array}{c}\sum _{z\in B_I^t\left(y\right)}\\ S_I\left(y,z\right)S_T\left(z,x\right)\end{array}}{\sum _{z^{\prime }\in B_I^t\left(y\right)}S_I\left(y,z^{\prime }\right)}\right)\end{array}\right]\begin{array}{c}\leftarrow C\\ \leftarrow D\end{array}$

[0080] Note that Eqn. 1 has four terms which will be referred to as terms A, B, C, and D. Terms A and B, within the bracket preceded by γ_T^t, relate to the text portion of the objects. Term A considers the positively labeled text parts of each object y. Term B, after the minus sign, considers the negatively labeled text parts of objects y. Terms C and D, within the bracket preceded by γ_I^t, consider the corresponding positively and negatively labeled image parts of objects y. Within each term A, B, C and D, subparts A1, B1, C1, and D1 considers the similarity matrix value S_T or S_I, respectively, between objects y and x, obtained from the respective text or image similarity matrix 46. Subparts A2, B2, C2, and D2, preceded by λ_T, δ_T, λ_I, and δ_I, respectively, are pseudo-relevance components which are described in greater detail below.

[0081] In Eqn. 1, the scalars γ_T^t and γ_I^t are weights that reflect the search modality(ies) chosen by the user at the current iteration. More precisely, at each iteration:

$\begin{array}{cc}{\gamma }_T^t=\{\begin{array}{cc}0& \mathrm{if}{\mathrm{mod}}^{t}=I\\ c_T& \mathrm{otherwise}\end{array}\mathrm{and}& \left(\mathrm{Eqn}.2\right)\\ {\gamma }_I^t=\{\begin{array}{cc}0& \mathrm{if}{\mathrm{mod}}^{t}=T\\ c_I& \mathrm{otherwise}\end{array}& \left(\mathrm{Eqn}.3\right)\end{array}$

where c_T and c_I are pre-defined constants. In one embodiment c_T and c_I have values which are greater than 0 and ≦1. Thus, for example, if at the current iteration, the user has selected the text modality, T, then terms C and D of Eqn. 1 are thus multiplied by zero and relevance score f^t+1(x) is solely dependent on terms A and B. If, on the other hand, the user selects the hybrid modality H (text and image are to be considered), then γ_T^t takes a value c_T and γ_I^t takes a value c_I.

$\mathrm{In}\mathrm{Eqn}.1,\sum _{y^{\prime }\in T_{+}^t}{\alpha }_T^t\left(y^{\prime }\right),\sum _{y^{\prime }\in T_{-}^t}{\beta }_T^t\left(y^{\prime }\right),\sum _{y^{\prime }\in I_{+}^t}{\alpha }_I^t\left(y^{\prime }\right),\mathrm{and}\sum _{y^{\prime }\in T_{-}^t}{\beta }_I^t\left(y^{\prime }\right)$

are normalizing factors for normalizing the respective weight vectors. Similarly,

$\sum _{z^{\prime }\in B_T^t\left(y\right)}S_T\left(y,z^{\prime }\right),\sum _{z^{\prime }\in B_T^t\left(y\right)}S_T\left(y,z^{\prime }\right),$

etc. are normalizing factors for the pseudo-relevance components of terms A, B, C and D.

[0082] The vectors a_T^t,a_I^t,β_T^t,β_I^t are weights that give the importance of (positively or negatively) annotated texts or images at a given iteration in order to compute the new relevance scores. These weights take into account different parameters, as follows:

[0083] First, the user can select a subset of the current annotated items. These selected objects are defined S_T^t and S_I^t, which correspond to the nodes of the graph around which the system 20 should develop new elements. These elements are given an extra weight loc^t compared to other labeled objects.

[0084] Second, the user can explicitly assign the importance to be given to previously annotated data. This is the forgetting factor (forg^t). With such a factor, it is assumed that the weight of an annotated item will decrease with time. Thus, the older the annotation given to an element, the lower the weight of the latter. The user (or the system, through default settings) can control this parameter and choose to give different kinds of weights' distribution.

[0085] The “recentness” (or oldness) of the labeling can be modified based on the user's past behavior. Suppose that the current iteration is t. Assume that the user decides to go back to the results provided at iteration t′<t and selects some objects of iteration t′. This may mean that the user wants to pursue another direction in information seeking. Therefore, it is assumed that the texts and images that were annotated from step t′+1 up to t−1 are no longer important. Hence, a null weight may be given to these objects.

[0086] According to the notations given in Table 1, the weight vectors for the annotated texts are computed as follows. In one embodiment, β_T^t(y)=α_T^t(y) (which has been found to work well in practice), although in other embodiments, these weights may be computed differently. Then, for example,

$\begin{array}{cc}\forall y\in T^t\text{:}{\alpha }_T^t\left(y\right)=\{\begin{array}{cc}\frac{1}{1-{\mathrm{loc}}^t}& \mathrm{if}y\in S_T^t\\ {\left({\mathrm{forg}}^t\right)}^{m_T\left(y\right)}& \mathrm{if}y\notin S_T^t\mathrm{and}m_T\left(y\right)\ge 0\\ 0& \mathrm{if}y\notin S_T^t\mathrm{and}m_T\left(y\right)=-1\end{array}& \left(\mathrm{Eqn}.4\right)\\ \mathrm{where}\text{:}m_T\left(y\right)=\{\begin{array}{cc}t-{\mathrm{date}}_T\left(y\right)& \mathrm{if}S_T^t=\\ \underset{z\in D_T^t\left(y\right)}{\min }\left({\mathrm{date}}_T\left(z\right)-{\mathrm{date}}_T\left(y\right)\right)& \mathrm{if}D_T^t\left(y\right)\ne \\ -1& \mathrm{if}D_T^t\left(y\right)=\end{array}& \left(\mathrm{Eqn}.5\right)\end{array}$

[0087] where D_T^t(y)={z ∈ S_T^t: date_T(z)≧date_T(y)} and Ø represents an empty set.

[0088] The second condition of m_T(y) takes care of the case where a user has decided to go back to a prior iteration and select an object for labeling from that iteration.

[0089] In one embodiment, the locality factor loc^t can vary between 0 and 1. It can be seen that a locality factor loc^t equal to 0 amounts to giving no extra weight to selected objects (in this case, it does not make sense to select any object). On the contrary, a locality factor equal to 1 will result in discarding all the non-selected items. Indeed, when this factor tends to 1, the only non-null contributions in the different terms of Eqn. (1) come from the selected objects, due to the weighted average effect. In one embodiment, the system 20 automatically assigns a default locality factor 0</loc^t<1 to all objects that the user identifies as being selected objects.

[0090] Similarly, for the image part, the equations below may be applied. Once again, it may be assumed that β_I^t(y)=α_I^t(y),

$\begin{array}{cc}\forall y\in I^t\text{:}{\alpha }_I^t\left(y\right)=\{\begin{array}{cc}\frac{1}{1-{\mathrm{loc}}^t}& \mathrm{if}y\in S_I^t\\ {\left({\mathrm{forg}}^t\right)}^{m_I\left(y\right)}& \mathrm{if}y\notin S_I^t\mathrm{and}m_I\left(y\right)\ge 0\\ 0& \mathrm{if}y\notin S_I^t\mathrm{and}m_I\left(y\right)=-1\end{array}& \left(\mathrm{Eqn}.6\right)\\ \mathrm{where}\text{:}m_I\left(y\right)=\{\begin{array}{cc}t-{\mathrm{date}}_I\left(y\right)& \mathrm{if}S_I^t=\\ \underset{z\in D_I^t\left(y\right)}{\min }\left({\mathrm{date}}_I\left(z\right)-{\mathrm{date}}_I\left(y\right)\right)& \mathrm{if}D_I^t\left(y\right)\ne \\ -1& \mathrm{if}D_I^t\left(y\right)=\end{array}& \left(\mathrm{Eqn}.7\right)\end{array}$

[0091] where D_I^t(y)={z ∈ S_I^t: date_I(z)≧date_I(y)}.

[0092] Negative and positive pseudo-relevance feedback is respectively introduced through the terms A2, B2, C2 and D2, which are weighted by δ_T,δ_I and λ_T,λ_I, respectively, in Eqn. (1). The pseudo-relevance terms assume that text and image of an object are more likely to have a similar relevance. To be more precise, it is a trans-media pseudo-relevance feedback, which considers as relevant, the textual part of images z that are very similar to the images fed back as relevant by the user. However, this feedback mechanism discounts a pseudo-relevant object by the factors λ_T or λ_I and by the specific (normalized) visual similarity between the pseudo-relevant object and the corresponding neighboring labeled objects. Similarly, the system 20 considers as irrelevant, the textual part of images that are very similar to the images fed back as non-relevant by the user, the feedback mechanism discounts such pseudo-relevant object by the general δ_T or δ_I factors and by the specific (normalized) similarity between this pseudo-relevant object and the corresponding labeled neighboring objects. To be consistent, neighbors of labeled objects that are themselves labeled are never considered as pseudo-relevant objects.

[0093] C. The Diversity-Based Re-Ranker 65

[0094] The Ranker/Scorer 64 outputs are optionally post-processed by the diversity-based re-ranker 65 whose role is to avoid redundancy in what will be proposed to the user at the next iteration and to favor quick local exploration. This component can be intimately coupled with the graph-layout component 66 by basing its decision on the cluster structure revealed by the graph-layout component (this ensures consistency between both modules). In one embodiment, component 65 may be disabled after a sufficient number of iterations if the user's objective is to get as many relevant objects as possible (focusing on recall), rather than quickly identifying one single object that fits the user's information needs. The re-ranker 65 may employ an algorithm based on an implicit clustering (e.g., the MMR—Maximum Marginal Relevance—method) or an explicit clustering. Avoiding redundancy is realized by a re-ranking phase (S114), where objects very similar to (or in the same cluster as) objects with better relevance scores, are downgraded. The diversity-based re-ranker may be configured similar to that described in J. Ah-Pine, C. Cifarelli, S. Clinchant, G. Csurka, and J. Renders. XRCE's Participation to ImageCLEF 2008, In Working Notes of CLEF'08 Workshop. 2008. Clustering methods and re-ranking strategies (explicit clustering and implicit clustering based on the maximal marginal relevance paradigm) are discussed in that reference.

[0095] D. The Graph-Layout Component 66

[0096] For the global map 56, a sequence of several force directed layout algorithms may be applied to generate the different views of the global map. The final stage may use the LinLog energy model. (See A. Noack, Visual “Clustering of Graphs with Non-Uniform Degrees,” in Proc. Int. Symp. on Graph Drawing (GD'05), pages 309-320. Springer-Verlag, 2005). The component 66 includes threshold similarity matrices, which may have a user-adjustable threshold. A standard agglomerative hierarchical clustering algorithm is then applied to identify clusters in the 2D space. Cluster naming techniques allow extraction of the most discriminative, representative keywords of each cluster.

[0097] The local map layout is a dynamic process. Results are added on the map at each “interactive query” performed by the user. Regarding dynamic representations, one additional constraint may be applied which considers the problem of preserving of the user's mental map (See, e.g., K. Misue, P. Eades, W. Lai, and K. Sugiyama, Layout Adjustment and the Mental Map, J. Visual Languages & Computing, 6:183-210, 1995). The objective is not to lose the user by constantly changing the map layout from one iteration to the next one. Thus, in one embodiment, 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 (See, e.g., T. M. J. Fruchterman and E. M. Reingold, “Graph Drawing by Force-Directed Placement,” Softw., Pract. Exper., 21:1129-1164, 1991) or other algorithm of this kind.

[0098] Optionally, a clustering algorithm is also applied in the 2D local map 56, in order to avoid redundancy in what will be proposed to the user at the next iteration and to favor quick local exploration. In this embodiment, only the most relevant objects of each cluster are displayed on the local map (see, for example, J. Ah-Pine, C. Cifarelli, S. Clinchant, G. Csurka, and J. Renders, “XRCE's Participation to ImageCLEF 2008,” in Working Notes of CLEF'08 Workshop, 2008). 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 process.

[0099] By way of example, FIGS. 4 and 5 illustrate local and global maps 58, 56 of a collection of objects which include, within the global collection 18, objects relating to the Eiffel Tower dating back to the beginning of the 20^th Century. Suppose that a user is interested in old pictures of the Eiffel Tower and wishes to retrieve as broad a range of information as possible. The user may start by looking at the global map, however, may find it more efficient to start by entering a query by typing “Eiffel+tower” in the textual query form 52. The text search engine 68 retrieves a subset of objects 14, 16, etc. which include, within the text component 49, the words Eiffel and Tower (or semantically acceptable equivalents thereof). The responsive objects are highlighted in the global map 56 (FIG. 5). Representations 78, such as thumbnails, of the retrieved objects are displayed in the local map 58. The user may click on one of the objects represented. The underlying object 14 is then displayed on the screen, e.g., beside the local map at 98 (FIG. 4).

[0100] Suppose that the user finds that although the text includes information about the Eiffel tower that he is interested in, the image is one of the designer, Gustave Eiffel. He decides to label the text portion as relevant and the image portion as non relevant. He also decides to select the image modality via the modality selector 90, to see if there are other images of the Eiffel tower. At any time, the user may also select scoring parameters via the respective parameter selectors 92. The ranker/scorer component 64 then scores the unlabeled objects in the collection based on the labels applied to the object(s) the user has reviewed and the similarity measures retrieved from the similarity matrices. If he has selected the image modality as a parameter, the ranker/scorer component 64 places greater weight on finding similar images, and the modified local map places greater emphasis on these. The system 20 may also retrieve additional objects from the collection containing similar images to the labeled object which were not originally on the local map, for example, because they did not include the words Eiffel and Tower in any text portion of the object. The system may add these new objects to the local map.

[0101] The user may go through several iterations, labeling new objects and at each iteration, the ranking component recomputes the scores/ranking of the unlabeled objects and the local map is modified accordingly. After the user has labeled a few of the objects, he may decide than one of the objects provides a particularly good image of the Eiffel Tower and give it an image locality label, which causes the system to use this as a node 96, around which a cluster of the most similar images. The user may review some of the images in the cluster and label them. Objects which are labeled as not relevant, with respect to both the image and text may be dropped from the local map 58 at the next modification. The user may later switch to the text modality and find an object which describes the construction of the Eiffel Tower in an informative way and label this object with a text locality label. The system 20 then generates a cluster using this object as a new node, around which objects with similar text are arranged. The original cluster of labeled objects, around the node 96, remain unperturbed. Eventually, the user may store some of the most interesting objects in a separate memory location for later review and/or printing.

[0102] In the example scenario, on reviewing the global map, the user may observe that a large proportion of the highlighted objects are surrounded by non-highlighted objects and their distribution is spread all over the global map. After a quick observation of some of the highlighted objects, the user may infer that many of the highlighted objects are not relevant for the specific task. The reason is that the Eiffel Tower is often used as a generic French emblem. After zooming in on the global map to review particular areas presenting a high density of highlighted results, the user picks an object whose image represents the Eiffel Tower. Even if not completely relevant to the search subtask (it may be a black and white drawing instead of a photograph, as shown at 95 in FIG. 4). From this chosen element, the user starts a local deployment with the “hybrid modality”. The user sets the forgetting factor to 0.2. After 8 iterations during which 12 objects are labeled relevant and 20 irrelevant, the user obtains the results shown in FIG. 4. During this sequence, the user uses the locality feature that allows deeper focus on a set of selected objects. During the iterations, the user may explore different regions of the global map, until a branch of the global map in the upper left part of the map is selected, as it appears to be more related to 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 finds what she is looking for: 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 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. Using one global map and one local map jointly allows the user to control better the exploitation/exploration trade-off. The local map allows the user to express the information need more precisely while the global map allows the user to understand better the different boundaries of the search and discover unexpected subtopics.

[0103] While using the local map, the user can progressively express the desired information need by selecting relevant texts and/or images and discarding negative examples, in a flexible manner. In the case of the present multimodal feedback technique, 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 locality factor allows 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 achievement of 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 the user to decrease the importance of texts and images with different rates, which is particularly useful in the example scenario.

[0104] It will be appreciated that various of the above-disclosed and other features and functions, or alternatives thereof, may be desirably combined into many other different systems or applications. Also that various presently unforeseen or unanticipated alternatives, modifications, variations or improvements therein may be subsequently made by those skilled in the art which are also intended to be encompassed by the following claims.