Les ontologies offrent une modélisation des connaissances d'un domaine basée sur une hiérarchie des concepts clefs de ce domaine. Leur utilisation dans le cadre des Systèmes de Recherche d'Information (SRI), tant pour indexer les documents que pour exprimer une requête, permet notamment d'éviter les ambiguïtés du langage naturel qui pénalisent les SRI classiques. Les travaux de cette thèse portent essentiellement sur l'utilisation d'ontologies lors du processus d'appariement durant lequel les SRI ordonnent les documents d'une collection en fonction de leur pertinence par rapport à une requête utilisateur. Nous proposons de calculer cette pertinence à l'aide d'une stratégie d'agrégation de scores élémentaires entre chaque document et chaque concept de la requête. Cette agrégation, simple et intuitive, intègre un modèle de préférences dépendant de l'utilisateur et une mesure de similarité sémantique associée à l'ontologie. L'intérêt majeur de cette approche est qu'elle permet d'expliquer à l'utilisateur pourquoi notre SRI, OBIRS, estime que les documents qu'il a sélectionnés sont pertinents. Nous proposons de renforcer cette justification grâce à une visualisation originale où les résultats sont représentés par des pictogrammes, résumant leurs pertinences élémentaires, puis disposés sur une carte sémantique en fonction de leur pertinence globale. La Recherche d'Information étant un processus itératif, il est nécessaire de permettre à l'utilisateur d'interagir avec le SRI, de comprendre et d'évaluer les résultats et de le guider dans sa reformulation de requête. Nous proposons une stratégie de reformulation de requêtes conceptuelles basée sur la transposition d'une méthode éprouvée dans le cadre de SRI vectoriels. La reformulation devient alors un problème d'optimisation utilisant les retours faits par l'utilisateur sur les premiers résultats proposés comme base d'apprentissage. Nous avons développé une heuristique permettant de s'approcher d'une requête optimale en ne testant qu'un sous-espace des requêtes conceptuelles possibles. Nous montrons que l'identification efficace des concepts de ce sous-espace découle de deux propriétés qu'une grande partie des mesures de similarité sémantique vérifient, et qui suffisent à garantir la connexité du voisinage sémantique d'un concept.Les modèles que nous proposons sont validés tant sur la base de performances obtenues sur des jeux de tests standards, que sur la base de cas d'études impliquant des experts biologistes. / Domain ontologies provide a knowledge model where the main concepts of a domain are organized through hierarchical relationships. In conceptual Information Retrieval Systems (IRS), where they are used to index documents as well as to formulate a query, their use allows to overcome some ambiguities of classical IRSs based on natural language processes.One of the contributions of this study consists in the use of ontologies within IRSs, in particular to assess the relevance of documents with respect to a given query. For this matching process, a simple and intuitive aggregation approach is proposed, that incorporates user dependent preferences model on one hand, and semantic similarity measures attached to a domain ontology on the other hand. This matching strategy allows justifying the relevance of the results to the user. To complete this explanation, semantic maps are built, to help the user to grasp the results at a glance. Documents are displayed as icons that detail their elementary scores. They are organized so that their graphical distance on the map reflects their relevance to a query represented as a probe. As Information Retrieval is an iterative process, it is necessary to involve the users in the control loop of the results relevancy in order to better specify their information needs. Inspired by experienced strategies in vector models, we propose, in the context of conceptual IRS, to formalize ontology based relevance feedback. This strategy consists in searching a conceptual query that optimizes a tradeoff between relevant documents closeness and irrelevant documents remoteness, modeled through an objective function. From a set of concepts of interest, a heuristic is proposed that efficiently builds a near optimal query. This heuristic relies on two simple properties of semantic similarities that are proved to ensure semantic neighborhood connectivity. Hence, only an excerpt of the ontology dag structure is explored during query reformulation.These approaches have been implemented in OBIRS, our ontological based IRS and validated in two ways: automatic assessment based on standard collections of tests, and case studies involving experts from biomedical domain.

