Uma Abordagem de Componentes Combinados para a Geração de Funções de Ordenação usando Programação Genética

• Humberto Mossri de Almeida UFMG
• Marcos Andre Gonçalves UFMG

Resumo

Com o crescimento da Web, a tarefa de recuperação de informação (RI) transformou-se em um problema extremamente complexo e desafiador. Por isso, diversas funções de ordenação têm sido investigadas ao longo dos anos. No entanto, a maioria delas tem um caráter genérico, isto é, são projetadas para serem efetivas em qualquer coleção. Este trabalho propõe um novo método para descobrir funções de ordenação adaptadas a uma coleção baseado em programação genética (GP). O processo evolutivo da Abordagem de Componentes Combinados (CCA), proposta por este trabalho, reutiliza componentes de diferentes funções de ordenação comprovadamente eficazes e conhecidas da literatura de recuperação de informação. Parte-se da hipótese de que estes componentes são individualmente representativos e ricos de significado e podem ser combinado pelo arcabouço GP para a geração de uma nova função de ordenação mais efetiva e especializada para uma determinada coleção. Os resultados experimentais mostram que a abordagem proposta foi capaz de superar em até 40% abordagens clássicas da literatura em duas coleções diferentes e de reduzir o problema do “treinamento exagerado”, geralmente encontrado em métodos de aprendizado de máquina, especialmente programação genética.

Referências

Almeida, H. M. (2007). Uma abordagem de componentes combinados para a geração de funções de ordenação usando programação genética. Dissertação de Mestrado, DCC, UFMG. Disponível em [link].

Almeida, H. M., Gonçalves, M. A., Cristo, M., and Calado, P. (2007). A combined component approach for finding collection-adapted ranking functions based on genetic programming. In Proc. of the 30th ACM SIGIR, pages 399–406, Amsterdam, Netherlands.

Battelle, J. (2005). A Busca. Elsevier, Rio de Janeiro.

Buckley, C., Singhal, A., and Mitra, M. (1996). New retrieval approaches using smart: TREC 4. In Proc. of TREC-4, pages 25–48, Gaithersburg, MD. NIST Special Publication 500-236.

Fan, W., Gordon, M. D., and Pathak, P. (2004). A generic ranking function discovery framework by genetic programming for information retrieval. Information Processing and Management, 40(4):587–602.

Fan, W., Gordon, M. D., and Pathak, P. (2005). Genetic programming-based discovery of ranking functions for effective web search. Journal of Management Information Systems, 21(4):37–56.

Koza, J. R. (1992). Genetic Programming: On the programming of computers by natural selection. MIT Press, Cambridge.

Robertson, S. E. and Sparck-Jones, K. (1976). Relevance weighting of search terms. Journal of the American Society for Information Science, 27(3):129–146.

Robertson, S. E. and Walker, S. (1999). Okapi/keenbow at TREC-8. In Proc. of TREC-8, pages 151–162, Gaithersburg, MD. NIST Special Publication 500-246.

Salton, G. and Buckley, C. (1988). Term-weighting approaches in automatic text retrieval. Information Processing and Management, 24(5):513–523.

Singhal, A., Buckley, C., and Mitra, M. (1996). Pivoted document length normalization. In Proc. of the 19th ACM SIGIR, pages 21–29, Zurich, Switzerland.

Trotman, A. (2005). Learning to rank. Information Retrieval, 8(3):359–381.

Voorhees, E. M. and Harman, D. (1999). Overview of the eighth Text REtrieval Conference (TREC-8). In Proc. of TREC-8, pages 1–24, Gaithersburg, MD. NIST Special Publication 500-246.

Zobel, J. and Moffat, A. (1998). Exploring the similarity space. SIGIR Forum, 32(1):453–490.