Model selection for learning boolean hypothesis (2018)
- Authors:
- Autor USP: CASTRO, JOEL EDU SANCHEZ - IME
- Unidade: IME
- Sigla do Departamento: MAC
- Assunto: APRENDIZADO COMPUTACIONAL
- Keywords: Aprendizado de máquina; Boolean hypothesis; Dimensão VC; Domain partitions; Hipóteses booleanas; Learning feasibility; Machine learning; Partições do domínio; VC-dimension; Viabilidade de aprendizado
- Agências de fomento:
- Language: Inglês
- Abstract: 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
- Imprenta:
- Data da defesa: 10.08.2018
-
ABNT
SANCHEZ CASTRO, Joel Edu. Model selection for learning boolean hypothesis. 2018. Tese (Doutorado) – Universidade de São Paulo, São Paulo, 2018. Disponível em: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-02042019-231050/. Acesso em: 14 fev. 2026. -
APA
Sanchez Castro, J. E. (2018). Model selection for learning boolean hypothesis (Tese (Doutorado). Universidade de São Paulo, São Paulo. Recuperado de http://www.teses.usp.br/teses/disponiveis/45/45134/tde-02042019-231050/ -
NLM
Sanchez Castro JE. Model selection for learning boolean hypothesis [Internet]. 2018 ;[citado 2026 fev. 14 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-02042019-231050/ -
Vancouver
Sanchez Castro JE. Model selection for learning boolean hypothesis [Internet]. 2018 ;[citado 2026 fev. 14 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-02042019-231050/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