Relevance is an essential concept in information retrieval (IR) and relevance estimation is a fundamental IR task. It involves not only document relevance estimation, but also estimation of user's information need. Relevance-based language model aims to estimate a relevance model (i.e., a relevant query term distribution) from relevance feedback documents. The true relevance model should be generated from truly relevant documents. The ideal estimation of the true relevance model is expected to be not only effective in terms of mean retrieval performance (e.g., Mean Average Precision) over all the queries, but also stable in the sense that the performance is stable across different individual queries. In practice, however, in approximating/estimating the true relevance model, the improvement of retrieval effectiveness often sacrifices the retrieval stability, and vice versa. In this thesis, we propose to explore and analyze such effectiveness-stability tradeoff from a new perspective, i.e., the bias-variance tradeoff that is a fundamental theory in statistical estimation. We first formulate the bias, variance and the trade-off between them for retrieval performance as well as for query model estimation. We then analytically and empirically study a number of factors (e.g., query model complexity, query model combination, document weight smoothness and irrelevant documents removal) that can affect the bias and variance. Our study shows that the proposed bias-variance trade-off analysis can serve as an analytical framework for query model estimation. We then investigate in depth on two particular key factors: document weight smoothness and removal of irrelevant documents, in query model estimation, by proposing novel methods for document weight smoothing and irrelevance distribution separation, respectively. Systematic experimental evaluation on TREC collections shows that the proposed methods can improve both retrieval effectiveness and retrieval stability of query model estimation. In addition to the above main contributions, we also carry out initial exploration on two further directions: the formulation of bias-variance in personalization and looking at the query model estimation via a novel theoretical angle (i.e., Quantum theory) that has partially inspired our research.

This thesis compares four relevance feedback methods. The Rocchio and Ide dec-hi algorithms for the vector space model and the binary independence model and Okapi BM25 within the probabilistic framework. This is done in a custom-made Information Retrieval system utilizing a collection containing 131 896 LA-Times articles which is part of the TREC ad-hoc collection. The methods are compared on two grounds, using only the relevance information from the 20 highest ranked documents from an initial search and also by using all available relevance information. Although a significant effect of choice of method could be found on the first ground, post-hoc analysis could not determine any statistically significant differences between the methods where Rocchio, Ide dec-hi and Okapi BM25 performed equivalent. All methods except the binary independence model performed significantly better than using no relevance feedback. It was also revealed that although the binary independence model performed far worse on average than the other methods it did outperform them on nearly 20 % of the topics. Further analysis argued that this depends on the lack of query expansion in the binary independence model which is advantageous for some topics although has a negative effect on retrieval efficiency in general. On the second ground Okapi BM25 performed significantly better than the other methods with the binary independence model once again being the worst performer. It was argued that the other methods have problems scaling to large amounts of relevance information where Okapi BM25 has no such issues. / Uppsatsnivå: D

