Search

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.

Abstract: In the face of an overwhelmingly information intensive Internet, searching has become the most important way to locate information efficiently. Current searching techniques are able to retrieve relevant data, however, personalization techniques are still needed to better identify different user requirements. This thesis proposes an interactive and iterative approach to infer a user's intentions implicitly, and adapt to changing user requirements. We gather relevance feedback from the user, and classify items in the query result set into different groups based on the feedback for each item. We rerank the original result set according to the user's interest towards each group. The group of the user's interest is ranked higher. We illustrate the approach using a personalized academic paper searching application and evaluate it with real users. The experimental results show improvements after applying our approach. The system design is extensible and potentially applicable to other search domains.

An image retrieval system needs to be able to communicate with people using a common language, if it is to serve its user's information need. I propose techniques for interactive image search with the help of visual attributes, which are high-level semantic visual properties of objects (like "shiny" or "natural"), and are understandable by both people and machines. My thesis explores attributes as a novel form of user input for search. I show how to use attributes to provide relevance feedback for image search; how to optimally choose what to seek feedback on; how to ensure that the attribute models learned by a system align with the user's perception of these attributes; how to automatically discover the shades of meaning that users employ when applying an attribute term; and how attributes can help learn object category models. I use attributes to provide a channel on which the user of an image retrieval system can communicate her information need precisely and with as little effort as possible. One-shot retrieval is generally insufficient, so interactive retrieval systems seek feedback from the user on the currently retrieved results, and adapt their relevance ranking function accordingly. In traditional interactive search, users mark some images as "relevant" and others as "irrelevant", but this form of feedback is limited. I propose a novel mode of feedback where a user directly describes how high-level properties of retrieved images should be adjusted in order to more closely match her envisioned target images, using relative attribute feedback statements. For example, when conducting a query on a shopping website, the user might state: "I want shoes like these, but more formal." I demonstrate that relative attribute feedback is more powerful than traditional binary feedback. The images believed to be most relevant need not be most informative for reducing the system's uncertainty, so it might be beneficial to seek feedback on something other than the top-ranked images. I propose to guide the user through a coarse-to-fine search using a relative attribute image representation. At each iteration of feedback, the user provides a visual comparison between the attribute in her envisioned target and a "pivot" exemplar, where a pivot separates all database images into two balanced sets. The system actively determines along which of multiple such attributes the user's comparison should next be requested, based on the expected information gain that would result. The proposed attribute search trees allow us to limit the scan for candidate images on which to seek feedback to just one image per attribute, so it is efficient both for the system and the user. No matter what potentially powerful form of feedback the system offers the user, search efficiency will suffer if there is noise on the communication channel between the user and the system. Therefore, I also study ways to capture the user's true perception of the attribute vocabulary used in the search. In existing work, the underlying assumption is that an image has a single "true" label for each attribute that objective viewers could agree upon. However, multiple objective viewers frequently have slightly different internal models of a visual property. I pose user-specific attribute learning as an adaptation problem in which the system leverages any commonalities in perception to learn a generic prediction function. Then, it uses a small number of user-labeled examples to adapt that model into a user-specific prediction function. To further lighten the labeling load, I introduce two ways to extrapolate beyond the labels explicitly provided by a given user. While users differ in how they use the attribute vocabulary, there exist some commonalities and groupings of users around their attribute interpretations. Automatically discovering and exploiting these groupings can help the system learn more robust personalized models. I propose an approach to discover the latent factors behind how users label images with the presence or absence of a given attribute, from a sparse label matrix. I then show how to cluster users in this latent space to expose the underlying "shades of meaning" of the attribute, and subsequently learn personalized models for these user groups. Discovering the shades of meaning also serves to disambiguate attribute terms and expand a core attribute vocabulary with finer-grained attributes. Finally, I show how attributes can help learn object categories faster. I develop an active learning framework where the computer vision learning system actively solicits annotations from a pool of both object category labels and the objects' shared attributes, depending on which will most reduce total uncertainty for multi-class object predictions in the joint object-attribute model. Knowledge of an attribute's presence in an image can immediately influence many object models, since attributes are by definition shared across subsets of the object categories. The resulting object category models can be used when the user initiates a search via keywords such as "Show me images of cats" and then (optionally) refines that search with the attribute-based interactions I propose. My thesis exploits properties of visual attributes that allow search to be both effective and efficient, in terms of both user time and computation time. Further, I show how the search experience for each individual user can be improved, by modeling how she uses attributes to communicate with the retrieval system. I focus on the modes in which an image retrieval system communicates with its users by integrating the computer vision perspective and the information retrieval perspective to image search, so the techniques I propose are a promising step in closing the semantic gap.

