• Português
  • English
  • Español
  • Boosting (1): Árvores de Decisão e Gradient Boosting

    Por: em 6 de fevereiro de 2019

    Este texto corresponde ao primeiro de uma mini-série de três posts sobre algoritmos de boosting. Neste primeiro texto, faremos uma introdução breve e prática sobre árvores de decisão e ajusteremos um modelo de classificação e um de regressão sobre dois conjuntos simples de dados em poucas linhas de código. Ao final, chegaremos em um exemplo básico de uso de gradient boosting usando scikit-learn. Os outros dois posts (a serem publicados em breve) falarão sobre implementações específicas de LightGBM e CatBoost.

    Nota: parte deste tutorial segue o conteúdo dos capítulos 6 e 7 do excelente livro “Hands-On Machine Learning with Scikit-Learn & Tensorflow”, de Aurélien Géron [1] e também do capítulo 10 do livro “The Elements of Statistical Learning”, de Hastie et al. [2]

    Introdução

    Árvores de decisão são métodos de classificação ou regressão que particionam o espaço de featuresem pedaços disjuntos e, então, classificam os dados ou ajustam um modelo simples (uma constante, por exemplo) sobre eles de acordo com a partição em que caíram. O nome vem do fato de que o modelo pode ser facilmente representado por uma árvore. São modelos simples, mas poderosos.

    Em um problema de classificação, uma árvore típica é produzida da seguinte forma: encontra-se uma variável e um respectivo ponto de divisão que, separando o conjunto total de treino em dois subconjuntos disjuntos, produz partições com o menor valor de alguma métrica de impureza, como o Gini Index, por exemplo. Ou seja, inicialmente, os dados são divididos nos dois subconjuntos mais puros possível. Em sequência, busca-se outra subdivisão (em qualquer dos subconjuntos já existentes) que produza subconjuntos ainda mais puros que anteriormente. E estes passos são repetidos até que algum critério de parada seja atingido – critérios comuns são, por exemplo, a exigência que todo conjunto tenha um número mínimo de pontos, ou atingir um número pré-definido de subdivisões. Ao final, os pontos são classificados de acordo com o subconjunto final do qual faz parte.

    Em um problema de regressão, os passos são equivalentes, com a diferença que a métrica que deve ser minimizada em cada divisão não é uma estimativa de impureza, mas tipicamente um erro quadrático médio do ajuste (ou outra métrica mais apropriada para o problema específico).

     

    Árvores de Decisão: Classificação com Scikit-learn

    Para iniciar este tutorial prático, vamos utilizar o próprio scikit-learn para importar o dataset Iris, introduzido por Fisher em 1936 e presença constante em exemplos de machine learning:

    from sklearn.datasets import load_iris
    iris = load_iris()
    

    Estes dados correspondem à 150 medidas da largura e comprimento das sépalas e pétalas de flores de três diferentes espécies: Iris Setosa, Iris Versicolor e Iris Virginica.

    iris.data.shape
    > (150, 4)
    
    iris.feature_names
    > ['sepal length (cm)',
      'sepal width (cm)',
      'petal length (cm)',
      'petal width (cm)']
    
    iris.target_names
    > array(['setosa', 'versicolor', 'virginica'], dtype='<U10')
    

    Para o nosso exemplo, vamos usar somente as informações sobre as pétalas:

    X = iris.data[:,2:]
    y = iris.target
    

    Vamos então fazer uso da implementação do scikit-learn para construir e ajustar uma árvore de decisão nestes dados com pouquíssimas linhas de código.

    from sklearn.tree import DecisionTreeClassifier
    tree_clf = DecisionTreeClassifier(max_depth=2)
    tree_clf.fit(X,y)
    
    > DecisionTreeClassifier(class_weight=None, criterion='gini', max_depth=2,
                max_features=None, max_leaf_nodes=None,
                min_impurity_decrease=0.0, min_impurity_split=None,
                min_samples_leaf=1, min_samples_split=2,
                min_weight_fraction_leaf=0.0, presort=False, random_state=None,
                splitter='best')
    

    Uma das grandes vantagens de se usar árvores de decisão é a facilidade de visualização do modelo que, como dito anteriormente, pode ser representado graficamente como uma árvore. O próprio scikit-learn permite a visualização do ajustede uma árvore de decisão com ajuda do Graphviz, que em Linux é facilmente chamado pelo comando dot:

    from sklearn.tree import export_graphviz
    export_graphviz(tree_clf,
                    out_file="iris_clf.dot",
                    feature_names=iris.feature_names[2:],
                    class_names=iris.target_names,
                    rounded=True,
                    filled=True)
    
    ! dot -Tpng iris_clf.dot -o iris_clf.png    # rodar no terminal
    

     

     

     

    O que esta árvore bastante curta indica é que, primeiramente, o conjunto de 150 amostras foi dividido em dois com base na largura da pétala – se a planta tem pétala menor que 0.8 cm, é classificada como setosa. Esta separação é perfeita, como mostra o valor do coeficiente de gini (zero para este conjunto) e a linha value, e todas as 50 amostras do conjunto de treinamento com pétalas menores que este valor são, de fato, desta espécie. Igualmente, todas os outros 50+50 exemplos com pétalas maiores são de alguma outra espécie. Em sequência, foi buscado outro ponto de corte entre as variáveis todas e este foi encontrado novamente na largura da pétala, desta vez no valor 1.75 cm. Pétalas menores que este valor (mas maiores que 0.8 cm) são classificadas como versicolore pétalas maiores, como virginica. Mas note que neste caso os conjuntos não são completamente puros, como pode ser verificado na imagem abaixo (que pode ser criada a partir de um exemplo encontrado na documentação do scikit-learn).

     

     

    Um exemplo de regressão

    Para exemplificar uma regressão com árvores, criamos primeiramente um conjunto de dados quase trivial: uma função quadrática com algum ruído.

    x = np.arange(0, 1, 0.005)
    X = np.c_[x]
    y = (2*x-1)**2 + np.random.normal(scale=0.1, size=len(x))
    

    Nas linhas de código a seguir, usamos novamente a implementação do scikit-learn para ajustar quatro árvores com diferentes profundidades máximas: 2, 3, 5 e 30. Nestes exemplos, este é o único hiper-parâmetro variável. Note como uma árvore, mesmo sendo um modelo simples, pode no limite representar pequenas variações nos dados, apresentando um overfittingóbvio para algumas escolhas de hiper-parâmetros.

    from sklearn.tree import DecisionTreeRegressor
    _, axs = plt.subplots(2, 2, figsize=(15,10))
    for ax, depth in zip(axs.flatten(), (2, 3, 5, 30)):
        tree_reg = DecisionTreeRegressor(max_depth=depth)
        tree_reg.fit(X,y)
    
        ax.scatter(x, y, s=8)
        ax.plot(x, tree_reg.predict(np.c_[x]), color='r')
        ax.set_title('max_depth = ' + str(depth))
    

     

    Gradient Boosting

    Chegamos enfim ao boosting. Esta é uma técnica desenvolvida recentemente que se mostrou muito poderosa e hoje corresponde a uma das mais utilizadas em competições de machine learning. O princípio que está por trás de qualquer algoritmo de boosting é a combinação do resultado de muitos classificadores (ou regressores) fracos, se combinando para formar uma espécie de comitê forte de decisão. Embora não haja restrições quanto a estes classificadores e regressores, é usual a utilização de árvores.

    Em sua definição matemática, boosting é uma forma de expansão, ajustando os dados em uma soma ponderada de funções elementares:

    $$ f(x) = \sum_{m=1}^M \beta_m b(x;\gamma_m), $$

    onde $ \beta_m $ são os coeficientes da expansão e $ b(x;\gamma) $são funções simples do argumento $x$, caracterizadas pelo parâmetro $\gamma$.Tipicamente estes modelos são ajustados ao se minimizar o valor esperado (sobre o conjunto de treino) de alguma _loss:

    $$ \min{ {\beta_m, \gamma_m }_1^M } \sum{i=1}^N L \left(yi, \sum{m=1}^M \beta_m b(x_i;\gamma_m) \right)$$.

    Mas como esta minimização pode ser extremamente custosa computacionalmente, uma forma de simplificá-la e torná-la viável é fazer a seguinte aproximação: ao invés de minimizar sobre todo o conjunto de parâmetros ${\beta_m, \gamma_m }_1^M$de uma só vez, adicionar sequencialmente novas funções-base $b(x;\gamma)$sem nunca alterar os parâmetros e coeficientes que já foram adicionados antes. Isto é, a cada iteração $m$, encontra-se o termo $\beta_m$ e a função $b(x;\gamma_m)$ótimos que minimizam a _losse adiciona-se $\beta_m b(x;\gamma_m)$à expansão $f{m-1}(x)$, sem alterar os termos anteriores. Quando estivermos considerando como losso erro quadrático médio $L(y, f(x)) = (y-f(x))^2$, isto significaria minimizar, a cada etapa, o valor

    $$ L(y_i, f_{m-1}(x_i) + \beta b(x_i;\gamma)) = (r_{im} – \beta b(x_i; \gamma))^2, $$

    onde $r_{im} = y_i – f_{m-1}$ é o resíduo do atual modelo na observação $i$. Assim, para esta escolha específica de loss, a cada etapa adicionaríamos à expansão o termo que melhor ajusta o resíduo atual. Este raciocínio está implementado no algoritmo abaixo, onde três termos são adicionados em sequência, cada um ajustando uma árvore sobre os resíduos da etapa anterior. Aqui, consideramos o mesmo conjunto de dados do exemplo passado.

    tree_reg1 = DecisionTreeRegressor(max_depth=2)
    tree_reg1.fit(X, y)
    
    y2 = y - tree_reg1.predict(X)
    tree_reg2 = DecisionTreeRegressor(max_depth=2)
    tree_reg2.fit(X, y2)
    
    y3 = y2 - tree_reg2.predict(X)
    tree_reg3 = DecisionTreeRegressor(max_depth=2)
    tree_reg3.fit(X, y3)
    

     

     

    O mesmo resultado acima pode ser obtido com a implementação do scikit-learn, chamada através de:

    from sklearn.ensemble import GradientBoostingRegressor
    
    gbrt = GradientBoostingRegressor(max_depth=2, n_estimators=3, learning_rate=1)
    gbrt.fit(X,y)
    

    Note na figura como o ajuste fica progressivamente mais preciso com a adição de novas árvores. Mas quantas árvores podemos adicionar antes que haja overfitting? É claro que a resposta depende de muitos fatores, onde não menos importantes são os dados disponíveis para análise. No código abaixo, treinamos um ensemblecom 120 árvores, e medimos o erro no conjunto de validação para cada etapa.

    from sklearn.model_selection import train_test_split
    from sklearn.metrics import mean_squared_error
    
    X_train, X_val, y_train, y_val = train_test_split(X,y)
    
    gbrt = GradientBoostingRegressor(max_depth=2, n_estimators=120)
    gbrt.fit(X_train, y_train)
    
    errors = [mean_squared_error(y_val, y_pred) for y_pred in gbrt.staged_predict(X_val)]
    

    Por fim, usamos o erro de validação a cada etapa para estimar o número ótimo de árvores e usamos este número para treinar outro ensemble, cujo resultado se encontra na figura a seguir.

    best_number_of_estimators = np.argmin(errors)
    
    gbrt_best = GradientBoostingRegressor(max_depth=2, n_estimators=best_number_of_estimators)
    gbrt_best.fit(X_train, y_train)
    

    Algoritmos de boosting têm sido cada vez mais utilizados na comunidade de machine learning, especialmente após a enorme sequência de sucessos obtidos por algumas implementações em competições por todo o mundo. No Serasa Experian DataLab não é diferente. Estes modelos tipicamente produzem resultados muito acima dos obtidos com técnicas tradicionais, e portanto fazem parte do arsenal de todos os data scientists da equipe – de fácil implementação, geram rapidamente um benchmark inicial realista em um número grande de aplicações.

    Já falamos aqui no blog sobre XGBoost [3] e, nas próximas semanas, teremos posts sobre implementações específicas de outros algoritmos de boosting.

    [1] Géron, Aurélien. Hands-on machine learning with Scikit-Learn and TensorFlow: concepts, tools, and techniques to build intelligent systems. “O’Reilly Media, Inc.”, 2017.

    [2] Friedman, Jerome, Trevor Hastie, and Robert Tibshirani. The elements of statistical learning. Vol. 1. No. 10. New York, NY, USA:: Springer series in statistics, 2001.

    [3] https://www.serasaexperian.com.br/datalab/blog/xgboost

    6 de fevereiro de 2019

    Filtre por autor