Ver registro no DEDALUS
Exportar registro bibliográfico

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

  • Authors:
  • USP affiliated authors: REIS, MARCELO DA SILVA - IME
  • USP Schools: IME
  • Sigla do Departamento: MAC
  • Subjects: INTELIGÊNCIA ARTIFICIAL
  • 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). Apresentamos
  • Imprenta:
  • Data da defesa: 28.11.2012
  • Acesso online ao documento

    Acesso à fonte or search this record in

    How to cite
    A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas

    • ABNT

      REIS, Marcelo da Silva; BARRERA, Júnior. Minimização de funções decomponíveis em curvas em U definidas sobre cadeias de posets - algoritmos e aplicações. 2012.Universidade de São Paulo, São Paulo, 2012. Disponível em: < http://www.teses.usp.br/teses/disponiveis/45/45134/tde-05022013-123757 >.
    • APA

      Reis, M. da S., & Barrera, J. (2012). Minimização de funções decomponíveis em curvas em U definidas sobre cadeias de posets - algoritmos e aplicações. 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, Barrera J. Minimização de funções decomponíveis em curvas em U definidas sobre cadeias de posets - algoritmos e aplicações [Internet]. 2012 ;Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-05022013-123757
    • Vancouver

      Reis M da S, Barrera J. Minimização de funções decomponíveis em curvas em U definidas sobre cadeias de posets - algoritmos e aplicações [Internet]. 2012 ;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 - 2019