Gradiente Descendente

Gradiente Descendente em uma dimensão

Suponha uma função \(f: \mathbb{R} \to \mathbb{R}\) para a qual sabemos calcular \(f(x)\), \(\forall \ x \in \mathbb{R}\), e sabemos calcular \(f'(x)\), \(\forall \ x \in \mathbb{R}\). Suponha também que essa função contém pelo menos um mínimo local. O gradiente descendente é um método numérico que converge para o ponto \(x^\star \in \mathbb{R}\) tal que \(x^\star = \arg \min_{x \in \mathbb{R}} f(x)\), isto é, \(f(x^\star) \le f(x) \ \forall x \in \mathbb{R}\).

A Idéia

A ideia princial do gradiente descendente é a seguinte: dado um ponto qualquer do domínio \(x_0\) sabemos que \(f´(x_0)\) indica se a função cresce ou decresce em \(x_0\). Por exemplo, se \(f'(x_0) > 0\), significa que a função é crescente em \(x_0\). Então se definirmos \(x_1 = x_0 - \delta\), com \(\delta\) pequeno, provavelmente teremos \(f(x_1) < f(x_0)\).

Por outro lado, se \(f'(x_0) < 0\) significa que a função é decrescente em \(x_0\). Então se definirmos \(x_1 = x_0 + \delta\), com \(\delta\) pequeno, provavelmente teremos \(f(x_1) < f(x_0)\).

o tamanho do passo \(\delta\) não pode ser constante, ele precisa diminuir para pontos que já estiverem relativamente próximo de \(x^\star\). Uma maneira de fazer isso é definir o tamanho do passo como uma proporção do tamanho da derivada no ponto, pois \(f'(x)\) fica menor quando \(x\) se aproxima de \(x^\star\).

\[ x_{i+1} = x_{i} - \delta f'(x_i) \]

Veja um exemplo considerando \(\delta= 0,2\) e \(f(x) = x^2 - 1\).

Veja agora a diferença quando \(\delta= 2\).

O Algoritmo

Seja \(f: \mathbb{R} \to \mathbb{R}\) uma função tal que é possível calcular \(f'(x)\) \(\forall \ x \in \mathbb{R}\).

1. Defina valores inicias para os hiperparâmetros \(\delta\), \(\varepsilon\) e \(N_{max}\).

2. Inicie \(i=0\) e \(x_0\) como um ponto qualquer. Geralmente \(x_0\) é definido de forma aleatória.

3. Calcule \(f'(x_0)\) e atualize \(x_0 = x_0 - \delta f'(x_0)\).

4. Incremente \(i = i + 1\) .

5. Se um dos critérios de parada for alcançado, retorne \(x_0\):

   • \(|f'(x_0)| < \varepsilon\)

   • $i > \(N_{max}\)

6. Se não, volte para o passo 3.

Um exemplo no R

Vamos implmentar o gradiente descendente para encontrar o mínimo da seguinte função:

\[ f(x) = 1- x^2 \ e^{-3x} \]

f = function(x){1-(x^2)*exp(-3*x)}
curve(f(x)+x*0,xlim=c(0,3))

A derivada de \(f\) pode ser calculada por

\[ f'(x) = -2x e^{-3x} + 3 x^2 e^{-3x} \]

df = function(x){-(2*x)*exp(-3*x)+exp(-3*x)*3*x^2}

grad_des = function(x0 = runif(1), delta = 0.1, Nmax = 10000, epsilon = 0.00001){
  i = 0
  repeat{
    x0 = x0 - delta*df(x0)
    if(abs(df(x0))<epsilon){
      print(paste0("convergiu com ",i," iterações"))
      return(x0)
    }
    if(i > Nmax){
      print(paste0("Não convergiu"))
      return(x0)
    }
    i = i + 1  
  }
}

x = grad_des()

[1] "convergiu com 337 iterações"

curve(f(x)+x*0,xlim=c(0,3))
points(x,f(x),pch=19,col="red")

Vamos ver o caminho que o método fez até a convergência.

  curve(f(x)+x*0,xlim=c(0,3))
  delta = 0.8
  Nmax = 10000
  epsilon = 0.00001
  x0 = 2.5
  i = 0
  repeat{
    points(x0,f(x0),pch=19,col="red")
    segments(x0,f(x0),x0 - delta*df(x0),f(x0 - delta*df(x0)))
    x0 = x0 - delta*df(x0)
    if(abs(df(x0))<epsilon){
      print(paste0("convergiu com ",i," iterações"))
      return(x0)
    }
    if(i > Nmax){
      print(paste0("Não convergiu"))
      return(x0)
    }
    i = i + 1  
  }

[1] "convergiu com 128 iterações"

E se a gente aumentar o valor de \(\delta\).

  curve(f(x)+x*0,xlim=c(0,2))
  delta = 10
  Nmax = 10000
  epsilon = 0.00001
  x0 = 2.5
  i = 0
  repeat{
    points(x0,f(x0),pch=19,col="red")
    segments(x0,f(x0),x0 - delta*df(x0),f(x0 - delta*df(x0)))
    x0 = x0 - delta*df(x0)
    if(abs(df(x0))<epsilon){
      print(paste0("convergiu com ",i," iterações"))
      return(x0)
    }
    if(i > Nmax){
      print(paste0("Não convergiu"))
      return(x0)
    }
    i = i + 1  
  }

[1] "Não convergiu"

Gradiente Descendente em duas dimensões

Aqui vamos generlizar o problema para funções \(f: \mathbb{R}^2 \to \mathbb{R}\). Ou seja, para cada par orddenado \((x,y) \in \mathbb{R}^2\) a função \(f\) associa um ponto em \(\mathbb{R}\).

\[ \begin{array}{cccc} f: & \mathbb{R}^2 & \to & \mathbb{R}\\ & (x,y) & \to & f(x,y) \end{array} \]

Por exemplo, podemos aplicar o método do gradiente descendente para encontrar o ponto mínimo da função

\[ f(x,y) = 3x^2 + 5y^2 - x + 4y - 1 \]

library(plotly)

x <- seq(-5, 5, length = 50)
y <- seq(-5, 5, length = 50)
z <- outer(x, y, function(x, y) 3*x^2 + 5*y^2 - x + 4*y - 1)

plot_ly(
  x = x,
  y = y,
  z = z,
  type = "surface"
)

O que queremos responder é: qual o ponto \((x,y)\) onde \(f(x,y)\) assume seu valor mínimo?

A Idéia

A ideia é a mesma, mas em vez de caminhar na direção da derivada o caminho será na direção do gradiente da função \(f\) no ponto \(x_0\).

\[ \nabla f(x,y) = \left( \frac{\partial f}{\partial x}(x,y), \frac{\partial f}{\partial y}(x,y) \right) \]

O que precisamos saber de cálculo, além de calcular as derivadas parciais, é que o vetor gradiente sempre aponta para a direção de maior crescimento da função. Dessa forma, o passo que vamos dar será na direção oposta ao vetor gradiente.

O Algoritmo

Seja \(f: \mathbb{R}^2 \to \mathbb{R}\) uma função tal que é possível calcular suas derivadas parciais em todos os pontos do \(\mathbb{R}^2\).

1. Defina valores inicias para os hiperparâmetros \(\delta\), \(\varepsilon\) e \(N_{max}\).

2. Inicie \(i=0\) e \((x_0,y_0)\) como um ponto qualquer. Geralmente \((x_0,y_0)\) é definido de forma aleatória.

3. Calcule \(\nabla f(x_0,y_0) = \left(\frac{\partial f}{\partial x}(x_0,y_0),\frac{\partial f}{\partial y}(x_0,y_0)\right)\) e atualize \((x_0,y_0) = (x_0,y_0) - \delta \ \nabla f(x_0,y_0)\).

4. Incremente \(i = i + 1\) .

5. Se um dos critérios de parada for alcançado, retorne \((x_0,y_0)\):

   • \(|| \nabla f(x_0,y_0) || < \varepsilon\)

   • \(i > N_{max}\)

6. Se não, volte para o passo 3.

Um Exemplo no R

Vamos implementar o algoritmo para encontrar o mínimo de

\[ f(x,y) = 3x^2 + 5y^2 - x + 4y - 1 \] Vamos calcular as derivadas parciais para encontrar o vetor gradiente.

\[ \frac{\partial f}{\partial x} (x,y) = 6x - 1 \quad \text{ e } \quad \frac{\partial f}{\partial y} (x,y) = 10y + 4 \]

f2 = function(x,y){3*x^2 + 5*y^2 - x + 4*y - 1}
grad_f2 = function(x,y){c(6*x - 1 , 10*y + 4)}

grad_des2 = function(x0 = runif(1), y0 = runif(1), delta = 0.1, Nmax = 10000, epsilon = 0.00001){
  i = 0
  
  repeat{
    
    g_f2 = grad_f2(x0,y0)
    
    x0 = x0 - delta*g_f2[1]
    y0 = y0 - delta*g_f2[2]
    
    norma = sqrt(sum(g_f2^2))
      
    if(norma < epsilon){
      print(paste0("convergiu com ",i," iterações"))
      return(c(x0,y0))
    }
    if(i > Nmax){
      print(paste0("Não convergiu"))
      return(c(x0,y0))
    }
    i = i + 1  
  }
}

(ponto = grad_des2())

[1] "convergiu com 13 iterações"

[1]  0.1666673 -0.4000000

x <- seq(-5, 5, length = 50)
y <- seq(-5, 5, length = 50)
z <- outer(x, y, function(x, y) 3*x^2 + 5*y^2 - x + 4*y - 1)

# ponto
x0 <- ponto[1]
y0 <- ponto[2]
z0 <- f2(x0, y0)

plot_ly(
  x = x,
  y = y,
  z = z,
  type = "surface"
) %>%
  add_trace(
    x = x0,
    y = y0,
    z = z0,
    type = "scatter3d",
    mode = "markers",
    marker = list(
      color = "red",
      size = 6))

x0 = 4
y0 = 4
delta = 0.05
Nmax = 10000
epsilon = 0.00001

i = 0

todos_x = x0
todos_y = y0
  
  repeat{
    
    g_f2 = grad_f2(x0,y0)
    
    x0 = x0 - delta*g_f2[1]
    y0 = y0 - delta*g_f2[2]
    
    todos_x = c(todos_x,x0)
    todos_y = c(todos_y,y0)

    norma = sqrt(sum(g_f2^2))
      
    if(norma < epsilon){
      print(paste0("convergiu com ",i," iterações"))
      return(c(x0,y0))
    }
    if(i > Nmax){
      print(paste0("Não convergiu"))
      return(c(x0,y0))
    }
    i = i + 1  
  }

[1] "convergiu com 42 iterações"

x <- seq(-5, 5, length = 50)
y <- seq(-5, 5, length = 50)
z <- outer(x, y, function(x, y) 3*x^2 + 5*y^2 - x + 4*y - 1)

plot_ly(
  x = x,
  y = y,
  z = z,
  type = "surface"
) %>%
  add_trace(
    x = todos_x,
    y = todos_y,
    z = f2(todos_x,todos_y),
    type = "scatter3d",
    mode = "markers",
    marker = list(
      color = "red",
      size = 6))

O que pode acontecer se aumentarmos \(\delta\)?

x0 = 4
y0 = 4
delta = 0.2
Nmax = 10000
epsilon = 0.00001

i = 0

todos_x = x0
todos_y = y0
  
  repeat{
    
    g_f2 = grad_f2(x0,y0)
    
    x0 = x0 - delta*g_f2[1]
    y0 = y0 - delta*g_f2[2]
    
    todos_x = c(todos_x,x0)
    todos_y = c(todos_y,y0)

    norma = sqrt(sum(g_f2^2))
      
    if(norma < epsilon){
      print(paste0("convergiu com ",i," iterações"))
      return(c(x0,y0))
    }
    if(i > Nmax){
      print(paste0("Não convergiu"))
      return(c(x0,y0))
    }
    i = i + 1  
  }

[1] "Não convergiu"

tail(todos_x)

[1] 0.1666667 0.1666667 0.1666667 0.1666667 0.1666667 0.1666667

tail(todos_y)

[1] -4.8  4.0 -4.8  4.0 -4.8  4.0

x <- seq(-5, 5, length = 50)
y <- seq(-5, 5, length = 50)
z <- outer(x, y, function(x, y) 3*x^2 + 5*y^2 - x + 4*y - 1)

plot_ly(
  x = x,
  y = y,
  z = z,
  type = "surface"
) %>%
  add_trace(
    x = todos_x[1:10],
    y = todos_y[1:10],
    z = f2(todos_x[1:10],todos_y[1:10]),
    type = "scatter3d",
    mode = "markers",
    marker = list(
      color = "red",
      size = 6))

Gradiente Descendente - caso geral

Na prática, a função que queremos minimizar tem mais duas variáveis. O caso geral pode ser definido como:

\[ \begin{array}{cccc} f: & \mathbb{R}^m & \to & \mathbb{R}\\ & \mathbf{x} & \to & f(\mathbf{x}) \end{array} \] Aqui \(\mathbf{x}\) representa um vetor de dimensão \(m\): \[ \mathbf{x} = \left( x_1, x_2, \ldots, x_m \right) \]

A Idéia

Agora precisamos definir o gradiente em \(m\) dimensões:

\[ \nabla f(\mathbf{x}) = \left( \frac{\partial f}{\partial x_1}(\mathbf{x}), \frac{\partial f}{\partial x_2}(\mathbf{x}), \ldots , \frac{\partial f}{\partial x_m}(\mathbf{x}) \right) \]

O Algoritmo

Seja \(f: \mathbb{R}^m \to \mathbb{R}\) uma função tal que é possível calcular suas derivadas parciais em todos os pontos do \(\mathbb{R}^2\).

1. Defina valores inicias para os hiperparâmetros \(\delta\), \(\varepsilon\) e \(N_{max}\).

2. Inicie \(i=0\) e \(\mathbf{x}_0 \in \mathbb{R}^m\) como um ponto qualquer. Geralmente \(\mathbf{x}_0\) é definido de forma aleatória.

3. Calcule \(\nabla f(\mathbf{x}_0)\) e atualize \(\mathbf{x}_0 = \mathbf{x}_0 - \delta \ \nabla f(\mathbf{x}_0)\).

4. Incremente \(i = i + 1\) .

5. Se um dos critérios de parada for alcançado, retorne \((x_0,y_0)\):

   • \(|| \nabla f(\mathbf{x}_0) || < \varepsilon\)

   • \(i > N_{max}\)

6. Se não, volte para o passo 3.