Posit AI Weblog: tocha para otimização


Até agora, todos torch os casos de uso que discutimos aqui foram de aprendizado profundo. Entretanto, seu recurso de diferenciação automática é útil em outras áreas. Um exemplo proeminente é a otimização numérica: podemos usar torch para encontrar o mínimo de uma função.

Na verdade, a minimização da função é exatamente o que acontece no treinamento de uma rede neural. Mas aí, a função em questão normalmente é demasiado complexa para sequer imaginarmos encontrar os seus mínimos analiticamente. A otimização numérica visa construir ferramentas para lidar exatamente com essa complexidade. Para esse fim, porém, parte de funções que são muito menos compostas. Em vez disso, são feitos à mão para apresentar desafios específicos.

Este publish é uma primeira introdução à otimização numérica com torch. As principais conclusões são a existência e a utilidade de seu otimizador L-BFGS, bem como o impacto da execução do L-BFGS com pesquisa de linha. Como complemento divertido, mostramos um exemplo de otimização restrita, onde uma restrição é aplicada por meio de uma função de penalidade quadrática.

Para aquecer, fazemos um desvio, minimizando uma função “nós mesmos” usando nada além de tensores. Porém, isso será relevante mais tarde, pois o processo geral ainda será o mesmo. Todas as mudanças estarão relacionadas à integração de optimizerse suas capacidades.

Minimização de função, abordagem DYI

Para ver como podemos minimizar uma função “manualmente”, vamos tentar o icônico Função Rosenbrock. Esta é uma função com duas variáveis:

(f(x_1, x_2) = (a – x_1)^2 + b * (x_2 – x_1^2)^2 )

com (um) e (b) parâmetros configuráveis ​​geralmente definidos como 1 e 5, respectivamente.

Em R:

library(torch)

a <- 1
b <- 5

rosenbrock <- perform(x) {
  x1 <- x(1)
  x2 <- x(2)
  (a - x1)^2 + b * (x2 - x1^2)^2
}

Seu mínimo está localizado em (1,1), dentro de um vale estreito cercado por falésias íngremes e alucinantes:


Posit AI Weblog: tocha para otimização

Figura 1: Função Rosenbrock.

Nosso objetivo e estratégia são os seguintes.

Queremos encontrar os valores (x_1) e (x_2) para o qual a função atinge seu mínimo. Temos que começar em algum lugar; e de onde quer que isso nos leve no gráfico, seguimos o negativo do gradiente “para baixo”, descendo para regiões de valor de função consecutivamente menor.

Concretamente, em cada iteração, tomamos o atual ((x1,x2)) ponto, calcule o valor da função, bem como o gradiente, e subtraia alguma fração deste último para chegar a um novo ((x1,x2)) candidato. Este processo continua até atingirmos o mínimo – o gradiente é zero – ou a melhoria ficar abaixo de um limite escolhido.

Aqui está o código correspondente. Sem nenhuma razão especial, começamos em (-1,1) . A taxa de aprendizagem (a fração do gradiente a ser subtraída) precisa de alguma experimentação. (Experimente 0,1 e 0,001 para ver seu impacto.)

num_iterations <- 1000

# fraction of the gradient to subtract 
lr <- 0.01

# perform enter (x1,x2)
# that is the tensor w.r.t. which we'll have torch compute the gradient
x_star <- torch_tensor(c(-1, 1), requires_grad = TRUE)

for (i in 1:num_iterations) {

  if (i %% 100 == 0) cat("Iteration: ", i, "n")

  # name perform
  worth <- rosenbrock(x_star)
  if (i %% 100 == 0) cat("Worth is: ", as.numeric(worth), "n")

  # compute gradient of worth w.r.t. params
  worth$backward()
  if (i %% 100 == 0) cat("Gradient is: ", as.matrix(x_star$grad), "nn")

  # handbook replace
  with_no_grad({
    x_star$sub_(lr * x_star$grad)
    x_star$grad$zero_()
  })
}
Iteration:  100 
Worth is:  0.3502924 
Gradient is:  -0.667685 -0.5771312 

Iteration:  200 
Worth is:  0.07398106 
Gradient is:  -0.1603189 -0.2532476 

...
...

Iteration:  900 
Worth is:  0.0001532408 
Gradient is:  -0.004811743 -0.009894371 

Iteration:  1000 
Worth is:  6.962555e-05 
Gradient is:  -0.003222887 -0.006653666 