Les systèmes de recherche d'information ont pour fonction de permettre à l'utilisateur d'accéder à des documents qui contribuent à résoudre le problème d'information qui motive sa recherche. Ainsi le système peut être vu comme un instrument de prédiction de la pertinence des documents du corpus pour l'utilisateur. Les indices traditionnellement utilisés par le système pour estimer cette pertinence sont de nature thématique, et sont fournis par l'utilisateur sous la forme d'un ensemble de mots-clés : la requête. Le système implémente donc une fonction de correspondance entre documents et requête qui modélise la dimension thématique de la pertinence. Cependant l'éventail des utilisations et des utilisateurs des systèmes va s'élargissant, de même que la nature des documents présents dans les corpus, qui ne sont plus seulement des documents textuels. Nous tirons deux conséquences de cette évolution. D'une part, l'hypothèse que le facteur thématique de pertinence est prépondérant (et donc seul sujet à modélisation dans les systèmes), ne tient plus. Les autres facteurs, nombreux, de la pertinence interviennent d'une manière telle qu'ils compromettent les performances des systèmes dans le contexte d'une utilisation réelle. Ces autres facteurs dépendent fortement de l'individu et de sa situation de recherche d'information, ce qui remet en cause la conception de la pertinence système comme une fonction de correspondance qui ne prend en compte que les facteurs de la pertinence qui ne dépendent pas de l'utilisateur. D'autre part, la nature de l'utilisation interactive du système contribue à définir la situation de recherche de l'utilisateur, et en cela participe aux performances du système de recherche d'information. Un certain nombre de caractéristiques de l'interaction sont directement liées à la modélisation de la pertinence système et à des préoccupations spécifiques à la problématique de la recherche d'information. Notre thèse s'appuie sur les travaux réalisés sur les facteurs de la pertinence pour un individu, pour définir un modèle de conception de la pertinence système qui prend en compte les facteurs qui relèvent de l'utilisation interactive du système et de la nécessité d'adaptation de la fonction de correspondance à la situation de recherche particulière dans laquelle l'utilisateur se trouve. Ainsi, nous définissons trois nouvelles fonctions du système de recherche d'information, en termes d'utilisation du système : permettre la détection de la pertinence des documents retrouvés, permettre la compréhension des raisons de leur pertinence système, et permettre de procéder à une reformulation du problème d'information dans le cadre d'un processus itératif de recherche. La notion de schéma de pertinence se substitue à celle de requête, en tant qu'interface entre la pertinence système et l'utilisateur. Ce schéma de pertinence intègre deux types de paramètres permettant l'adaptation du système à la situation de recherche : d'une part les paramètres sémantiques, qui recouvrent non seulement la dimension thématique de la pertinence mais aussi d'autres critères de pertinence liés aux caractéristiques indexées des documents, et d'autre part les paramètres pragmatiques qui prennent en compte les facteurs de la pertinence liés aux conditions dans lesquelles l'utilisateur réalise les tâches qui lui incombent dans l'interaction. Nous appliquons ce modèle de conception de la pertinence système dans le cadre d'une application de recherche d'images, dont le corpus est indexé de façon à couvrir plusieurs dimensions de la pertinence outre la dimension thématique. Notre prototype nous permet de montrer comment le système s'adapte en fonction des situations qui se présentent au cours d'une session de recherche.

The increasing ubiquity of networked mobile devices such as cell phones and PDAs has created new opportunities for the transmission and display of multimedia content. However, any mobile device has inherent resource constraints: low network bandwidth, small screen sizes, limited input methods, and low commitment viewing. Mobile systems that provide information display and access thus need to mitigate these various constraints. Despite progress in information retrieval and content recommendation, there has been less focus on issues arising from a network-oriented and mobile perspective. This dissertation investigates a coordinated design approach to networked multimedia on mobile devices, and considers the abovementioned system perspectives. Within the context of accessing news video on mobile devices, the goal is to provide a cognitively palatable stream of videos and a seamless, low-latency user experience. Mixed-initiative---a method whereby intelligent services and users collaborate efficiently to achieve the user's goals, is the cornerstone of the system design and integrates user relevance feedback with a content recommendation engine and a content- and network-aware video buffer prefetching technique. These various components have otherwise been considered independently in other prior system designs. To overcome limited interactivity, a mixed-initiative user interface was used to present a sequence of news video clips to the user, along with operations to vote-up or vote-down a video to indicate its relevance. On-screen gesture equivalents of these operations were also implemented to reduce user interface elements occupying the screen. Semantic relevancy was then improved by extracting and indexing the content of each video clip as text features, and using a Na"ive Bayesian content recommendation strategy that harnessed the user relevance feedback to tailor the subsequent video recommendations. With the system's knowledge of relevant videos, a content-aware video buffer prefetching scheme was then integrated, using the abovementioned feedback to lower the user perceived latency on the client-end. As an information retrieval system consists of many interacting components, a client-server video streaming model is first developed for clarity and simplicity. Using a CNN news video clip database, experiments were then conducted using this model to simulate user scenarios. As the aim of improving semantic relevancy sometimes opposes user interface tools for interactivity and user perceived latency, a quantitative evaluation was done to observe the tradeoffs between bandwidth, semantic relevance, and user perceived latency. Performance tradeoffs involving semantic relevancy and user perceived latency were then predicted. In addition, complementary human user subjective tests are conducted with actual mobile phone hardware running on the Google Android platform. These experiments suggest that a mixed-initiative approach is helpful for recommending news video content on a mobile device for overcoming the mobile limitations of user interface tools for interactivity and client-end perceived latency. Users desired interactivity and responsiveness while viewing videos, and were willing to sacrifice some content relevancy in order gain lower perceived latency. Recommended future work includes expanding the content recommendation to incorporate viewing data from a large population, and the creation of a global hybrid content-based and collaborative filtering algorithm for better results. Also, based on existing user behaviour, users were reluctant to provide more input than necessary. Additional user experiments can be designed to quantify user attention and interest during video watching on a mobile device, and for better definition and incorporation of implicit user feedback.

