Busca por Descida de Gradiente

Este texto é parte da disciplina de Fundamentos de Inteligência Artificial do Programa de Pós-Graduação em Computação da Universidade Federal de Pelotas e não foi feito para fazer muito sentido fora deste contexto.

Na busca por subida de encosta mais íngreme (steepest ascent hill climbing), todos os vizinhos do estado atual são avaliados e o melhor deles se torna o novo estado atual. Claramente isso tem um alto custo quando o número de vizinhos é grande, o que tipicamente é o caso em problemas de otimização. Enquanto a busca por subida de encosta tradicional tenta solucionar isso avaliando os vizinhos em sequência e parando no momento que encontra um melhor que o atual, no pior caso ainda é necessário visitar todos. Idealmente, seria interessante saber pelo menos a direção do melhor vizinho. Por exemplo, se estamos otimizando f(x) e nosso estado atual é x=3, temos que testar valores maiores ou menores que 3?

Quando nossa função de avaliação é numérica e diferenciável, temos uma alternativa melhor do que testar a vizinhança de forma exaustiva: a busca por descida de gradiente (agora estamos descendo algo e não subindo, como no hill climbing; a notação da área não é a mais consistente, mas é sempre possível transformar qualquer problema de minimização em um de maximização e vice-versa).

Uma função ser numérica simplesmente significa que seus parâmetros todos são valores reais. A contraparte é otimização combinatória onde, por exemplo, se deseja encontrar a melhor permutação de elementos. Uma função ser diferenciável (ou derivável) significa que é possível calcular sua derivada para todos seus pontos. Neste ponto é útil ler sobre derivadas se você não teve uma formação em Cálculo, mas em essência a derivada de uma função em um ponto é o ângulo da reta tangente ao ponto e à função. Este ângulo nos dá informação sobre a direção do crescimento da função com relação à variável — e.g. um valor negativo informa que f(x) cresce com x. Esta informação é denominada gradiente. Você pode visualizar interativamente esta interpretação geométrica neste site.

O cálculo do gradiente permite calcular diretamente o próximo estado da busca, sem testes desnecessários, sendo portanto muito mais eficiente que uma subida de encosta. O método de busca baseado em minimizar o gradiente é denominado busca por descida de gradiente (gradient descent search). Porém, ele ainda sofre com ótimos locais. Um ótimo local é indicado por uma derivada igual a zero, impedindo o progresso do algoritmo. Técnicas como reinício aleatório podem ser usados para encontrar múltiplos ótimos locais.

Busca por descida de gradiente tem sido amplamente empregada no treinamento de redes neurais, onde define-se uma função de erro diferenciável e, então, procura-se por parâmetros da rede que minimizem esta função por meio de gradientes. É, portanto, um dos algoritmos de busca mais importantes no momento.

Para saber mais, esta é uma boa leitura sobre o assunto (não esqueça de seguir para a Parte 2).