Embora isso funcione, na verdade serve para ilustrar o princípio. Com torch fornecendo vários algoritmos de otimização comprovados, não há necessidade de calcular manualmente o candidato (mathbf{x}) valores.

Minimização de função com torch otimizadores

Em vez disso, deixamos um torch otimizador atualiza o candidato (mathbf{x}) para nós. Habitualmente, nossa primeira tentativa é Adão.

Adão

Com Adam, a otimização ocorre muito mais rápido. Verdade seja dita, escolher uma boa taxa de aprendizagem ainda requer experimentação não negligenciável. (Experimente a taxa de aprendizagem padrão, 0,001, para comparação.)

num_iterations <- 100

x_star <- torch_tensor(c(-1, 1), requires_grad = TRUE)

lr <- 1
optimizer <- optim_adam(x_star, lr)

for (i in 1:num_iterations) {
  
  if (i %% 10 == 0) cat("Iteration: ", i, "n")
  
  optimizer$zero_grad()
  worth <- rosenbrock(x_star)
  if (i %% 10 == 0) cat("Worth is: ", as.numeric(worth), "n")
  
  worth$backward()
  optimizer$step()
  
  if (i %% 10 == 0) cat("Gradient is: ", as.matrix(x_star$grad), "nn")
  
}
Iteration:  10 
Worth is:  0.8559565 
Gradient is:  -1.732036 -0.5898831 

Iteration:  20 
Worth is:  0.1282992 
Gradient is:  -3.22681 1.577383 

...
...

Iteration:  90 
Worth is:  4.003079e-05 
Gradient is:  -0.05383469 0.02346456 

Iteration:  100 
Worth is:  6.937736e-05 
Gradient is:  -0.003240437 -0.006630421 

Levamos cerca de cem iterações para chegar a um valor decente. Isso é muito mais rápido do que a abordagem handbook acima, mas ainda assim bastante. Felizmente, novas melhorias são possíveis.

L-BFGS

Entre os muitos torch otimizadores comumente usados ​​em aprendizagem profunda (Adam, AdamW, RMSprop…), existe um “estranho”, muito mais conhecido na otimização numérica clássica do que no espaço de redes neurais: L-BFGS, também conhecido como BFGS de memória limitadauma implementação com otimização de memória do Algoritmo de otimização Broyden – Fletcher – Goldfarb – Shanno (BFGS).

O BFGS é talvez o mais amplamente utilizado entre os chamados algoritmos de otimização de segunda ordem Quasi-Newton. Ao contrário da família de algoritmos de primeira ordem que, ao decidir sobre uma direção de descida, utilizam apenas informações de gradiente, os algoritmos de segunda ordem levam adicionalmente em consideração informações de curvatura. Para esse fim, os métodos exatos de Newton, na verdade, calculam o Hessiano (uma operação cara), enquanto os métodos quase-Newton evitam esse custo e, em vez disso, recorrem à aproximação iterativa.

Olhando para os contornos da função Rosenbrock, com o seu vale estreito e prolongado, não é difícil imaginar que a informação da curvatura possa fazer a diferença. E, como você verá em um segundo, realmente acontece. Antes, porém, uma observação sobre o código. Ao usar L-BFGS, é necessário envolver a chamada de função e a avaliação de gradiente em um encerramento (calc_loss()no trecho abaixo), para que possam ser chamados várias vezes por iteração. Você pode se convencer de que o encerramento é, de fato, inserido repetidamente, inspecionando a saída tagarela deste trecho de código:

num_iterations <- 3

x_star <- torch_tensor(c(-1, 1), requires_grad = TRUE)

optimizer <- optim_lbfgs(x_star)

calc_loss <- perform() {

  optimizer$zero_grad()

  worth <- rosenbrock(x_star)
  cat("Worth is: ", as.numeric(worth), "n")

  worth$backward()
  cat("Gradient is: ", as.matrix(x_star$grad), "nn")
  worth

}

for (i in 1:num_iterations) {
  cat("Iteration: ", i, "n")
  optimizer$step(calc_loss)
}
Iteration:  1 
Worth is:  4 
Gradient is:  -4 0 

Worth is:  6 
Gradient is:  -2 10 

...
...

Worth is:  0.04880721 
Gradient is:  -0.262119 -0.1132655 

Worth is:  0.0302862 
Gradient is:  1.293824 -0.7403332 

Iteration:  2 
Worth is:  0.01697086 
Gradient is:  0.3468466 -0.3173429 

