Logotipo Dedalus   Logotipo ABCD
                         
Identificação       Preferências   Catálogos   Fale Conosco   Encerrar Sessão  
Buscas   Resultados   Buscas Anteriores   Meus Docs.   Histórico   Vocabulário   Ajuda
 
  Adicionar Reg. Meus Docs.  |  Localizar  |  Salvar / E-mail  

Registro Completo

Escolher formato: Padrão Ficha Formato Reduzido Nomes MARC Campos MARC
No. Registro   002406809
Tipo de material   TESE
Entrada Principal   LinkReis, Marcelo da Silva https://orcid.org/0000-0002-3754-9115
Título   LinkMinimização de funções decomponíveis em curvas em U definidas sobre cadeias de posets - algoritmos e aplicações.
Imprenta   São Paulo, 2013.
Descrição   142 p.
Idioma   Português
Nota Tese/Diss   Tese (Doutorado)
Resumo   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
  també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.
Ag de Financiamento   Financiado pelo CNPq
Nota Local   Ciência da Computação
Departamento   MAC CIENCIA DA COMPUTACAO
Assunto   LinkINTELIGÊNCIA ARTIFICIAL
Autor Secundário   LinkBarrera, Júnior
Localiz.Eletrônica    Clicar sobre o botão para acesso ao texto 
 
Acervo Geral   Todos os itens
Itens na Biblioteca   IME-Inst. Mat. e EstatísticaLibrary Info
Unidade USP   IME -- INSTITUTO DE MATEMÁTICA E ESTATÍSTICA

Escolher formato: Padrão Ficha Formato Reduzido Nomes MARC Campos MARC


Encerrar Sessão - Preferências - Fale Conosco - Ajuda - Ex Libris
Buscas - Resultados - Buscas Anteriores - Catálogos