傳統的音樂檢索系統主要在提供使用者特定音樂的查詢(target search)。除此之外，使用者也有類型音樂查詢(category search)的需求。在類型音樂查詢中，該類型的所有音都共同具備使用者所定義的概念(semantic concept)。這個由使用者定義的概念在音樂檢索系統上是主觀的且動態產生的。換句話說，同一使用者在不同情境之下對於同一首音樂可能產生不同的解讀概念。為了動態擷取使用者的概念，讓使用者參與在查詢過程的互動機制是必要的。因此， 我們提出將相關回饋(relevance feedback)的機制運用在以內容為主的音樂查詢系統上，讓系統從使用者的相關回饋中學習使用者的概念，並利用這學習出的概念來幫助音樂查詢。 由於使用者可能從整首音樂或音樂片段兩種角度來判斷該音樂是否具備使用者定義的概念。因此，本論文提出用以片段為主的音樂模型(segment-based modeling approach)將音樂表示成音樂片段的集合。進一步再從整首音樂和片段中擷取特徵。 其次，我們針對該問題提出相關演算法來探勘使用者的概念。該演算法先從相關和不相關的音樂資料庫中個別探勘常見樣式，再利用這些樣式建立分類器以區分音樂的相關性。 最後，我們分析各種系統回饋機制對搜尋效果的影響。Most-positive回傳機制會選擇根據目前系統判斷為最相關的物件。Most-informative機制則是回傳系統無法判斷其相關性的音樂物件。Most-informative 機制的目的在增加每回合系統從使用者身上得到的資訊量。Hybrid 則是中和前兩種機制的優點。本文中，我們模擬並比較各種回傳機制的效能。實驗結果顯示相關回饋機制確實能提升查詢的效果。 / Traditional content-based music retrieval system retrieves a specific music object which is similar to the user’s query. There is also a need, category search, for retrieving a specific category of music objects. In category search, music objects of the same category share a common semantic concept which is defined by the user. The concept for category search in music retrieval is subjective and dynamic. Different users at different time may have different interpretations for the same music object. In the music retrieval system along with relevance feedback mechanism, users are expected to be involved in the concept learning process. Relevance feedback enables the system to learn user’s concept dynamically. In this paper, the relevance feedback mechanism for category search of music retrieval based on the semantic concept learning is investigated. We proposed a segment-based music representation to assist the system in discovering user’s concept in terms of low-level music features. Each music object is modeled as a set of significant motivic patterns (SMP) achieved by discovering motivic repeating pattern. Both global and local music features are considered in concept learning. Moreover, to discover user’s semantic concept, a two-phase frequent pattern mining algorithm is proposed to discover common properties from relevant and irrelevant objects respectively and based on which a classifier is derived for distinguishing music objects. Except user’s feedback, three strategies of the system’s feedback to select objects for user’s relevance judgment are investigated. Most-positive strategy returns the most relevant music object to the user while most-informative strategy returns the most uncertain music objects for improving the discrimination power of the next round. Hybrid feedback strategy returns both of them. Comparative experiments are conducted to evaluate effectiveness of the proposed relevance feedback mechanism. Experimental results show that a better precision can be achieved via proposed relevance feedback mechanism.

