Notebook com códigos R para a implementação do Multi-Layer Perceptron - ERAMIA 2020

Código baseado na implementação do professor Rodrigo Mello - ICMC/USP

https://www.youtube.com/watch?v=FSvD2HT0Zfg

Primeiro vamos implementar uma função de ativação

funcao.ativacao <- function(v){

  # Função logística
  y <- 1 / (1 + exp(-v))

  return(y)
}

Vamos também precisar da derivada da função de ativação

der.funcao.ativacao <- function(y){

  # Derivada da logística
  derivada <- y * (1 - y)

  return(derivada)
}

Vamos criar uma arquitetura para nossa MLP

arquitetura <- function(num.entrada, num.escondida, num.saida,
                        funcao.ativacao, der.funcao.ativacao){

  arq <- list()

  # Parametros da rede    
  arq$num.entrada <- num.entrada
  arq$num.escondida <- num.escondida
  arq$num.saida <- num.saida
  arq$funcao.ativacao <- funcao.ativacao
  arq$der.funcao.ativacao <- der.funcao.ativacao

  # 2 neuronios na camada escondida
  # 
  #       Ent1    Ent2   Bias 
  # 1     w11     w12    w13
  # 2     w21     w22    w23

  # Pesos conectando entrada e escondida
  num.pesos.entrada.escondida <- (num.entrada+1)*num.escondida
  arq$escondida <- matrix(runif(min=-0.5,max=0.5, num.pesos.entrada.escondida),
                                nrow=num.escondida, ncol=num.entrada+1)

  # Pesos conectando escondida e saida
  num.pesos.escondida.saida <- (num.escondida+1)*num.saida
  arq$saida <- matrix(runif(min=-0.5,max=0.5,  num.pesos.escondida.saida),
                            nrow=num.saida, ncol=num.escondida+1)


  return(arq)
}

Precisamos de um código para a fase de propagação da MLP

mlp.propagacao <- function(arq, exemplo){

  # Entrada -> Cama Escondida
  v.entrada.escondida <- arq$escondida %*% as.numeric(c(exemplo,1))
  y.entrada.escondida <- arq$funcao.ativacao(v.entrada.escondida)

  # Camada Escondida -> Camada de Saida
  v.escondida.saida <- arq$saida %*% c(y.entrada.escondida,1)
  y.escondida.saida <- arq$funcao.ativacao(v.escondida.saida)

  # Resultados
  resultado <- list()
  resultado$v.entrada.escondida <- v.entrada.escondida
  resultado$y.entrada.escondida <- y.entrada.escondida
  resultado$v.escondida.saida <- v.escondida.saida
  resultado$y.escondida.saida <- y.escondida.saida

  return(resultado)
}

Agora o código para a fase de treinamento da MLP, usando o algoritmo Back-propagation

mlp.retropropagacao <- function(arq, dados, n, limiar){

  erroQuadratico <- 2 * limiar
  epocas <- 0

  # Treina eqto o erro quadratico for maior que um limiar
  while(erroQuadratico > limiar){
    erroQuadratico <- 0

    # Treino para todos os exemplos (epoca)
    for(i in 1:nrow(dados)){

      # Pego um exemplo de entrada
      x.entrada <- dados[i,1:arq$num.entrada]
      x.saida <- dados[i,ncol(dados)]

      # Pego a saida da rede para o exemplo
      resultado <- mlp.propagacao(arq,x.entrada)
      y <- resultado$y.escondida.saida

      # Calculo do erro para o exemplo
      erro <- x.saida - y

      # Soma erro quadratico
      erroQuadratico <- erroQuadratico + erro*erro

      # Gradiente local no neuronio de saida
      # erro * derivada da funcao de ativacao
      grad.local.saida <- erro * arq$der.funcao.ativacao(y)

      # Gradiente local no neuronio escondido
      # derivada da funcao de ativacao no neuronio escondido * soma dos gradientes
      # locais dos neuronios conectados na proxima camada * pesos conectando a camada
      # escondida com a saida
      pesos.saida <- arq$saida[,1:arq$num.escondida]
      grad.local.escondida <-
        as.numeric(arq$der.funcao.ativacao(resultado$y.entrada.escondida)) *
        (grad.local.saida %*% pesos.saida)

      # Ajuste dos pesos
      # Saida
      arq$saida <- arq$saida + n * (grad.local.saida %*%
                                     c(resultado$y.entrada.escondida,1))
      # Escondida
      arq$escondida <- arq$escondida + n * (t(grad.local.escondida) %*%
                                             as.numeric(c(x.entrada,1)))
    } # Fim for(i in 1:nrow(dados))

    erroQuadratico <- erroQuadratico / nrow(dados)
    cat("Erro Quadratico Medio = ",erroQuadratico, "\n")
    epocas <- epocas+1
    
  } # Fim while(erroQuadratico > limiar)

  retorno <- list()
  retorno$arq <- arq
  retorno$epocas <- epocas

  return(retorno)
}