Worth is:  0.01124081 
Gradient is:  0.2420997 -0.2347881 

...
...

Worth is:  1.111701e-09 
Gradient is:  0.0002865837 -0.0001251698 

Worth is:  4.547474e-12 
Gradient is:  -1.907349e-05 9.536743e-06 

Iteration:  3 
Worth is:  4.547474e-12 
Gradient is:  -1.907349e-05 9.536743e-06 

Embora tenhamos executado o algoritmo em três iterações, o valor superb é realmente alcançado após duas. Vendo como isso funcionou bem, tentamos L-BFGS em uma função mais difícil, chamada florpor razões bastante evidentes.

(Ainda) mais diversão com L-BFGS

Aqui está o flor função. Matematicamente, seu mínimo está próximo (0,0)mas tecnicamente a função em si é indefinida em (0,0)desde o atan2 usado na função não está definido lá.

a <- 1
b <- 1
c <- 4

flower <- perform(x) {
  a * torch_norm(x) + b * torch_sin(c * torch_atan2(x(2), x(1)))
}

Função flor.

Figura 2: Função flor.

Executamos o mesmo código acima, começando em (20,20) desta vez.

num_iterations <- 3

x_star <- torch_tensor(c(20, 0), requires_grad = TRUE)

optimizer <- optim_lbfgs(x_star)

calc_loss <- perform() {

  optimizer$zero_grad()

  worth <- flower(x_star)
  cat("Worth is: ", as.numeric(worth), "n")

  worth$backward()
  cat("Gradient is: ", as.matrix(x_star$grad), "n")
  
  cat("X is: ", as.matrix(x_star), "nn")
  
  worth

}

for (i in 1:num_iterations) {
  cat("Iteration: ", i, "n")
  optimizer$step(calc_loss)
}
Iteration:  1 
Worth is:  28.28427 
Gradient is:  0.8071069 0.6071068 
X is:  20 20 

...
...

Worth is:  19.33546 
Gradient is:  0.8100872 0.6188223 
X is:  12.957 14.68274 

...
...

Worth is:  18.29546 
Gradient is:  0.8096464 0.622064 
X is:  12.14691 14.06392 

...
...

Worth is:  9.853705 
Gradient is:  0.7546976 0.7025688 
X is:  5.763702 8.895616 

Worth is:  2635.866 
Gradient is:  -0.7407354 -0.6717985 
X is:  -1949.697 -1773.551 

Iteration:  2 
Worth is:  1333.113 
Gradient is:  -0.7413024 -0.6711776 
X is:  -985.4553 -897.5367 

Worth is:  30.16862 
Gradient is:  -0.7903821 -0.6266789 
X is:  -21.02814 -21.72296 

Worth is:  1281.39 
Gradient is:  0.7544561 0.6563575 
X is:  964.0121 843.7817 

Worth is:  628.1306 
Gradient is:  0.7616636 0.6480014 
X is:  475.7051 409.7372 

Worth is:  4965690 
Gradient is:  -0.7493951 -0.662123 
X is:  -3721262 -3287901 

Worth is:  2482306 
Gradient is:  -0.7503822 -0.6610042 
X is:  -1862675 -1640817 

Worth is:  8.61863e+11 
Gradient is:  0.7486113 0.6630091 
X is:  645200412672 571423064064 

Worth is:  430929412096 
Gradient is:  0.7487153 0.6628917 
X is:  322643460096 285659529216 

Worth is:  Inf 
Gradient is:  0 0 
X is:  -2.826342e+19 -2.503904e+19 

Iteration:  3 
Worth is:  Inf 
Gradient is:  0 0 
X is:  -2.826342e+19 -2.503904e+19 

Este foi um sucesso menor. No início, a perda diminui bastante, mas, de repente, a estimativa ultrapassa dramaticamente e continua oscilando entre o espaço exterior negativo e positivo para sempre.

Felizmente, há algo que podemos fazer.

Tomado isoladamente, o que um método Quasi-Newton como o L-BFGS faz é determinar a melhor direção de descida. Porém, como acabamos de ver, uma boa direção não é suficiente. Com a função floral, onde quer que estejamos, o caminho superb leva ao desastre se permanecermos nele por tempo suficiente. Assim, precisamos de um algoritmo que avalie cuidadosamente não apenas para onde ir, mas também até onde ir.

Por esta razão, as implementações L-BFGS comumente incorporam pesquisa de linhaisto é, um conjunto de regras que indicam se um comprimento de passo proposto é bom ou deve ser melhorado.

