Compressive sensing for media search engines

Referência do Projecto: PTDC/EIA-EIA/111518/2009
Investigador Responsável: João Miguel Costa Magalhães
Instituição Proponente: Fundação da Faculdade de Ciências e Tecnologia da Universidade Nova de Lisboa (FFCT/FCT/UNL)
Data de Início: 01-04-2011
Data de Fim: 30-09-2014
Financiamento Concedido: €67.599,00

Os motores de pesquisa atuais recolhem grandes quantidades de dados sobre a interacção do utilizador, como por exemplo, pesquisas, “click data”, anotações, comentários e novos conteúdos. Esta diversidade de fontes de informação coloca dois desafios críticos às técnicas tradicionais de indexação e pesquisa: (1) extrair a informação relevante de um grande número de fontes e (2) fazer a correspondência entre a pesquisa do utilizador e a informação extraída.

A hipótese principal deste projecto é que as técnicas de “compressed sensing” poderão dar um forte contribute à área de recuperação de informação multimédia. Esta hipótese é suportada por dois factos. O primeiro facto está relacionado com o critério de minimização L1: aplicações multimédia necessitam tratar informação com um elevado número de variáveis, e os modelos esparsos, como os computados por técnicas de “compressed sensing”, podem realmente reduzir o número de fontes de informação. O segundo facto está relacionado com a larga escala de recursos disponíveis que permite a inferência de uma representação esparsa de documentos multimédia.

Para investigar esta hipótese, foram identificados três objectivos principais.

  1. O primeiro objectivo foca os métodos de indexação de elevada dimensão. A complexidade computacional para pesquisar um índice aumenta com a dimensionalidade dos dados. Serão investigados novos métodos para computar uma representação esparsa de multimédia para uma rápida indexação e recuperação.
  2. O segundo objectivo aborda a mineração (ou extracção) da informação (estruturada) relevante dos dados. O elevado número de fontes envolvido na inferência de informação/factos é uma das grandes vantagens das técnicas de “compressed sensing”.
  3. O terceiro objectivo: aprendizagem online para responder às pesquisas do utilizador. A análise e categorização automática da pesquisa do utilizador podem direccionar os utilizadores para uma consulta mais próxima das suas intenções.

Objectivos atingidos

O projeto propunha-se a seguir três grandes objetivos. Destas três áreas, a indexação de imagens foi a que obteve melhores resultados passíveis de serem patenteados. Foram utilizados conceitos presentes em compressive sensing para melhorar o particionamento do espaço de indexação. O processo de obtenção de patente está neste momento a ser avaliado pelos serviços da Universidade Nova de Lisboa.

Outra área onde foi possível fazer avanços interessantes foi na combinação de anotação e análise de queries: mais concretamente no tema de recomendação através da análise de comentários. Foram utilizados métodos de regularização esparsa na decomposição de matrizes de ratings colaborativos.

Para além dos artigos, foram produzidas duas teses de mestrado e uma tese de doutoramento que aguarda discussão. Para além destes resultados, um dos investigadores está a dar continuidade a este projeto através da realização do Doutoramento no tema da indexação cross-media, que combina dois dos objetivos do projeto: anotação e indexação.


Publicações

Conferências

High-dimensional Indexing and Ranking
1. André Mourão, Flávio Martins, João Magalhães: NovaSearch at TREC 2013 Federated Web Search Track: Experiments with rank fusion. Text REtrieval Conference 2013.

Pendente de decisão sobre patente:
André Mourão, Pedro Borges and João Magalhães: Scalable Web Media Search with Distributed Indexing by Sparse Approximation. To be submitted.

Query processing and search
2. Bruno Cardoso, João Magalhães: Google, bing and a new perspective on ranking similarity. CIKM 2011: 1933-1936
3. André Mourão, Flávio Martins, João Magalhães: NovaSearch on Medical ImageCLEF 2013. CLEF (Working Notes) 2013
4. André Mourão, Flávio Martins, João Magalhães: Inverse square rank fusion for multimodal search. CBMI 2014: 1-6
5. Flávio Martins, André Mourão, João Magalhães: NovaSearch at TREC 2013 Microblog Track: Experiments with reranking using Wikipedia. Text REtrieval Conference 2013.