Leitura de uma tabela com os dados do problema XOR

dados <- read.table('XOR.txt')
dados

Vamos treinar nossa MLP

arq <- arquitetura(2,2,1,funcao.ativacao, der.funcao.ativacao)
modelo <- mlp.retropropagacao(arq,dados,0.1,1e-3)

Vamos testar em dados novos

retorno <- mlp.propagacao(modelo$arq,c(0,1))
retorno$y.escondida.saida

mlp.propagacao(modelo$arq,c(1,0))$y.escondida.saida

mlp.propagacao(modelo$arq,c(1,1))$y.escondida.saida

mlp.propagacao(modelo$arq,c(0,0))$y.escondida.saida

Leitura de dados sobre risco de crédito.

Queremos prever, com base nas variáveis de entrada, se ocorrerá ou não um calote em 10 anos

dataset <- read.csv("creditset.csv")
head(dataset)

# clientid: identificação do cliente
# income: renda anual
# age: idade
# loan: empréstimo com data de no mínimo 10 anos atrás
# LTI: razão entre valor do empréstimo e renda anual
# default10yr: se ocorrerá (1) ou não (0) um calote em 10 anos

Vamos utilizar como variáveis de entrada LTI e age

dados <- dataset[,c(3,5,6)]
dados[,1:2] <- scale(dados[,1:2]) # normalização dos dados (media 0 e desvio 1)

Vamos escolher aleatoriamente dados para treino e teste O conjunto de dados já está randomizado. Assim, Vamos pegar os primeiros 1400 exemplos para treino e o restante para teste

dados.treino <- dados[1:1400,]
dados.teste <- dados[1401:2000,]

Vamos treinar nossa rede com 4 neurônios na camada escondida

arq <- arquitetura(2,4,1,funcao.ativacao, der.funcao.ativacao)
modelo <- mlp.retropropagacao(arq,dados.treino,0.3,1e-3)

Fazendo predicoes para cada exemplo de teste

predicoes <- vector()
for(i in 1:nrow(dados.teste)){

  pred <- mlp.propagacao(modelo$arq,dados.teste[i,1:2])$y.escondida.saida
    
  predicoes <- c(predicoes,pred)
}

Criando uma matriz para comparação dos resultados

matriz.comparacao <- cbind(dados.teste[,3],predicoes)
colnames(matriz.comparacao) <- c('V','P')
matriz.comparacao

Matriz de confusão com o arredondamento das predições

