• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Tesis Doctoral
DOI
https://doi.org/10.11606/T.45.2019.tde-02042019-231050
Documento
Autor
Nombre completo
Joel Edu Sanchez Castro
Dirección Electrónica
Instituto/Escuela/Facultad
Área de Conocimiento
Fecha de Defensa
Publicación
São Paulo, 2018
Director
Tribunal
Hashimoto, Ronaldo Fumio (Presidente)
Barrera, Junior
Braga Neto, Ulisses de Mendonça
Martins Junior, David Corrêa
Ris, Marcelo
Título en inglés
Model selection for learning boolean hypothesis
Palabras clave en inglés
Boolean hypothesis
Domain partitions
Learning feasibility
Machine learning
VC-dimension
Resumen en inglés
The state of the art in machine learning of Boolean functions is to learn a hypothesis h, which is similar to a target hypothesis f, using a training sample of size N and a family of a priori models in a given hypothesis set H, such that h must belong to some model in this family. An important characteristic in learning is that h should also predict outcome values of f for previously unseen data, so the learning algorithm should minimize the generalization error which is the discrepancy measure between outcome values of f and h. The method proposed in this thesis learns family of models compatible with training samples of size N. Taking into account that generalizations are performed through equivalence classes in the Boolean function domain, the search space for finding the correct model is the projection of H in all possible partitions of the domain. This projection can be seen as a model lattice which is anti-isomorphic to the partition lattice and also has the property that for every chain in the lattice there exists a relation order given by the VC dimension of the models. Hence, we propose a model selector that uses the model lattice for selecting the best model with VC dimension compatible to a training sample of size N, which is closely related to the classical sample complexity theorem. Moreover, this model selector generalizes a set of learning methods in the literature (i.e, it unifies methods such as: the feature selection problem, multiresolution representation and decision tree representation) using models generated from a subset of partitions of the partition space. Furthermore, considering as measure associated to the models the estimated error of the learned hypothesis, the chains in the lattice present the so-called U-curve phenomenon. Therefore, we can use U-curve search algorithms in the model lattice to select the best models and, consequently, the corresponding VC dimension. However, this new generation of learning algorithms requires an increment of computational power. In order to face this problem, we introduce a stochastic U-curve algorithm to work on bigger lattices. Stochastic search algorithms do not guarantee finding optimal solutions, but maximize the mean quality of the solution for a given amount of computational power. The contribution of this thesis advances both the state of the art in machine learning theory and in practical problem solutions in learning.
Título en portugués
Seleção de modelos para o aprendizado de hipóteses booleanas
Palabras clave en portugués
Aprendizado de máquina
Dimensão VC
Hipóteses booleanas
Partições do domínio
Viabilidade de aprendizado
Resumen en portugués
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óteses 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 dada pela dimensão VC dos modelos. Portanto, 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, 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, introduzimos o algoritmo Stochastic $U$-curve para trabalhar em reticulados maiores. Algoritmos de busca estocásticos não garantem encontrar soluções ótimas, mas maximizam a qualidade média 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.
 
ADVERTENCIA - La consulta de este documento queda condicionada a la aceptación de las siguientes condiciones de uso:
Este documento es únicamente para usos privados enmarcados en actividades de investigación y docencia. No se autoriza su reproducción con finalidades de lucro. Esta reserva de derechos afecta tanto los datos del documento como a sus contenidos. En la utilización o cita de partes del documento es obligado indicar el nombre de la persona autora.
tese.pdf (1.15 Mbytes)
Fecha de Publicación
2019-05-22
 
ADVERTENCIA: Aprenda que son los trabajos derivados haciendo clic aquí.
Todos los derechos de la tesis/disertación pertenecen a los autores
CeTI-SC/STI
Biblioteca Digital de Tesis y Disertaciones de la USP. Copyright © 2001-2024. Todos los derechos reservados.