Recommendation
6. Filipa Peleja, Pedro Dias, João Magalhães: A Regularized Recommendation Algorithm with Probabilistic Sentiment-Ratings. ICDM Workshops 2012: 701-708
7. Pedro Dias and João Magalhães: Matrix Factorization with Latent-space Clustering for Group-recommendations. EPIA 2013 (conferência nacional).

Information Analysis and Extraction
8. André Mourão, Pedro Borges, Nuno Correia, João Magalhães: Facial Expression Recognition by Sparse Reconstruction with Robust Features. ICIAR 2013: 107-115
9. André Mourão, Pedro Borges, Nuno Correia and Joao Magalhaes: Sparse Reconstruction of Facial Expressions with Localized Gabor Moments. EUSIPCO 2014
10. Filipa Peleja, João Santos, João Magalhães: Reputation analysis with a ranked sentiment-lexicon. SIGIR 2014: 1207-1210
11. Filipa Peleja, João Santos, and João Magalhães: Ranking Linked-Entities in a Sentiment Graph. IEEE/WIC/ACM Web Intelligence 2014.

Revista

  1. André Mourão, Flávio Martins and João Magalhães: Multimodal medical information retrieval with unsupervised rank fusion. Computerized Medical Imaging and Graphics 2014.05.006,  2014
  2. Filipa Peleja and João Magalhães: ACM Transactions on Information Systems, submitted for publication.

Pendente de decisão sobre patente:
Pedro Borges, André Mourão and João Magalhães: High-dimensional Indexing by Sparse Approximation. IEEE Transactions on Multimedia, to be submitted for publication.

Master Thesis

  1. P. Borges, “High-dimensional indexing by sparse approximation”, Computer Science M.Sc. thesis, FCT/UNL, concluded in January 2013.
  2. P. Dias, “Recommending media content based on machine learning methods”, Computer Science M.Sc. thesis, FCT/UNL, concluded in December 2011.

Doctoral Thesis

  1. Filipa Peleja, “Sentiment analysis for recommender systems,” Ph.D. in Computer Science, FCT/UNL, aguarda exame que antecede discussão final. Previsto para Janeiro de 2015.

Protótipos e Demonstrações

NovaMedSearch: http://medical.novasearch.org

O sistema de pesquisa para o domínio médico encontra-se ilustrado na figura abaixo. Trata-se de um sistema que junta efetivamente todas as componentes investigadas no projeto. As componentes deste motor de pesquisa integram funcionalidades como:

  1. Indexação de todo o conteúdo aberto do PubMed;
  2. Análise e expansão de query textual;
  3. Pesquisa cross-modal para pesquisar com imagens médicas o repositório do PubMed;
  4. Pesquisa de casos semelhantes;
  5. Pesquisa escalável para milhões de imagens.

novamedsearch

NovaVidSearch: http://video.novasearch.org

No seguimento do sucesso das tecnologias desenvolvidas, a equipa foi contactada pela Portugal Telecom para avaliar a viabilidade destas tecnologias para os seus serviços de pesquisa de vídeos. Consequentemente, a equipa foi financiada para desenvolver a aplicação computacional NovaVidSearch.
Com esta aplicação foi possível cobrir informação na forma de vídeos que até então não tinha sido considerado. Todos os algoritmos investigados foram focados em imagem e texto. Como forma de confirmar a generalização do trabalho desenvolvido, esta aplicação pôde re-utilizar toda a base desenvolvida sem qualquer esforço considerável.

novavidsearch

Protótipo Laboratorial: Servidor para pesquisa de multimédia

Foi desenvolvida um protótipo de servidor para pesquisa de multimédia que tem como objetivo ser fortemente reutilizável e abrangente o suficiente para suportar dados muito variados como é o caso de multimédia.
Este protótipo continua a ser desenvolvido pela equipa no contexto de uma tese de doutoramento.
As duas aplicações de pesquisa são dois casos de uso onde foram utilizadas duas coleções de dados muito distintas e foram implementadas duas interfaces de suporte a pesquisa multimodal.

Modelos

Foi desenvolvido um modelo sobre o léxico para análise de texto de opiniões de utilizadores. Este modelo está descrito no artigo de revista que se encontra neste momento em análise e que é a contribuição principal da tese de Doutoramento apoiada pelo projeto.