table(matriz.comparacao[,1],round(matriz.comparacao[,2]))
LS0tCnRpdGxlOiAiUiBOb3RlYm9vayAtIE11bHRpLUxheWVyIFBlcmNlcHRyb24iCm91dHB1dDogaHRtbF9ub3RlYm9vawotLS0KCiMjIE5vdGVib29rIGNvbSBjw7NkaWdvcyBSIHBhcmEgYSBpbXBsZW1lbnRhw6fDo28gZG8gTXVsdGktTGF5ZXIgUGVyY2VwdHJvbiAtIEVSQU1JQSAyMDIwCgpDw7NkaWdvIGJhc2VhZG8gbmEgaW1wbGVtZW50YcOnw6NvIGRvIHByb2Zlc3NvciBSb2RyaWdvIE1lbGxvIC0gSUNNQy9VU1AKCmh0dHBzOi8vd3d3LnlvdXR1YmUuY29tL3dhdGNoP3Y9RlN2RDJIVDBaZmcgCgpQcmltZWlybyB2YW1vcyBpbXBsZW1lbnRhciB1bWEgZnVuw6fDo28gZGUgYXRpdmHDp8OjbwpgYGB7cn0KZnVuY2FvLmF0aXZhY2FvIDwtIGZ1bmN0aW9uKHYpewoKICAjIEZ1bsOnw6NvIGxvZ8Otc3RpY2EKICB5IDwtIDEgLyAoMSArIGV4cCgtdikpCgogIHJldHVybih5KQp9CmBgYAoKClZhbW9zIHRhbWLDqW0gcHJlY2lzYXIgZGEgZGVyaXZhZGEgZGEgZnVuw6fDo28gZGUgYXRpdmHDp8OjbwpgYGB7cn0KZGVyLmZ1bmNhby5hdGl2YWNhbyA8LSBmdW5jdGlvbih5KXsKCiAgIyBEZXJpdmFkYSBkYSBsb2fDrXN0aWNhCiAgZGVyaXZhZGEgPC0geSAqICgxIC0geSkKCiAgcmV0dXJuKGRlcml2YWRhKQp9CmBgYAoKClZhbW9zIGNyaWFyIHVtYSBhcnF1aXRldHVyYSBwYXJhIG5vc3NhIE1MUApgYGB7cn0KYXJxdWl0ZXR1cmEgPC0gZnVuY3Rpb24obnVtLmVudHJhZGEsIG51bS5lc2NvbmRpZGEsIG51bS5zYWlkYSwKICAgICAgICAgICAgICAgICAgICAgICAgZnVuY2FvLmF0aXZhY2FvLCBkZXIuZnVuY2FvLmF0aXZhY2FvKXsKCiAgYXJxIDwtIGxpc3QoKQoKICAjIFBhcmFtZXRyb3MgZGEgcmVkZSAgICAKICBhcnEkbnVtLmVudHJhZGEgPC0gbnVtLmVudHJhZGEKICBhcnEkbnVtLmVzY29uZGlkYSA8LSBudW0uZXNjb25kaWRhCiAgYXJxJG51bS5zYWlkYSA8LSBudW0uc2FpZGEKICBhcnEkZnVuY2FvLmF0aXZhY2FvIDwtIGZ1bmNhby5hdGl2YWNhbwogIGFycSRkZXIuZnVuY2FvLmF0aXZhY2FvIDwtIGRlci5mdW5jYW8uYXRpdmFjYW8KCiAgIyAyIG5ldXJvbmlvcyBuYSBjYW1hZGEgZXNjb25kaWRhCiAgIyAKICAjICAgICAgIEVudDEgICAgRW50MiAgIEJpYXMgCiAgIyAxICAgICB3MTEgICAgIHcxMiAgICB3MTMKICAjIDIgICAgIHcyMSAgICAgdzIyICAgIHcyMwoKICAjIFBlc29zIGNvbmVjdGFuZG8gZW50cmFkYSBlIGVzY29uZGlkYQogIG51bS5wZXNvcy5lbnRyYWRhLmVzY29uZGlkYSA8LSAobnVtLmVudHJhZGErMSkqbnVtLmVzY29uZGlkYQogIGFycSRlc2NvbmRpZGEgPC0gbWF0cml4KHJ1bmlmKG1pbj0tMC41LG1heD0wLjUsIG51bS5wZXNvcy5lbnRyYWRhLmVzY29uZGlkYSksCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgbnJvdz1udW0uZXNjb25kaWRhLCBuY29sPW51bS5lbnRyYWRhKzEpCgogICMgUGVzb3MgY29uZWN0YW5kbyBlc2NvbmRpZGEgZSBzYWlkYQogIG51bS5wZXNvcy5lc2NvbmRpZGEuc2FpZGEgPC0gKG51bS5lc2NvbmRpZGErMSkqbnVtLnNhaWRhCiAgYXJxJHNhaWRhIDwtIG1hdHJpeChydW5pZihtaW49LTAuNSxtYXg9MC41LCAgbnVtLnBlc29zLmVzY29uZGlkYS5zYWlkYSksCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBucm93PW51bS5zYWlkYSwgbmNvbD1udW0uZXNjb25kaWRhKzEpCgoKICByZXR1cm4oYXJxKQp9CmBgYAoKClByZWNpc2Ftb3MgZGUgdW0gY8OzZGlnbyBwYXJhIGEgZmFzZSBkZSBwcm9wYWdhw6fDo28gZGEgTUxQCmBgYHtyfQptbHAucHJvcGFnYWNhbyA8LSBmdW5jdGlvbihhcnEsIGV4ZW1wbG8pewoKICAjIEVudHJhZGEgLT4gQ2FtYSBFc2NvbmRpZGEKICB2LmVudHJhZGEuZXNjb25kaWRhIDwtIGFycSRlc2NvbmRpZGEgJSolIGFzLm51bWVyaWMoYyhleGVtcGxvLDEpKQogIHkuZW50cmFkYS5lc2NvbmRpZGEgPC0gYXJxJGZ1bmNhby5hdGl2YWNhbyh2LmVudHJhZGEuZXNjb25kaWRhKQoKICAjIENhbWFkYSBFc2NvbmRpZGEgLT4gQ2FtYWRhIGRlIFNhaWRhCiAgdi5lc2NvbmRpZGEuc2FpZGEgPC0gYXJxJHNhaWRhICUqJSBjKHkuZW50cmFkYS5lc2NvbmRpZGEsMSkKICB5LmVzY29uZGlkYS5zYWlkYSA8LSBhcnEkZnVuY2FvLmF0aXZhY2FvKHYuZXNjb25kaWRhLnNhaWRhKQoKICAjIFJlc3VsdGFkb3MKICByZXN1bHRhZG8gPC0gbGlzdCgpCiAgcmVzdWx0YWRvJHYuZW50cmFkYS5lc2NvbmRpZGEgPC0gdi5lbnRyYWRhLmVzY29uZGlkYQogIHJlc3VsdGFkbyR5LmVudHJhZGEuZXNjb25kaWRhIDwtIHkuZW50cmFkYS5lc2NvbmRpZGEKICByZXN1bHRhZG8kdi5lc2NvbmRpZGEuc2FpZGEgPC0gdi5lc2NvbmRpZGEuc2FpZGEKICByZXN1bHRhZG8keS5lc2NvbmRpZGEuc2FpZGEgPC0geS5lc2NvbmRpZGEuc2FpZGEKCiAgcmV0dXJuKHJlc3VsdGFkbykKfQpgYGAKCgpBZ29yYSBvIGPDs2RpZ28gcGFyYSBhIGZhc2UgZGUgdHJlaW5hbWVudG8gZGEgTUxQLCB1c2FuZG8gbyBhbGdvcml0bW8gQmFjay1wcm9wYWdhdGlvbgpgYGB7cn0KbWxwLnJldHJvcHJvcGFnYWNhbyA8LSBmdW5jdGlvbihhcnEsIGRhZG9zLCBuLCBsaW1pYXIpewoKICBlcnJvUXVhZHJhdGljbyA8LSAyICogbGltaWFyCiAgZXBvY2FzIDwtIDAKCiAgIyBUcmVpbmEgZXF0byBvIGVycm8gcXVhZHJhdGljbyBmb3IgbWFpb3IgcXVlIHVtIGxpbWlhcgogIHdoaWxlKGVycm9RdWFkcmF0aWNvID4gbGltaWFyKXsKICAgIGVycm9RdWFkcmF0aWNvIDwtIDAKCiAgICAjIFRyZWlubyBwYXJhIHRvZG9zIG9zIGV4ZW1wbG9zIChlcG9jYSkKICAgIGZvcihpIGluIDE6bnJvdyhkYWRvcykpewoKICAgICAgIyBQZWdvIHVtIGV4ZW1wbG8gZGUgZW50cmFkYQogICAgICB4LmVudHJhZGEgPC0gZGFkb3NbaSwxOmFycSRudW0uZW50cmFkYV0KICAgICAgeC5zYWlkYSA8LSBkYWRvc1tpLG5jb2woZGFkb3MpXQoKICAgICAgIyBQZWdvIGEgc2FpZGEgZGEgcmVkZSBwYXJhIG8gZXhlbXBsbwogICAgICByZXN1bHRhZG8gPC0gbWxwLnByb3BhZ2FjYW8oYXJxLHguZW50cmFkYSkKICAgICAgeSA8LSByZXN1bHRhZG8keS5lc2NvbmRpZGEuc2FpZGEKCiAgICAgICMgQ2FsY3VsbyBkbyBlcnJvIHBhcmEgbyBleGVtcGxvCiAgICAgIGVycm8gPC0geC5zYWlkYSAtIHkKCiAgICAgICMgU29tYSBlcnJvIHF1YWRyYXRpY28KICAgICAgZXJyb1F1YWRyYXRpY28gPC0gZXJyb1F1YWRyYXRpY28gKyBlcnJvKmVycm8KCiAgICAgICMgR3JhZGllbnRlIGxvY2FsIG5vIG5ldXJvbmlvIGRlIHNhaWRhCiAgICAgICMgZXJybyAqIGRlcml2YWRhIGRhIGZ1bmNhbyBkZSBhdGl2YWNhbwogICAgICBncmFkLmxvY2FsLnNhaWRhIDwtIGVycm8gKiBhcnEkZGVyLmZ1bmNhby5hdGl2YWNhbyh5KQoKICAgICAgIyBHcmFkaWVudGUgbG9jYWwgbm8gbmV1cm9uaW8gZXNjb25kaWRvCiAgICAgICMgZGVyaXZhZGEgZGEgZnVuY2FvIGRlIGF0aXZhY2FvIG5vIG5ldXJvbmlvIGVzY29uZGlkbyAqIHNvbWEgZG9zIGdyYWRpZW50ZXMKICAgICAgIyBsb2NhaXMgZG9zIG5ldXJvbmlvcyBjb25lY3RhZG9zIG5hIHByb3hpbWEgY2FtYWRhICogcGVzb3MgY29uZWN0YW5kbyBhIGNhbWFkYQogICAgICAjIGVzY29uZGlkYSBjb20gYSBzYWlkYQogICAgICBwZXNvcy5zYWlkYSA8LSBhcnEkc2FpZGFbLDE6YXJxJG51bS5lc2NvbmRpZGFdCiAgICAgIGdyYWQubG9jYWwuZXNjb25kaWRhIDwtCiAgICAgICAgYXMubnVtZXJpYyhhcnEkZGVyLmZ1bmNhby5hdGl2YWNhbyhyZXN1bHRhZG8keS5lbnRyYWRhLmVzY29uZGlkYSkpICoKICAgICAgICAoZ3JhZC5sb2NhbC5zYWlkYSAlKiUgcGVzb3Muc2FpZGEpCgogICAgICAjIEFqdXN0ZSBkb3MgcGVzb3MKICAgICAgIyBTYWlkYQogICAgICBhcnEkc2FpZGEgPC0gYXJxJHNhaWRhICsgbiAqIChncmFkLmxvY2FsLnNhaWRhICUqJQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgYyhyZXN1bHRhZG8keS5lbnRyYWRhLmVzY29uZGlkYSwxKSkKICAgICAgIyBFc2NvbmRpZGEKICAgICAgYXJxJGVzY29uZGlkYSA8LSBhcnEkZXNjb25kaWRhICsgbiAqICh0KGdyYWQubG9jYWwuZXNjb25kaWRhKSAlKiUKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgYXMubnVtZXJpYyhjKHguZW50cmFkYSwxKSkpCiAgICB9ICMgRmltIGZvcihpIGluIDE6bnJvdyhkYWRvcykpCgogICAgZXJyb1F1YWRyYXRpY28gPC0gZXJyb1F1YWRyYXRpY28gLyBucm93KGRhZG9zKQogICAgY2F0KCJFcnJvIFF1YWRyYXRpY28gTWVkaW8gPSAiLGVycm9RdWFkcmF0aWNvLCAiXG4iKQogICAgZXBvY2FzIDwtIGVwb2NhcysxCiAgICAKICB9ICMgRmltIHdoaWxlKGVycm9RdWFkcmF0aWNvID4gbGltaWFyKQoKICByZXRvcm5vIDwtIGxpc3QoKQogIHJldG9ybm8kYXJxIDwtIGFycQogIHJldG9ybm8kZXBvY2FzIDwtIGVwb2NhcwoKICByZXR1cm4ocmV0b3JubykKfQpgYGAKCgpMZWl0dXJhIGRlIHVtYSB0YWJlbGEgY29tIG9zIGRhZG9zIGRvIHByb2JsZW1hIFhPUgotLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tCmBgYHtyfQpkYWRvcyA8LSByZWFkLnRhYmxlKCdYT1IudHh0JykKZGFkb3MKYGBgCgpWYW1vcyB0cmVpbmFyIG5vc3NhIE1MUApgYGB7cn0KYXJxIDwtIGFycXVpdGV0dXJhKDIsMiwxLGZ1bmNhby5hdGl2YWNhbywgZGVyLmZ1bmNhby5hdGl2YWNhbykKbW9kZWxvIDwtIG1scC5yZXRyb3Byb3BhZ2FjYW8oYXJxLGRhZG9zLDAuMSwxZS0zKQpgYGAKClZhbW9zIHRlc3RhciBlbSBkYWRvcyBub3ZvcwpgYGB7cn0KcmV0b3JubyA8LSBtbHAucHJvcGFnYWNhbyhtb2RlbG8kYXJxLGMoMCwxKSkKcmV0b3JubyR5LmVzY29uZGlkYS5zYWlkYQoKbWxwLnByb3BhZ2FjYW8obW9kZWxvJGFycSxjKDEsMCkpJHkuZXNjb25kaWRhLnNhaWRhCgptbHAucHJvcGFnYWNhbyhtb2RlbG8kYXJxLGMoMSwxKSkkeS5lc2NvbmRpZGEuc2FpZGEKCm1scC5wcm9wYWdhY2FvKG1vZGVsbyRhcnEsYygwLDApKSR5LmVzY29uZGlkYS5zYWlkYQpgYGAKLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLQoKCkxlaXR1cmEgZGUgZGFkb3Mgc29icmUgcmlzY28gZGUgY3LDqWRpdG8uCi0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0KUXVlcmVtb3MgcHJldmVyLCBjb20gYmFzZSBuYXMgdmFyacOhdmVpcyBkZSBlbnRyYWRhLCAKc2Ugb2NvcnJlcsOhIG91IG7Do28gdW0gY2Fsb3RlIGVtIDEwIGFub3MKYGBge3J9CmRhdGFzZXQgPC0gcmVhZC5jc3YoImNyZWRpdHNldC5jc3YiKQpoZWFkKGRhdGFzZXQpCgojIGNsaWVudGlkOiBpZGVudGlmaWNhw6fDo28gZG8gY2xpZW50ZQojIGluY29tZTogcmVuZGEgYW51YWwKIyBhZ2U6IGlkYWRlCiMgbG9hbjogZW1wcsOpc3RpbW8gY29tIGRhdGEgZGUgbm8gbcOtbmltbyAxMCBhbm9zIGF0csOhcwojIExUSTogcmF6w6NvIGVudHJlIHZhbG9yIGRvIGVtcHLDqXN0aW1vIGUgcmVuZGEgYW51YWwKIyBkZWZhdWx0MTB5cjogc2Ugb2NvcnJlcsOhICgxKSBvdSBuw6NvICgwKSB1bSBjYWxvdGUgZW0gMTAgYW5vcwpgYGAKClZhbW9zIHV0aWxpemFyIGNvbW8gdmFyacOhdmVpcyBkZSBlbnRyYWRhIExUSSBlIGFnZQpgYGB7cn0KZGFkb3MgPC0gZGF0YXNldFssYygzLDUsNildCmRhZG9zWywxOjJdIDwtIHNjYWxlKGRhZG9zWywxOjJdKSAjIG5vcm1hbGl6YcOnw6NvIGRvcyBkYWRvcyAobWVkaWEgMCBlIGRlc3ZpbyAxKQpgYGAKCgpWYW1vcyBlc2NvbGhlciBhbGVhdG9yaWFtZW50ZSBkYWRvcyBwYXJhIHRyZWlubyBlIHRlc3RlCk8gY29uanVudG8gZGUgZGFkb3MgasOhIGVzdMOhIHJhbmRvbWl6YWRvLiBBc3NpbSwgVmFtb3MgcGVnYXIgb3MgcHJpbWVpcm9zIDE0MDAKZXhlbXBsb3MgcGFyYSB0cmVpbm8gZSBvIHJlc3RhbnRlIHBhcmEgdGVzdGUKYGBge3J9CmRhZG9zLnRyZWlubyA8LSBkYWRvc1sxOjE0MDAsXQpkYWRvcy50ZXN0ZSA8LSBkYWRvc1sxNDAxOjIwMDAsXQpgYGAKCgpWYW1vcyB0cmVpbmFyIG5vc3NhIHJlZGUgY29tIDQgbmV1csO0bmlvcyBuYSBjYW1hZGEgZXNjb25kaWRhCmBgYHtyfQphcnEgPC0gYXJxdWl0ZXR1cmEoMiw0LDEsZnVuY2FvLmF0aXZhY2FvLCBkZXIuZnVuY2FvLmF0aXZhY2FvKQptb2RlbG8gPC0gbWxwLnJldHJvcHJvcGFnYWNhbyhhcnEsZGFkb3MudHJlaW5vLDAuMywxZS0zKQpgYGAKCgpGYXplbmRvIHByZWRpY29lcyBwYXJhIGNhZGEgZXhlbXBsbyBkZSB0ZXN0ZQpgYGB7cn0KcHJlZGljb2VzIDwtIHZlY3RvcigpCmZvcihpIGluIDE6bnJvdyhkYWRvcy50ZXN0ZSkpewoKICBwcmVkIDwtIG1scC5wcm9wYWdhY2FvKG1vZGVsbyRhcnEsZGFkb3MudGVzdGVbaSwxOjJdKSR5LmVzY29uZGlkYS5zYWlkYQogICAgCiAgcHJlZGljb2VzIDwtIGMocHJlZGljb2VzLHByZWQpCn0KYGBgCgoKQ3JpYW5kbyB1bWEgbWF0cml6IHBhcmEgY29tcGFyYcOnw6NvIGRvcyByZXN1bHRhZG9zCmBgYHtyfQptYXRyaXouY29tcGFyYWNhbyA8LSBjYmluZChkYWRvcy50ZXN0ZVssM10scHJlZGljb2VzKQpjb2xuYW1lcyhtYXRyaXouY29tcGFyYWNhbykgPC0gYygnVicsJ1AnKQptYXRyaXouY29tcGFyYWNhbwpgYGAKCgpNYXRyaXogZGUgY29uZnVzw6NvIGNvbSBvIGFycmVkb25kYW1lbnRvIGRhcyBwcmVkacOnw7VlcwpgYGB7cn0KdGFibGUobWF0cml6LmNvbXBhcmFjYW9bLDFdLHJvdW5kKG1hdHJpei5jb21wYXJhY2FvWywyXSkpCmBgYAoKCgoKCgo=