Videos on the Internet have become widespread. However search engines are still mostly limited to using associated text data to find desired content. In this dissertation, we build ranking functions that can directly analyze image and video content and assign a ranking to a database with respect to user queries.A common approach to building ranking functions is to use a machine learning algorithm to perform a priori training of class concepts and use the trained classifier as the ranking function. However, a priori training of class concepts for retrieval is daunting since users queries can be very diverse. In addition, a priori training cannot capture the subjective component of user queries. For example, if a user were searching for videos of ``nice basketball shots,'' there would be no way to know what the user considers ``nice.'' Relevance feedback (RF) is an interactive search framework that captures user subjectivity and supports on-the-fly learning of target classes.However, RF is limited in its need for large amounts of user feedback when the data being searched are complex (e.g. Internet content). Transfer learning (TL) is a machine learning formulation where existing knowledge about a related ``source'' classification task can be used to improve the generalization performance of a ``target'' task (where training data is scarce). In this dissertation we explore the combination of RF and TL and present a framework which can learn more from the user with less feedback. We show extensive experiments with real-world data taken from the Internet and show improved performance over past RF frameworks.Although our RF and TL framework is effective for a wide range of queries, we acknowledge that there are some highly specific but common queries users could make which would benefit from more dedicated design of a ranking function. For example, finding particular people using face recognition would be an important type of query on the Internet. The problem in this case is well defined and objective. While the problem is specific, it is important enough to warrant the dedicated design of a ranking function. Thus we complete our studies in this dissertation through the exploration of a robust face recognition based ranking function and show strong results in a challenging face identity retrieval task.

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.

This dissertation explores two types of applications of applied statistics techniques to develop methods associated with bioinformatics and information retrieval. The first type relates to planning probably the most common type of genetics related experiment, i.e., co-hybridized microarray testing. The question addressed concerns how to deploy the samples to slides and select dye colors to improve the sensitivity and specificity without increasing the associated cost. A generalized A-optimality criterion called the expected squared errors of coefficient estimates (ESECE) is proposed to aid in experimental design selection. The proposed criterion also can be applied to any type of experimentation focused on parameter estimation. Heuristic methods to generate arrays using the proposed criterion are also suggested. The resulting “hybrid” designs constitute a compromise between the widely used “reference” designs and the “loop” designs. The proposed criterion and a study of 15,488 genes together suggest that reference designs are generally likely to foster more accurate estimation than loop designs. Also, the proposed “hybrid” designs likely offer further benefits in increased sensitivity and specificity with no added costs. The second type of application explored is the design of vector space search engines, which constitute perhaps the most common type of search technology in information retrieval. In this dissertation, two types of methods are explored separately and also combined to tune the selection of weights of the similarity distance function so that the search engine generates results of greater interest to users. The first type is so-called discrete choice analysis (DCA) methods to estimate the weights that putatively maximize the expected utility of users in the context of specific queries. The second type of method is the application of mixture modeling. Based on the fitting of specific types of mixture regression models, methods are proposed to enhance the expected user utility for a variety of queries. The DCA methods are illustrated using a news database and simulated users. The associated test problems provide an indication that the proposed methods could improve performance compared with the common strategy of applying equal weights for all semantic dimensions.