Learning Embeddings for Indexing, Retrieval, and Classification, with Applications to Object and Shape Recognition in Image Databases

Nearest neighbor retrieval is the task of identifying, given a database of objects and a query object, the objects in the database that are the most similar to the query. Retrieving nearest neighbors is a necessary component of many practical applications, in fields as diverse as computer vision, pattern recognition, multimedia databases, bioinformatics, and computer networks. At the same time, finding nearest neighbors accurately and efficiently can be challenging, especially when the database contains a large number of objects, and when the underlying distance measure is computationally expensive. This thesis proposes new methods for improving the efficiency and accuracy of nearest neighbor retrieval and classification in spaces with computationally expensive distance measures. The proposed methods are domain-independent, and can be applied in arbitrary spaces, including non-Euclidean and non-metric spaces. In this thesis particular emphasis is given to computer vision applications related to object and shape recognition, where expensive non-Euclidean distance measures are often needed to achieve high accuracy. The first contribution of this thesis is the BoostMap algorithm for embedding arbitrary spaces into a vector space with a computationally efficient distance measure. Using this approach, an approximate set of nearest neighbors can be retrieved efficiently - often orders of magnitude faster than retrieval using the exact distance measure in the original space. The BoostMap algorithm has two key distinguishing features with respect to existing embedding methods. First, embedding construction explicitly maximizes the amount of nearest neighbor information preserved by the embedding. Second, embedding construction is treated as a machine learning problem, in contrast to existing methods that are based on geometric considerations. The second contribution is a method for constructing query-sensitive distance measures for the purposes of nearest neighbor retrieval and classification. In high-dimensional spaces, query-sensitive distance measures allow for automatic selection of the dimensions that are the most informative for each specific query object. It is shown theoretically and experimentally that query-sensitivity increases the modeling power of embeddings, allowing embeddings to capture a larger amount of the nearest neighbor structure of the original space. The third contribution is a method for speeding up nearest neighbor classification by combining multiple embedding-based nearest neighbor classifiers in a cascade. In a cascade, computationally efficient classifiers are used to quickly classify easy cases, and classifiers that are more computationally expensive and also more accurate are only applied to objects that are harder to classify. An interesting property of the proposed cascade method is that, under certain conditions, classification time actually decreases as the size of the database increases, a behavior that is in stark contrast to the behavior of typical nearest neighbor classification systems. The proposed methods are evaluated experimentally in several different applications: hand shape recognition, off-line character recognition, online character recognition, and efficient retrieval of time series. In all datasets, the proposed methods lead to significant improvements in accuracy and efficiency compared to existing state-of-the-art methods. In some datasets, the general-purpose methods introduced in this thesis even outperform domain-specific methods that have been custom-designed for such datasets.

Clustered indexing for branch predictors

As a result of resource limitations, state in branch predictors is frequently shared between uncorrelated branches. This interference can significantly limit prediction accuracy. In current predictor designs, the branches sharing prediction information are determined by their branch addresses and thus branch groups are arbitrarily chosen during compilation. This feasibility study explores a more analytic and systematic approach to classify branches into clusters with similar behavioral characteristics. We present several ways to incorporate this cluster information as an additional information source in branch predictors.

Enhanced approach for latent semantic indexing using wavelet transform

Latent semantic indexing (LSI) is a technique used for intelligent information retrieval (IR). It can be used as an alternative to traditional keyword matching IR and is attractive in this respect because of its ability to overcome problems with synonymy and polysemy. This study investigates various aspects of LSI: the effect of the Haar wavelet transform (HWT) as a preprocessing step for the singular value decomposition (SVD) in the key stage of the LSI process; and the effect of different threshold types in the HWT on the search results. The developed method allows the visualisation and processing of the term document matrix, generated in the LSI process, using HWT. The results have shown that precision can be increased by applying the HWT as a preprocessing step, with better results for hard thresholding than soft thresholding, whereas standard SVD-based LSI remains the most effective way of searching in terms of recall value.

Accuracy of medical subject heading indexing of dental survival analyses

PURPOSE: To assess the Medical Subject Headings (MeSH) indexing of articles that employed time-to-event analyses to report outcomes of dental treatment in patients.

