Aprendizado de Máquina via Álgebra Linear e Otimização

Página da disciplina optativa Aprendizado de Máquina via Álgebra Linear e Otimização, lecionada pelo Prof. Alexandre Salles da Cunha e pela Profa. Ana Paula Couto, para os cursos de Bacharelado em Ciência da Computação, Sistemas de Informação e Matemática Computacional da UFMG.

1 Objetivos gerais

Apresentar ao estudante de graduação uma formalização matemática dos processos de aprendizado através de uma abordagem centrada em Álgebra Linear e Otimização. Rediscutir modelos e técnicas de Aprendizado de Máquina (AM) sob o paradigma da Programação Matemática (com foco em Programação Linear Inteira e Binária Quadrática), buscando reformular os modelos e algoritmos de otimização embarcados nas técnicas de AM. Com o processo de reformulação, buscamos produzir técnicas mais interpretáveis, cuja capacidade de generalização seja menos dependente da presença de outliers, e que ofereçam parâmetros globalmente ótimos, dada a hipótese de aprendizado estabelecida.

Essencialmente, o objetivo desta disciplina é apresentar o tema AM, ou pelo menos a sua fase de treinamento, como um processo de modelagem e de resolução de problemas de Otimização. A resolução do problema de Otimização obtido é então discutida, seja utilizando ferramentas da Álgebra Linear, da Otimização Não Linear e/ou da Otimização em variáveis discretas.

2 Objetivos específicos

Trataremos de quatro grandes grupos de técnicas para aprendizado supervisionado e não supervisionado:

• Redes Neurais Artificiais de pequenas dimensões.

• Sparse Principal Component Analysis .

• Árvores de Decisão Ótimas.

• Hard-margin Support Vector Machines.

Cada uma destas técncias definirá um módulo da disciplina. E para cada módulo, trataremos de rediscutir e/ou reformular abordagens usualmente empregadas pela comunidade de AM, introduzindo formalmente paradigmas alternativos de Otimização, indicando suas vantagens e limitações em relação ao estabelecido na área.

Exceto pelo primeiro módulo, estes paradigmas passam necessariamente por reformular o processo de aprendizado por meio de modelos de otimização que empregam variáveis discretas para representar ou caracterizar o aprendizado. Para o primeiro módulo reservamos uma discussão pouco tratada usualmente: de onde vieram as adaptações dos mecanismos de treinamento de redes neurais e a natureza intrinsicamente local da otimalidade dos parâmetros aprendidos na fase de treinamento. No primeiro módulo trataremos apenas de redes neurais de dimensões mínimas, uma vez que estas já são capazes de expor as dificulades inerentes ao treinamento de redes neurais.

3 Organização do curso

A disciplina é organizada em quatro grandes módulos, descritos á seguir.

1. Módulo 1: Treinamento de Redes Neurais Mínimas. Referências bibliográficas: [5, 7, 6].

   1. Conjuntos e funções convexas.

   2. Série de Taylor como ferramenta de aproximação de funções.

   3. Problema de Otimização Não Linear Irrestrita: busca undirecional exata (Seção Áurea) e aproximada (Armijo), direção de descida, Método do Gradiente, Método de Newton.

   4. Adaptações para treinamento de redes neurais: Stochastic Gradient Search.

   5. Ordem e taxa de convergência.

   6. Treinamento de redes neurais mínimas com caracterização de não convexidade e múltiplos ótimos locais.

2. Módulo 2: Sparse Principal Component Analysis. Referências bibliográficas: [2].

   1. Revisão de PCA.

   2. Dificuldade de tratar a esparsidade e conexões com técnicas de regularização.

   3. Algoritmo Branch-and-bound.

   4. Cotas inferiores e superiores.

   5. Cotas duais via relaxações e cotas espectrais.

   6. Aplicação em feature engineering.

3. Módulo 3: Árvores de Classificação Ótimas. Referências bibliográficas: [2, 3].

   1. Heurística CART (Classification and Regression Trees), ideias principais e limitações. Controle de overfitting via prunning. Ensemble methods baseados em CART.

   2. Árvores de Classificação Ótimas com splits paralelos.

   3. Árvores de Classificação Ótimas com splits em hiperplanos.

   4. Aplicações em contextos onde explicabilidade é essencial.

4. Módulo 4: SVMs (Support Vector Machines.) Referências bibliográficas [1, 4]

   1. SVMs com soft-margin: modelagem matemática e limitações.

   2. SVMs com hard-margin: Modelagem e algoritmos.

   3. Aplicações em Medicina, e reconhecimento de imagens e ergonomia do trabalho.

4 Avaliação da disciplina

• Uma lista de exercícios por módulo da disciplina, totalizando 50 pontos.

• Desenvolvimento e apresentação de um projeto: 50 pontos.

5 Referências Bibliográficas

As referências principais empregadas são apresentadas abaixo. Ao longo do curso, indicaremos artigos cietíficos complementares para cada um dos módulos.

Referências