Download como arquivo ICAL
"Model Selection for Learning Boolean Hypothesis"
Sexta-feira 10 Agosto 2018, 10:00
Contato: Este endereço de email está sendo protegido de spambots. Você precisa do JavaScript ativado para vê-lo.

Candidato: Joel Edu Sanches Castro

 

Orientador: Prof. Dr. Ronaldo Fumio Hashimoto

 

Resumo: O estado da arte em aprendizado de funções Booleanas é aprender uma hipótese h,
que é similar a uma hipótese objetivo f, a partir de uma amostra de tamanho N e uma
família de modelos a priori em um dado conjunto de hipótese H, tal que h deve pertencer
a algum modelo nesta família. Uma característica importante no aprendizado é que h
deve também predizer resultados de f para elementos que não aparecem no conjunto de
treinamento, então o algoritmo de aprendizado deve minimizar o erro de generalização,
o qual mede a discrepância entre os resultados de f e h. O método proposto nesta
tese aprende uma família de modelos compatíveis com um conjunto de treinamento de
tamanho N.
Tomando em consideração que as generalizações são realizadas através de classes
de equivalência no domínio da função Booleana, o espaço de busca para encontrar
um modelo apropriado é a projeção de H em todas as possíveis partições do domínio.
Esta projeção pode ser vista como um reticulado de modelos que é anti-isomórfica ao
reticulado de partições e também tem a propriedade que para cada cadeia no reticulado
existe uma relação de ordem dado pela dimensão VC dos modelos. Por tanto, nós
propomos um seletor de modelos que usa o reticulado de modelos para selecionar o
melhor modelo com dimensão VC compatível ao conjunto de treinamento de tamanho
N, o qual é intimamente relacionado ao teorema clássico de complexidade da amostra.
Além disso, este seletor de modelos generaliza um conjunto de métodos de aprendizado
na literatura (i.e, ele unifica métodos tais como: o problema de seleção de
características, a representação multiresolução e a representação por árvores de decisão)
usando modelos gerados por um subconjunto de partições do espaço de partições. Ademais,
considerando como medida associada aos modelos o erro de estimação da hipótese
aprendida, as cadeias no reticulado apresentam o fenômeno chamado U-curve. Portanto,
nós podemos usar algoritmos de busca U-curve no reticulado de modelos para selecionar
os melhores modelos, consequentemente, a correspondente dimensão VC.
No entanto, esta nova geração de algoritmos de aprendizado requerem um incremento
de poder computacional. Para enfrentar este problema, nós introduzimos o algoritmo
v
vi
Stochastic U-curve para trabalhar em reticulados maiores. Algoritmos de busca estocásticos
não garantem encontrar soluções ótimas, mas maximizam a qualidade media das
soluções para uma determinada quantidade de poder computacional. A contribuição
desta tese avança ambos o estado da arte na teoria de aprendizado de máquina e soluções
a problemas práticos em aprendizado.
Palavras chave: aprendizado de máquina, hipóteses Booleanas, partições do domínio,
viabilidade de aprendizado, dimensão VC.

Local Auditório Jacy Monteiro - Bloco B do IME