MATERIALS AND METHODS: Articles published in 2008 in 50 dental journals with the highest impact factors were hand searched to identify articles reporting dental treatment outcomes over time in human subjects with time-to-event statistics (included, n = 95), without time-to-event statistics (active controls, n = 91), and all other articles (passive controls, n = 6,769). The search was systematic (kappa 0.92 for screening, 0.86 for eligibility). Outcome-, statistic- and time-related MeSH were identified, and differences in allocation between groups were analyzed with chi-square and Fischer exact statistics.

RESULTS: The most frequently allocated MeSH for included and active control articles were "dental restoration failure" (77% and 52%, respectively) and "treatment outcome" (54% and 48%, respectively). Outcome MeSH was similar between these groups (86% and 77%, respectively) and significantly greater than passive controls (10%, P < .001). Significantly more statistical MeSH were allocated to the included articles than to the active or passive controls (67%, 15%, and 1%, respectively, P < .001). Sixty-nine included articles specifically used Kaplan-Meier or life table analyses, but only 42% (n = 29) were indexed as such. Significantly more time-related MeSH were allocated to the included than the active controls (92% and 79%, respectively, P = .02), or to the passive controls (22%, P < .001).

CONCLUSIONS: MeSH allocation within MEDLINE to time-to-event dental articles was inaccurate and inconsistent. Statistical MeSH were omitted from 30% of the included articles and incorrectly allocated to 15% of active controls. Such errors adversely impact search accuracy.

Indexing and matching trajectories under inconsistent sampling rates

Quantifying the similarity between two trajectories is a fundamental operation in analysis of spatio-temporal databases. While a number of distance functions exist, the recent shift in the dynamics of the trajectory generation procedure violates one of their core assumptions; a consistent and uniform sampling rate. In this paper, we formulate a robust distance function called Edit Distance with Projections (EDwP) to match trajectories under inconsistent and variable sampling rates through dynamic interpolation. This is achieved by deploying the idea of projections that goes beyond matching only the sampled points while aligning trajectories. To enable efficient trajectory retrievals using EDwP, we design an index structure called TrajTree. TrajTree derives its pruning power by employing the unique combination of bounding boxes with Lipschitz embedding. Extensive experiments on real trajectory databases demonstrate EDwP to be up to 5 times more accurate than the state-of-the-art distance functions. Additionally, TrajTree increases the efficiency of trajectory retrievals by up to an order of magnitude over existing techniques.

The relationship between rapid automatized naming and reading performance: a meta-analysis

O estudo científico dos correlatos cognitivos da aquisição e desenvolvimento da competência de leitura é um assunto de grande relevância quer teórica quer prática, no sentido em que pode ajudar a compreender os processos cognitivos básicos envolvidos na leitura e, em última instância, a delinear os seus preditores e a predizer dificuldades na sua aquisição. A par da consciência fonológica – capacidade para perceber e manipular as unidades de som –, um dos construtos que frequentemente tem sido associado ao desenvolvimento da competência de leitura é a velocidade de nomeação de estímulos visuais (também conhecida como nomeação rápida automatizada ou velocidade de acesso ao léxico). Tradicionalmente, esta capacidade tem sido avaliada recorrendo ao paradigma clássico das provas de nomeação rápida automatizada (RAN) desenvolvidas por Denckla e Rudel (1976), nas quais é pedido ao sujeito que nomeie o mais rapidamente possível um conjunto de estímulos familiares apresentados serialmente. Nas últimas décadas, inúmeros estudos vieram demonstrar que a nomeação rápida é um importante preditor da competência de leitura, sobretudo da fluência da leitura, e um défice central em perturbações de leitura como a dislexia. O desempenho numa tarefa de nomeação rápida apela à sincronização e integração de vários processos, incluindo: (a) atenção ao estímulo, (b) integração da informação visual com representações visuais ou ortográficas arquivadas em memória, (c) recuperação de uma etiqueta verbal, e a (d) ativação da representação articulatória (Wolf & Bowers, 1999). Uma vez que a leitura e a nomeação rápida envolvem processos cognitivos semelhantes, não parece surpreendente que ambas as competências estejam associadas. No entanto, os estudos têm variado consideravelmente no que respeita à magnitude da associação entre a nomeação rápida e a leitura, encontrando-se resultados nulos ou negligenciáveis do valor preditivo da nomeação rápida na explicação da variância do desempenho de leitura. Vários fatores podem contribuir para as discrepâncias observadas na literatura, entre os quais as medidas utilizadas para avaliar o desempenho de nomeação rápida (por exemplo, medidas que utilizam estímulos ortográficos ou não-ortográficos) e de leitura (por exemplo, medidas de fluência ou de acuidade). A importância da natureza das medidas quer de nomeação rápida quer de leitura tem sido reconhecida por vários autores (para uma revisão, ver Norton & Wolf, 2011). Paralelamente, as amostras estudadas, que têm variado quanto à idade/escolaridade dos participantes e à sua competência de leitura (leitores normais ou fracos leitores ou leitores disléxicos), poderão estar a contribuir para a heterogeneidade dos resultados publicados. A literatura recente tem salientado a relevância destes fatores na aquisição e desenvolvimento da leitura, embora a direccionalidade do seu efeito seja ainda pouco clara. Por exemplo, a transição de um procedimento de leitura baseado em estratégias de descodificação fonológica para uma leitura automática, à medida que o sujeito se torna um leitor fluente, parece ser acompanhada por uma mudança no peso relativo das capacidades cognitivas subjacentes à leitura (ex., Reis, Faísca, Castro, & Petersson, in press). Outro fator importante que tem dificultado a interpretação dos dados publicados sobre os construtos envolvidos na leitura, e em particular sobre a nomeação rápida, relaciona-se com a consistência ortográfica do sistema de escrita nos quais os estudos são conduzidos. Estudos trans-linguísticos sugerem que a consistência ortográfica influencia a facilidade com que se aprende a ler nas escritas alfabéticas, bem como o tipo de processamento de leitura predominantemente adotado pelos leitores (Seymour, Aro, & Erskine, 2003). No seio deste enquadramento, nesta tese procurámos clarificar as divergências encontradas na literatura relativamente à relação entre a nomeação rápida e o desempenho de leitura. Através de um estudo de meta-análise 1 é nosso objetivo realizar uma síntese objetiva do estado da arte sobre a relação entre a nomeação rápida e a leitura, e avaliar a influência de potenciais fatores moderadores da magnitude desta relação, nomeadamente: (a) a natureza da tarefa de nomeação (tipo de estímulo nomeado, número total de itens, e número de itens diferentes); (b) a natureza da tarefa de leitura (subcomponente de leitura, e medida de resposta usada para avaliar o desempenho); (c) características da amostra (escolaridade e nível de leitura); e (d) ortografia (sistema de escrita, e consistência ortográfica). Para tal, foi realizada uma procura de artigos científicos nas bases de dados PubMed, PsycINFO, e Web of Knowledge, tendo sido incluídas na meta-análise um total de 154 experiências independentes, compreendendo 21,706 participantes. Os resultados indicam uma relação moderada-a-forte entre a nomeação rápida e o desempenho de leitura (r =.44, I2 = 71.19). Nas análises seguintes procurou-se avaliar o contributo de potenciais variáveis moderadoras que possam explicar a heterogeneidade observada entre os tamanhos dos efeitos. Verificou-se que a nomeação rápida se associa significativamente e em magnitude semelhante com todas as medidas de leitura, i.e., quer estas apelem preferencialmente a um processamento de descodificação fonológica ou de reconhecimento de padrões ortográficos da palavra. Os resultados sugerem ainda que a magnitude das correlações é inflacionada nos estudos em que o desempenho de leitura é baseado na velocidade/fluência de leitura, em particular nos níveis de escolaridade mais avançados, e que utilizam tarefas de nomeação com estímulos alfanuméricos ao invés de estímulos não-alfanuméricos. Adicionalmente, verificou-se que a força da associação entre a nomeação rápida e a acuidade de leitura varia de forma não linear durante a evolução da leitura, sendo que a correlação é maior nos leitores escolarizados mais novos e decresce à medida que a escolaridade aumenta. O papel atribuível à proficiência dos leitores, i.e., fracos leitores/leitores disléxicos ou leitores normais, foi menos claro; no entanto, houve uma tendência para a relação ser mais forte nas amostras de fracos leitores/leitores disléxicos. Os resultados das comparações trans-linguísticas, por sua vez, sugerem que a nomeação rápida tem um papel importante para o desempenho da leitura independentemente das características da ortografia, ainda que as correlações tenham sido maiores nas ortografias opacas, e em particular nas línguas não-alfabéticas. Em suma, a presente meta-análise fornece resultados convincentes de que o desempenho em tarefas de nomeação rápida refletirá processos cognitivos subjacentes que são também relevantes para a aquisição/desenvolvimento da leitura. Consequentemente, pode dizer-se que estas medidas serão um preditor útil da competência de leitura. Os resultados são também discutidos no contexto das teorias atuais que procuram explicar através de que processos cognitivos se associam a nomeação rápida e a leitura, com ênfase nas hipóteses fonológica versus ortográfica. 1 Uma meta-análise permite a integração quantitativa de resultados de diversos estudos, recorrendo para isso à noção de magnitude do efeito.

Dynamic cost indexing

This paper describes the development of a generic tool for dynamic cost indexing (DCI), which encompasses the ability to manage flight delay costs on a dynamic basis, trading accelerated fuel burn against ‘cost of time’. Many airlines have significant barriers to identifying which costs should be included in ‘cost of time’ calculations and how to quantify them. The need is highlighted to integrate historical passenger delay and policy data with real-time passenger connections data. The absence of industry standards for defining and interfacing necessary tools is recognised. Delay recovery decision windows and ATC cooperation are key constraints. DCI tools could also be used in the pre-departure phase, and may offer environmental decision support functionality: which could be used as a differentiating technology required for access to designated, future ‘green’ airspace. Short-term opportunities for saving fuel and/or reducing emissions are also identified.

Dynamic cost indexing: cost estimations and building the prototype

The design of a decision-support prototype tool for managing flight delay costs in the pre-departure and airborne phases of a flight is described. The tool trades accelerated fuel burn and emissions charges against 'cost of time'. Costs for all major 'cost of time' components, by three cost scenarios, twelve aircraft types and by magnitude of delay are derived. Short-term opportunities for saving fuel and/or reducing environmental impacts are identified. A shift in ATM from managing delay minutes to delay cost is also supported.

A DHT-Based Grid Resource Indexing and Discovery Scheme

This paper presents a DHT-based grid resource indexing and discovery (DGRID) approach. With DGRID, resource-information data is stored on its own administrative domain and each domain, represented by an index server, is virtualized to several nodes (virtual servers) subjected to the number of resource types it has. Then, all nodes are arranged as a structured overlay network or distributed hash table (DHT). Comparing to existing grid resource indexing and discovery schemes, the benefits of DGRID include improving the security of domains, increasing the availability of data, and eliminating stale data.

Space-efficient Indexing of Chess Endgame Tables

Chess endgame tables should provide efficiently the value and depth of any required position during play. The indexing of an endgame’s positions is crucial to meeting this objective. This paper updates Heinz’ previous review of approaches to indexing and describes the latest approach by the first and third authors. Heinz’ and Nalimov’s endgame tables (EGTs) encompass the en passant rule and have the most compact index schemes to date. Nalimov’s EGTs, to the Distance-to-Mate (DTM) metric, require only 30.6 × 10^9 elements in total for all the 3-to-5-man endgames and are individually more compact than previous tables. His new index scheme has proved itself while generating the tables and in the 1999 World Computer Chess Championship where many of the top programs used the new suite of EGTs.

Space-efficient indexing of endgame tables for chess

Chess endgame tables should provide efficiently the value and depth of any required position during play. The indexing of an endgame’s positions is crucial to meeting this objective. This paper updates Heinz’ previous review of approaches to indexing and describes the latest approach by the first and third authors. Heinz’ and Nalimov’s endgame tables (EGTs) encompass the en passant rule and have the most compact index schemes to date. Nalimov’s EGTs, to the Distance-to-Mate (DTM) metric, require only 30.6 × 109 elements in total for all the 3-to-5-man endgames and are individually more compact than previous tables. His new index scheme has proved itself while generating the tables and in the 1999 World Computer Chess Championship where many of the top programs used the new suite of EGTs.