Especificamente, torchO otimizador L-BFGS de implementa o Fortes condições de Wolfe. Executamos novamente o código acima, alterando apenas duas linhas. Mais importante ainda, aquele onde o otimizador é instanciado:

optimizer <- optim_lbfgs(x_star, line_search_fn = "strong_wolfe")

E em segundo lugar, desta vez descobri que após a terceira iteração, a perda continuou a diminuir por um tempo, então deixei funcionar por cinco iterações. Aqui está a saída:

Iteration:  1 
...
...

Worth is:  -0.8838741 
Gradient is:  3.742207 7.521572 
X is:  0.09035123 -0.03220009 

Worth is:  -0.928809 
Gradient is:  1.464702 0.9466625 
X is:  0.06564617 -0.026706 

Iteration:  2 
...
...

Worth is:  -0.9991404 
Gradient is:  39.28394 93.40318 
X is:  0.0006493925 -0.0002656128 

Worth is:  -0.9992246 
Gradient is:  6.372203 12.79636 
X is:  0.0007130796 -0.0002947929 

Iteration:  3 
...
...

Worth is:  -0.9997789 
Gradient is:  3.565234 5.995832 
X is:  0.0002042478 -8.457939e-05 

Worth is:  -0.9998025 
Gradient is:  -4.614189 -13.74602 
X is:  0.0001822711 -7.553725e-05 

Iteration:  4 
...
...

Worth is:  -0.9999917 
Gradient is:  -382.3041 -921.4625 
X is:  -6.320081e-06 2.614706e-06 

Worth is:  -0.9999923 
Gradient is:  -134.0946 -321.2681 
X is:  -6.921942e-06 2.865841e-06 

Iteration:  5 
...
...

Worth is:  -0.9999999 
Gradient is:  -3446.911 -8320.007 
X is:  -7.267168e-08 3.009783e-08 

Worth is:  -0.9999999 
Gradient is:  -3419.361 -8253.501 
X is:  -7.404627e-08 3.066708e-08 

Ainda não está perfeito, mas muito melhor.

Finalmente, vamos dar um passo adiante. Podemos usar torch para otimização restrita?

Penalidade quadrática para otimização restrita

Na otimização restrita, ainda buscamos um mínimo, mas esse mínimo não pode residir em qualquer lugar: sua localização precisa atender a uma série de condições adicionais. No jargão da otimização, tem que ser viável.

Para ilustrar, permanecemos com a função flower, mas adicionamos uma restrição: (mathbf{x}) tem que estar fora de um círculo de raio (quadrado(2))centrado na origem. Formalmente, isso produz a restrição de desigualdade

(2 – {x_1}^2 – {x_2}^2 <= 0 )

Uma maneira de minimizar flor e ainda assim, ao mesmo tempo, honrar a restrição é usar uma função de penalidade. Com métodos de penalidade, o valor a ser minimizado é uma soma de duas coisas: a saída da função alvo e uma penalidade que reflete uma possível violação da restrição. Uso de um quadrático penapor exemplo, resulta na adição de um múltiplo do quadrado da saída da função de restrição:

# x^2 + y^2 >= 2
# 2 - x^2 - y^2 <= 0
constraint <- perform(x) 2 - torch_square(torch_norm(x))

# quadratic penalty
penalty <- perform(x) torch_square(torch_max(constraint(x), different = 0))

A priori, não podemos saber quão grande deve ser esse múltiplo para impor a restrição. Portanto, a otimização prossegue iterativamente. Começamos com um pequeno multiplicador, (1)digamos, e aumente-o enquanto a restrição ainda for violada:

penalty_method <- perform(f, p, x, k_max, rho = 1, gamma = 2, num_iterations = 1) {

  for (okay in 1:k_max) {
    cat("Beginning step: ", okay, ", rho = ", rho, "n")

    reduce(f, p, x, rho, num_iterations)

    cat("Worth: ",  as.numeric(f(x)), "n")
    cat("X: ",  as.matrix(x), "n")
    
    current_penalty <- as.numeric(p(x))
    cat("Penalty: ", current_penalty, "n")
    if (current_penalty == 0) break
    
    rho <- rho * gamma
  }

}

reduce()chamado de penalty_method()segue os procedimentos usuais, mas agora minimiza a soma das saídas da função de penalidade alvo e ponderada:

reduce <- perform(f, p, x, rho, num_iterations) {

  calc_loss <- perform() {
    optimizer$zero_grad()
    worth <- f(x) + rho * p(x)
    worth$backward()
    worth
  }

  for (i in 1:num_iterations) {
    cat("Iteration: ", i, "n")
    optimizer$step(calc_loss)
  }

}

Desta vez, partimos de um valor de perda alvo baixo, mas inviável. Com mais uma mudança no L-BFGS padrão (ou seja, uma diminuição na tolerância), vemos o algoritmo saindo com sucesso após vinte e duas iterações, no ponto (0.5411692,1.306563).

x_star <- torch_tensor(c(0.5, 0.5), requires_grad = TRUE)

optimizer <- optim_lbfgs(x_star, line_search_fn = "strong_wolfe", tolerance_change = 1e-20)

penalty_method(flower, penalty, x_star, k_max = 30)
Beginning step:  1 , rho =  1 
Iteration:  1 
Worth:  0.3469974 
X:  0.5154735 1.244463 
Penalty:  0.03444662 

Beginning step:  2 , rho =  2 
Iteration:  1 
Worth:  0.3818618 
X:  0.5288152 1.276674 
Penalty:  0.008182613 

Beginning step:  3 , rho =  4 
Iteration:  1 
Worth:  0.3983252 
X:  0.5351116 1.291886 
Penalty:  0.001996888 

...
...

Beginning step:  20 , rho =  524288 
Iteration:  1 
Worth:  0.4142133 
X:  0.5411959 1.306563 
Penalty:  3.552714e-13 

Beginning step:  21 , rho =  1048576 
Iteration:  1 
Worth:  0.4142134 
X:  0.5411956 1.306563 
Penalty:  1.278977e-13 

Beginning step:  22 , rho =  2097152 
Iteration:  1 
Worth:  0.4142135 
X:  0.5411962 1.306563 
Penalty:  0 

Conclusão

Resumindo, tivemos uma primeira impressão da eficácia do torchotimizador L-BFGS do, especialmente quando usado com pesquisa de linha Sturdy-Wolfe. Na verdade, na otimização numérica – ao contrário da aprendizagem profunda, onde a velocidade computacional é muito mais um problema – quase nunca há uma razão para não use L-BFGS com pesquisa de linha.

Em seguida, tivemos uma ideia de como fazer otimização restrita, uma tarefa que surge em muitas aplicações do mundo actual. Nesse sentido, esta postagem parece muito mais um começo do que um balanço. Há muito a explorar, desde o ajuste geral do método – quando o L-BFGS é adequado para um problema? – através da eficácia computacional para aplicabilidade a diferentes espécies de redes neurais. Escusado será dizer que se isso o inspira a realizar seus próprios experimentos e/ou se você usa o L-BFGS em seus próprios projetos, adoraríamos ouvir seus comentários!

Obrigado por ler!

Apêndice

Código de plotagem da função Rosenbrock

library(tidyverse)

a <- 1
b <- 5

rosenbrock <- perform(x) {
  x1 <- x(1)
  x2 <- x(2)
  (a - x1)^2 + b * (x2 - x1^2)^2
}

df <- expand_grid(x1 = seq(-2, 2, by = 0.01), x2 = seq(-2, 2, by = 0.01)) %>%
  rowwise() %>%
  mutate(x3 = rosenbrock(c(x1, x2))) %>%
  ungroup()

ggplot(knowledge = df,
       aes(x = x1,
           y = x2,
           z = x3)) +
  geom_contour_filled(breaks = as.numeric(torch_logspace(-3, 3, steps = 50)),
                      present.legend = FALSE) +
  theme_minimal() +
  scale_fill_viridis_d(path = -1) +
  theme(facet.ratio = 1)

Código de plotagem de função flor

a <- 1
b <- 1
c <- 4

flower <- perform(x) {
  a * torch_norm(x) + b * torch_sin(c * torch_atan2(x(2), x(1)))
}

df <- expand_grid(x = seq(-3, 3, by = 0.05), y = seq(-3, 3, by = 0.05)) %>%
  rowwise() %>%
  mutate(z = flower(torch_tensor(c(x, y))) %>% as.numeric()) %>%
  ungroup()

ggplot(knowledge = df,
       aes(x = x,
           y = y,
           z = z)) +
  geom_contour_filled(present.legend = FALSE) +
  theme_minimal() +
  scale_fill_viridis_d(path = -1) +
  theme(facet.ratio = 1)

Foto de Michael Trimble sobre Remover respingo

Deixe um comentário

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *