Menu



Exportar registro bibliográfico

Tese

Minimização de funções decomponíveis em curvas em U definidas sobre cadeias de posets - algoritmos e aplicações (2012)

  • Authors:
  • Autor USP: REIS, MARCELO DA SILVA - IME
  • Unidade: IME
  • Sigla do Departamento: MAC
  • Assunto: INTELIGÊNCIA ARTIFICIAL
  • Agências de fomento:
  • Language: Português
  • Abstract: O problema de seleção de características, no contexto de Reconhecimento de Padrões, consiste na escolha de um subconjunto X de um conjunto S de características, de tal forma que X seja “ótimo” dentro de algum critério. Supondo a escolha de uma função custo c apropriada, o problema de seleção de características é reduzido a um problema de busca que utiliza c para avaliar os subconjuntos de S e assim detectar um subconjunto de características ótimo. Todavia, o problema de seleção de características é NP-difícil. Na literatura, existem diversos algoritmos e heurísticas propostos para abordar este problema. Porém, quase nenhuma dessas técnicas explora o fato que existem funções custo cujos valores são estimados a partir de uma amostra e que descrevem uma “curva em U” nas cadeias do reticulado Booleano (P(S); ), um fenômeno bem conhecido em Reconhecimento de Padrões: conforme aumenta-se o número de características consideradas, há uma queda no custo do subconjunto avaliado, até o ponto em que a limitação no número de amostras faz com que seguir adicionando características passe a aumentar o custo, devido ao aumento no erro de estimação. Em 2010, Ris e colegas propuseram um novo algoritmo para resolver esse caso particular do problema de seleção de características, que aproveita o fato de que o espaço de busca pode ser organizado como um reticulado Booleano, assim como a estrutura de curvas em U das cadeias do reticulado, para encontrar um subconjunto ótimo. Neste trabalho, estudamos a estrutura do problema de minimização de funções custo cujas cadeias são decomponíveis em curvas em U (problema U-curve), provando que o mesmo é NP-difícil. Mostramos que o algoritmo de Ris e colegas possui um erro que o torna de fato sub-ótimo, e propusemos uma versão corrigida e melhorada do mesmo, o algoritmo U-Curve-Search (UCS). Apresentamostambém duas variações do algoritmo UCS que gerenciam o espaço de busca de forma mais sistemática. Introduzimos dois novos algoritmos branch-and-bound para abordar o problema, chamados de U-Curve-Branch-and-Bound (UBB) e Poset-Forest-Search (PFS). Para todos os algoritmos apresentados nesta tese, fornecemos provas de correção e análise de complexidade de tempo. Implementamos todos os algoritmos apresentados utilizando o arcabouço featsel, também desenvolvido neste trabalho; realizamos experimentos ótimos e sub-ótimos com instâncias de dados reais e simulados e analisamos os resultados obtidos. Por fim, propusemos um relaxamento do problema U-curve que modela alguns tipos de projeto de classificadores; também provamos que os algoritmos UCS, UBB e PFS resolvem esta versão generalizada do problema.
  • Imprenta:
  • Data da defesa: 28.11.2012
    • Acesso à fonte
    How to cite
    A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas

    • ABNT

      REIS, Marcelo da Silva. Minimização de funções decomponíveis em curvas em U definidas sobre cadeias de posets - algoritmos e aplicações. 2012. Tese (Doutorado) – Universidade de São Paulo, São Paulo, 2012. Disponível em: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-05022013-123757. Acesso em: 23 abr. 2024.

    • APA

      Reis, M. da S. (2012). Minimização de funções decomponíveis em curvas em U definidas sobre cadeias de posets - algoritmos e aplicações (Tese (Doutorado). Universidade de São Paulo, São Paulo. Recuperado de http://www.teses.usp.br/teses/disponiveis/45/45134/tde-05022013-123757

    • NLM

      Reis M da S. Minimização de funções decomponíveis em curvas em U definidas sobre cadeias de posets - algoritmos e aplicações [Internet]. 2012 ;[citado 2024 abr. 23 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-05022013-123757

    • Vancouver

      Reis M da S. Minimização de funções decomponíveis em curvas em U definidas sobre cadeias de posets - algoritmos e aplicações [Internet]. 2012 ;[citado 2024 abr. 23 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-05022013-123757

    Últimas obras dos mesmos autores vinculados com a USP cadastradas na BDPI:

    Digital Library of Intellectual Production of Universidade de São Paulo     2012 - 2024