In content-based image retrieval (CBIR) systems, there are two general types of search: target search and category search. Unlike queries in traditional database systems, users in most cases cannot specify an ideal query to retrieve the desired results for either target search or category search in multimedia database systems, and have to rely on iterative feedback to refine their query. Efficient evaluation of such iterative queries can be a challenge, especially when the multimedia database contains a large number of entries, and the search needs many iterations, and when the underlying distance measure is computationally expensive. The overall processing costs, including CPU and disk I/O, are further emphasized if there are numerous concurrent accesses. To address these limitations involved in relevance feedback processing, we propose a generic framework, including a query model, index structures, and query optimization techniques. Specifically, this thesis has five main contributions as follows. The first contribution is an efficient target search technique. We propose four target search methods: naive random scan (NRS), local neighboring movement (LNM), neighboring divide-and-conquer (NDC), and global divide-and-conquer (GDC) methods. All these methods are built around a common strategy: they do not retrieve checked images (i.e., shrink the search space). Furthermore, NDC and GDC exploit Voronoi diagrams to aggressively prune the search space and move towards target images. We theoretically and experimentally prove that the convergence speeds of GDC and NDC are much faster than those of NRS and recent methods. The second contribution is a method to reduce the number of expensive distance computation when answering k-NN queries with non-metric distance measures. We propose an efficient distance mapping function that transfers non-metric measures into metric, and still preserves the original distance orderings. Then existing metric index structures (e.g., M-tree) can be used to reduce the computational cost by exploiting the triangular inequality property. The third contribution is an incremental query processing technique for Support Vector Machines (SVMs). SVMs have been widely used in multimedia retrieval to learn a concept in order to find the best matches. SVMs, however, suffer from the scalability problem associated with larger database sizes. To address this limitation, we propose an efficient query evaluation technique by employing incremental update. The proposed technique also takes advantage of a tuned index structure to efficiently prune irrelevant data. As a result, only a small portion of the data set needs to be accessed for query processing. This index structure also provides an inexpensive means to process the set of candidates to evaluate the final query result. This technique can work with different kernel functions and kernel parameters. The fourth contribution is a method to avoid local optimum traps. Existing CBIR systems, designed around query refinement based on relevance feedback, suffer from local optimum traps that may severely impair the overall retrieval performance. We therefore propose a simulated annealing-based approach to address this important issue. When a stuck-at-a-local-optimum occurs, we employ a neighborhood search technique (i.e., simulated annealing) to continue the search for additional matching images, thus escaping from the local optimum. We also propose an index structure to speed up such neighborhood search. Finally, the fifth contribution is a generic framework to support concurrent accesses. We develop new storage and query processing techniques to exploit sequential access and leverage inter-query concurrency to share computation. Our experimental results, based on the Corel dataset, indicate that the proposed optimization can significantly reduce average response time while achieving better precision and recall, and is scalable to support a large user community. This latter performance characteristic is largely neglected in existing systems making them less suitable for large-scale deployment. With the growing interest in Internet-scale image search applications, our framework offers an effective solution to the scalability problem.

No description available.

Dans le cadre d’une solution de modification de la requête, nous nous intéressons aux différentes façons d’utiliser la sémantique pour mieux exprimer le besoin d’information de l’utilisateur dans un contexte Web. Nous distinguons deux types de concepts : ceux identifiables dans une ressource sémantique comme une ontologie, et ceux que l’on extrait à partir d’un ensemble de documents de pseudo retour de pertinence. Nous proposons une Approche Sémantique Mixte d’Expansion et de Reformulation (ASMER) qui permet de modéliser l’utilisation de ces deux types de concepts dans une requête modifiée. Cette approche considère plusieurs défis liés à la modification automatique des requêtes, notamment le choix sélectif des termes d’expansion, le traitement des entités nommées et la reformulation de la requête finale.Bien que dans un contexte Web la précision soit le critère d’évaluation le plus adapté, nous avons aussi pris en compte le rappel pour étudier le comportement de notre approche sous plusieurs aspects. Ce choix a suscité une autre problématique liée à l’évaluation du rappel en recherche d’information. En constatant que les mesures précédentes ne répondent pas à nos contraintes, nous avons proposé la mesure MOR (Mesure Orientée Rappel), qui permet d’évaluer le rappel en tenant compte de la précision comme importante mais pas prioritaire dans un contexte dirigé rappel.En incluant MOR dans notre stratégie de test, nous avons évalué ASMER sur quatre collections Web issues des campagnes INEX et TREC. Nos expériences montrent qu’ASMER améliore la performance en précision par rapport aux requêtes originales et par rapport aux requêtes étendues par une méthode de l’état de l’art. / As a query expansion and reformulation solution, we are interested in the different ways the semantic could be used to translate users information need into a query. We define two types of concepts : those which we can identify in a semantic resource like an ontology, and the ones we extract from the collection of documents via pseudo relevance feedback procedure. We propose a semantic and mixed approach to query expansion and reformulation (ASMER) that allows to integrate these two types of concepts in an automatically modified query. Our approach considers many challenges, especially selective terms expansion, named entity treatment and query reformulation.Even though the precision is the evaluation criteria the most adapted to a web context, we also considered evaluating the recall to study the behavior of our model from different aspects. This choice led us to handle a different problem related to evaluating the recall in information retrieval. After realizing that actual measures don't satisfy our constraints, we proposed a new recall oriented measure (MOR) which considers the recall as a priority without ignoring the precision.Among other measures, MOR was considered to evaluate our approach ASMER on four web collection from the standard evaluation campaigns Inex and Trec. Our experiments showed that ASMER improves the precision of the non modified original queries. In most cases, our approach achieved statistically significant enhancements when compared to a state of the art query expansion method. In addition, ASMER retrieves the first relevant document in better ranks than the compared approaches, it also has slightly better recall according to the measure MOR.

O problema da descontinuidade semântica tem sido um dos principais focos de pesquisa no desenvolvimento de sistemas de recuperação de imagens baseada em conteúdo (CBIR). Neste contexto, as pesquisas mais promissoras focam principalmente na inferência de pesos de características contínuos e na seleção de características. Entretanto, os processos tradicionais de inferência de pesos contínuos são computacionalmente caros e a seleção de características equivale a uma ponderação binária. Visando tratar adequadamente o problema de lacuna semântica, este trabalho propõe dois métodos de transformação de espaço de características métricos baseados na inferência de funções de transformação por meio de algoritmo genético. O método WF infere funções de ponderação para ajustar a função de dissimilaridade e o método TF infere funções para transformação das características. Comparados às abordagens de inferência de pesos contínuos da literatura, ambos os métodos propostos proporcionam uma redução drástica do espaço de busca ao limitar a busca à escolha de um conjunto ordenado de funções de transformação. Análises visuais do espaço transformado e de gráficos de precisão vs. revocação confirmam que TF e WF superam a abordagem tradicional de ponderação de características. Adicionalmente, foi verificado que TF supera significativamente WF em termos de precisão dos resultados de consultas por similaridade por permitir transformação não lineares no espaço de característica, conforme constatado por análise visual. / The semantic gap problem has been a major focus of research in the development of content-based image retrieval (CBIR) systems. In this context, the most promising research focus primarily on the inference of continuous feature weights and feature selection. However, the traditional processes of continuous feature weighting are computationally expensive and feature selection is equivalent to a binary weighting. Aiming at alleviating the semantic gap problem, this master dissertation proposes two methods for the transformation of metric feature spaces based on the inference of transformation functions using Genetic Algorithms. The WF method infers weighting functions and the TF method infers transformation functions for the features. Compared to the existing methods, both proposed methods provide a drastic searching space reduction by limiting the search to the choice of an ordered set of transformation functions. Visual analysis of the transformed space and precision. vs. recall graphics confirm that both TF and WF outperform the traditional feature eighting methods. Additionally, we found that TF method significantly outperforms WF regarding the query similarity accuracy by performing non linear feature space transformation, as found in the visual analysis.