[pt] Métodos ensemble como random forest, boosting e bagging foram extensivamente estudados e provaram ter uma acurácia melhor do que usar apenas um preditor. Entretanto, a desvantagem é que os modelos obtidos utilizando esses métodos podem ser muito mais difíceis de serem interpretados do que por exemplo, uma árvore de decisão. Neste trabalho, nós abordamos o problema de construir uma árvore de decisão que aproximadamente reproduza um conjunto de árvores, explorando o tradeoff entre acurácia e interpretabilidade, que pode ser alcançado quando a reprodução exata do conjunto de árvores é relaxada. Primeiramente, nós formalizamos o problem de obter uma árvore de decisão de uma determinada profundidade que seja a mais aderente ao conjunto de árvores e propomos um algoritmo de programação dinâmica para resolver esse problema. Nós também provamos que a árvore de decisão obtida por esse procedimento satisfaz garantias de generalização relacionadas a generalização do modelo original de conjuntos de árvores, um elemento crucial para a efetividade dessa árvore de decisão em prática. Visto que a complexidade computacional do algoritmo de programação dinâmica é exponencial no número de features, nós propomos duas heurísticas para gerar árvores de uma determinada profundidade com boa aderência em relação ao conjunto de árvores. Por fim, nós conduzimos experimentos computacionais para avaliar os algoritmos propostos. Quando utilizados classificadores mais interpretáveis, os resultados indicam que em diversas situações a perda em acurácia é pequena ou inexistente: restrigindo a árvores de decisão de profundidade 6, nossos algoritmos produzem árvores que em média possuem acurácias que estão a 1 por cento (considerando o algoritmo de programção dinâmica) ou 2 por cento (considerando os algoritmos heurísticos) do conjunto original de árvores. / [en] Ensemble methods in machine learning such as random forest, boosting, and bagging have been thoroughly studied and proven to have better accuracy than using a single predictor. However, their drawback is that they give models that can be much harder to interpret than those given by, for example, decision trees. In this work, we approach in a principled way the problem of constructing a decision tree that approximately reproduces a tree ensemble, exploring the tradeoff between accuracy and interpretability that can be obtained once exact reproduction is relaxed. First, we formally define the problem of obtaining the decision tree of a given depth that is most adherent to a tree ensemble and give a Dynamic Programming algorithm for solving this problem. We also prove that the decision trees obtained by this procedure satisfy generalization guarantees related to the generalization of the original tree ensembles, a crucial element for their effectiveness in practice. Since the computational complexity of the Dynamic Programming algorithm is exponential in the number of features, we also design heuristics to compute trees of a given depth with good adherence to a tree ensemble. Finally, we conduct a comprehensive computational evaluation of the algorithms proposed. The results indicate that in many situations, there is little or no loss in accuracy in working more interpretable classifiers: even restricting to only depth-6 decision trees, our algorithms produce trees with average accuracies that are within 1 percent (for the Dynamic Programming algorithm) or 2 percent (heuristics) of the original random forest.

[pt] As árvores de decisão são estruturas comumente utilizadas em cenários nos quais modelos explicáveis de Aprendizado de Máquina são desejados, por serem visualmente intuitivas. Na literatura existente, a busca por explicabilidade em árvores envolve a minimização de métricas como altura e número de nós. Nesse contexto, definimos uma métrica de explicabilidade, chamada de explanation size, que reflete o número de atributos necessários para explicar a classificação dos exemplos. Apresentamos também um algoritmo, intitulado SER-DT, que obtém uma aproximação O(log n) (ótima se P diferente NP) para a minimização da altura no pior caso ou caso médio, assim como do explanation size no pior caso ou caso médio. Em uma série de experimentos, comparamos a implementação de SER-DT com algoritmos conhecidos da área, como CART e EC2, além de testarmos o impacto de parâmetros e estratégias de poda nesses algoritmos. SER-DT mostrou-se competitivo em acurácia com os algoritmos citados, mas gerou árvores muito mais explicáveis. / [en] Decision trees are commonly used structures in scenarios where explainable Machine Learning models are desired, as they are visually intuitive. In the existing literature, the search for explainability in trees involves minimizing metrics such as depth and number of nodes. In this context, we define an explainability metric, called explanation size, which reflects the number of attributes needed to explain the classification of examples. We also present an algorithm, called SER-DT, which obtains an O(log n) approximation (optimal if P different NP) for the minimization of depth in the worst/average case, as well as of explanation size in the worst/average case. In a series of experiments, we compared the SER-DT implementation with well-known algorithms in the field, such as CART and EC2 in addition to testing the impact of parameters and pruning strategies on these algorithms. SER-DT proved to be competitive in terms of accuracy with the aforementioned algorithms, but generated much more explainable trees.

[pt] Este trabalho propõe um novo modelo linear por partes para a extração de regras de conhecimento de banco de dados. O modelo é uma heurística baseada em análise de árvore de regressão, como introduzido por Friedman (1979) e discutido em detalhe por Breiman (1984). A motivação desta pesquisa é trazer uma nova abordagem combinando técnicas estatísticas de modelagem e um algoritmo de busca por quebras eficiente. A decisão de quebra usada no algoritmo de busca leva em consideração informações do ajuste de equações lineares e foi implementado tendo por inspiração o trabalho de Tsay (1989). Neste, ele sugere um procedimento para construção um modelo para a análise de séries temporais chamado TAR (threshold autoregressive model), introduzido por Tong (1978) e discutido em detalhes por Tong e Lim (1980) e Tong (1983). O modelo TAR é um modelo linear por partes cuja idéia central é alterar os parâmetros do modelo linear autoregressivo de acordo com o valor de uma variável observada, chamada de variável limiar. No trabalho de Tsay, a Identificação do número e localização do potencial limiar era baseada na analise de gráficos. A idéia foi então criar um novo algoritmo todo automatizado. Este processo é um algoritmo que preserva o método de regressão por mínimos quadrados recursivo (MQR) usado no trabalho de Tsay. Esta talvez seja uma das grandes vantagens da metodologia introduzida neste trabalho, visto que Cooper (1998) em seu trabalho de análise de múltiplos regimes afirma não ser possível testar cada quebra. Da combinação da árvore de decisão com a técnica de regressão (MQR), o modelo se tornou o TS-TARX (Tree Structured - Threshold AutoRegression with eXternal variables). O procedimento consiste numa busca em árvore binária calculando a estatística F para a seleção das variáveis e o critério de informação BIC para a seleção dos modelos. Ao final, o algoritmo gera como resposta uma árvore de decisão (por meio de regras) e as equações de regressão estimadas para cada regime da partição. A principal característica deste tipo de resposta é sua fácil interpretação. O trabalho conclui com algumas aplicações em bases de dados padrões encontradas na literatura e outras que auxiliarão o entendimento do processo implementado. / [en] This research work proposes a new piecewise linear model to extract knowledge rules from databases. The model is an heuristic based on analysis of regression trees, introduced by Friedman (1979) and discussed in detail by Breiman (1984). The motivation of this research is to come up with a new approach combining both statistical modeling techniques and an efficient split search algorithm. The split decision used in the split search algorithm counts on information from adjusted linear equation and was implemented inspired by the work of Tsay (1989). In his work, he suggests a model-building procedure for a nonlinear time series model called by TAR (threshold autoregressive model), first proposed by Tong (1978) and discussed in detail by Tong and Lim (1980) and Tong (1983). The TAR model is a piecewise linear model which main idea is to set the coefficients of a linear autoregressive process in accordance with a value of observed variable, called by threshold variable. Tsay`s identification of the number and location of the potential thresholds was based on supplementary graphic devices. The idea is to get the whole process automatic on a new model-building process. This process is an algorithm that preserves the method of regression by recursive least squares (RLS) used in Tsay`s work. This regression method allowed the test of all possibilities of data split. Perhaps that is the main advantage of the methodology introduced in this work, seeing that Cooper, S. (1998) said about the impossibility of testing each break.Thus, combining decision tree methodology with a regression technique (RLS), the model became the TS-TARX (Tree Structured - Threshold AutoRegression with eXternal variables). It searches on a binary tree calculating F statistics for variable selection and the information criteria BIC for model selection. In the end, the algorithm produces as result a decision tree and a regression equation adjusted to each regime of the partition defined by the decision tree. Its major advantage is easy interpretation.This research work concludes with some applications in benchmark databases from literature and others that helps the understanding of the algorithm process.

[pt] volatilidade dos ativos financeiros reflete uma reação prosseguida dos agentes a choques no passado ou alterações nas condições dos mercados determinam mudanças na dinâmica da variável? Enquanto modelos fracionalmente integrados vêm sendo extensamente utilizados como uma descrição adequada do processo gerador de séries de volatilidade, trabalhos teóricos recentes indicaram que mudanças estruturais podem ser uma relevante alternativa empírica para o fato estilizado de memória longa. O presente trabalho investiga o que alterações nos mercados significam nesse contexto, introduzindo variações de preços como uma possível fonte de mudanças no nível da volatilidade durante algum período, com grandes quedas (ascensões) nos preços trazendo regimes persistentes de variância alta (baixa). Uma estratégia de modelagem sistemática e flexível é estabelecida para testar e estimar essa assimetria através da incorporação de retornos acumulados passados num arcabouço não-linear. O principal resultado revela que o efeito é altamente significante - estima-se que níveis de volatilidade 25% e 50% maiores estão associados a quedas nos preços em períodos curtos - e é capaz de explicar altos valores de estimativas do parâmetro de memória longa. Finalmente, mostra-se que a modelagem desse efeito traz ganhos importantes para aplicações fora da amostra em períodos de volatilidade alta. / [en] Does volatility reflect lasting reactions to past shocks or changes in the markets induce shifts in this variable dynamics? In this work, we argue that price variations are an essential source of information about multiple regimes in the realized volatility of stocks, with large falls (rises) in prices bringing persistent regimes of high (low) variance. The study shows that this asymmetric effect is highly significant (we estimate that falls of different magnitudes over less than two months are associated with volatility levels 20% and 60% higher than the average of periods with stable or rising prices) and support large empirical values of long memory parameter estimates. We show that a model based on those findings significantly improves out of sample performance in relation to standard methods {specially in periods of high volatility.

[pt] Esta dissertação tem por objetivo comparar o desempenho de modelos não lineares de previsão de retornos em 10 ativos do mercado acionário brasileiro. Entre os modelos escolhidos, pode-se citar o STAR-Tree, que combina conceitos da metodologia STAR (Smooth Transition AutoRegression) e do algoritmo CART (Classification And Regression Trees), tendo como resultado final uma regressão com transição suave entre múltiplos regimes. A especificação do modelo é feita através de testes de hipótese do tipo Multiplicador de Lagrange que indicam o nó a ser dividido e a variável explicativa correspondente. A estimação dos parâmetros é feita pelo método de Mínimos Quadrados Não Lineares para determinar o valor dos parâmetros lineares e não lineares. Redes Neurais, modelos ARMAX (estes lineares) e ainda o método Naive também foram incluídos na análise. Os resultados das previsões foram avaliados a partir de medidas estatísticas e financeiras e se basearam em um negociador automático que informa o instante correto de assumir uma posição comprada ou vendida em cada ativo. Os melhores desempenhos foram alcançados pelas Redes Neurais, pelos modelos ARMAX e pela forma de previsão ARC (Adaptative Regime Combination) derivada da metodologia STAR-Tree, sendo ambos ainda superiores ao retorno das ações durante o período de teste / [en] The goal of this dissertation is to compare the performance of non linear models to forecast return on 10 equities in the Brazilian Stock Market. Among the chosen ones, it can be cited the STAR-Tree, which matches concepts from the STAR (Smooth Transition AutoRegression) methodology and the CART (Classification And Regression Trees) algorithm, having as the resultant structure a regression with smooth transition among multiple regimes. The model specification is done by Lagrange Multiplier hypothesis tests that indicate the node to be splitted and the corresponding explanatory variable. The parameter estimation is done by the Non Linear Least Squares method that determine the linear and non linear parameters. Neural Netwoks, ARMAX models (these ones linear) and the Naive method were also included in the analysis. The forecasting results were calculated using statistical and financial measures and were based on an automatic negociator that signaled the right instant to take a short or a long position in each stock. The best results were reached by the Neural Networks, ARMAX models and ARC (Adaptative Regime Combination ) forecasting method derived from STAR-Tree, with all of them performing better then the equity return during the test period.

[pt] O objetivo principal desta tese introduzir um modelo estruturado por árvores que combina aspectos de duas metodologias: CART (Classification and Regression Tree) e STR (Smooth Transition Regression). O modelo aqui denominado STR-Tree. A idéia especificar um modelo não-linear paramétrico através da estrutura de uma árvore de decisão binária. O modelo resultante pode ser analisado como uma regressão com transição suave entre múltiplos regimes. As decisões sobre as divisões dos nós são inteiramente baseadas em testes do tipo Multiplicadores de Lagrange. Uma especificação alternativa baseada em validação cruzada também utilizada. Um experimento de Monte Carlo utilizado para avaliar o desempenho da metodologia proposta comparando-a com outras técnicas comumente utilizadas. Como resultado verifica-se que o modelo STR- Tree supera o tradicional CART quando seleciona a arquitetura de árvores simuladas. Além do mais, utilizar testes do tipo Multiplicadores de Lagrange gera resultados melhores do que procedimentos de validação cruzada. Quando foram utilizadas bases de dados reais, o modelo STR-Tree demonstrou habilidade preditiva superior ao CART. Através de uma aplicação, extende-se a metodologia para a análise de séries temporais. Neste caso, o modelo denominado STAR- Tree, sendo obtido através de uma árvore de decisão binária que ajusta modelos autoregressivos de primeira ordem nos regimes. A série de retornos da taxa de câmbio Euro/Dólar foi modelada e a capacidade preditiva e o desempenho financeiro do modelo foi comparado com metodologias padrões como previsões ingênuas e modelos ARMA. Como resultado obtido um modelo parcimonioso que apresenta desempenho estatístico equivalente às estratégias convencionais, porém obtendo resultados financeiros superiores. / [en] He main goal of this Thesis is to introduce a tree- structured model that combines aspects from two methodologies: CART (Classification and Regression Trees) and STR (Smooth Transition Regression). The model is called STR-Tree, The idea is to specify a nonlinear parametric model through the structure of a binary decision tree. The resulting modelo can be analyzed as a smooth transition regression model with multiple regimes. The decisions for splitting the nodes of the tree are entirely based on Lagrange Multipliers tests. An alternative specification that uses cross- validation is also tried. A Monte Carlo Experiment is used to evaluate the performance of the proposed methodology and to compare with other techniques that are commonly used. The results showed that the STRTree model outperformed the traditional CART when specifying the architecture of a simulated tree. Moreover, the use of Lagrange Multipliers tests gave better results than a cross-validation procedure. After applying the model to real datasets, it could be seen that STR-Tree showed superior predictive ability when compared to CART. The idea was extended to time series analysis through an application. In this situation, we call the model as STAR- Tree which is obtained through a binary decision tree that fits first-order autoregressive models for different regimes. The model was fitted to the returns of Euro/Dolar exchange rate time series and then evaluated statistically and financially. Comparing with the naive approach and ARMA methodology, the STAR-Tree was parsimonious and presented statistical performance equivalent to others. The financial results were better than the others.

[pt] Os modelos de Black & Scholes e binomial para avaliação de opções financeiras dão como resultado prêmios cujo valor aumenta proporcionalmente ao aumento da incerteza do retorno dos ativos subjacentes às opções, medida pelo desvio-padrão. Também na avaliação de empresas, a teoria das opções financeiras pode ser estendida para avaliar as mesmas como opções reais. Este método é adequado quando se analisam ativos de empresas sujeitos a fortes incertezas, situação na qual a flexibilidade das opções adiciona valor considerável aos ativos físicos. Seguindo esta ótica, a pesquisa analisou uma linha aérea internacional de uma empresa de transporte aéreo regular de passageiros. A análise é adequada na medida em que a indústria do transporte aéreo, atualmente em crise, está sujeita a fortes incertezas de receita de passageiros e também de custos como o de combustível. Pela análise por opções reais, a pesquisa demonstrou que a flexibilidade existente acerca das opções de aumentar, reduzir freqüências nos vôos ou até mesmo abandonar as operações, aliada às incertezas de mercado, adiciona valor considerável aos ativos de uma empresa aérea. Assim, avaliar as mesmas apenas baseando-se no método ortodoxo do Valor Presente Líquido num cenário de crise como o atual, constitui-se numa análise incompleta. A pesquisa utilizou uma modelagem discreta no tempo e estado, com a combinação das incertezas de receita e combustível evoluindo segundo uma árvore quadrinomial. / [en] The Black & Scholes and the binomial models for financial options valuation give, as a result, premiums whose value increases proportionally to the increase of the degree of uncertainty about the return of the underlying assets, as measured by the standard deviation. When companies are valuated, financial options theory can be extended to valuate them as real options. This method is adequate when analysing company assets subjected to great uncertainty, in which the options flexibility adds considerable value to the physical assets. In this context, this research shows the analysis of an international airline of a regular passenger air transport company. The analysis is adequate as long as the air transport industry, nowadays in crisis, is subjected to strong uncertainties like passenger revenue and fuel costs. Through the real options analysis, the research showed that the flexibility given by the options of increasing or decreasing flights frequencies, and even of abandoning operations, together with the Market uncertainties, adds considerable value to the assets of an air carrier. In this sense, valuating them only according to the orthodox method of the Net Present Value in a scenario of crisis as nowadays, is an incomplete analysis. The study was based on a discrete time and discrete state model, combining the evolution of revenue and fuel cost uncertainties according to a quadrinomial decision tree.

[pt] O objetivo deste estudo foi explorar o problema de churn em seguros de vida, no sentido de prever se o cliente irá cancelar o produto nos próximos 6 meses. Atualmente, métodos de machine learning vêm se popularizando para este tipo de análise, tornando-se uma alternativa ao tradicional método de modelagem da probabilidade de cancelamento através da regressão logística. Em geral, um dos desafios encontrados neste tipo de modelagem é que a proporção de clientes que cancelam o serviço é relativamente pequena. Para isso, este estudo recorreu a técnicas de balanceamento para tratar a base naturalmente desbalanceada – técnicas de undersampling, oversampling e diferentes combinações destas duas foram utilizadas e comparadas entre si. As bases foram utilizadas para treinar modelos de Bagging, Random Forest e Boosting, e seus resultados foram comparados entre si e também aos resultados obtidos através do modelo de Regressão Logística. Observamos que a técnica SMOTE-modificado para balanceamento da base, aplicada ao modelo de Bagging, foi a combinação que apresentou melhores resultados dentre as combinações exploradas. / [en] The purpose of this study is to explore the churn problem in life insurance, in the sense of predicting if the client will cancel the product in the next 6 months. Currently, machine learning methods are becoming popular in this type of analysis, turning it into an alternative to the traditional method of modeling the probability of cancellation through logistics regression. In general, one of the challenges found in this type of modelling is that the proportion of clients who cancelled the service is relatively small. For this, the study resorted to balancing techniques to treat the naturally unbalanced base – under-sampling and over-sampling techniques and different combinations of these two were used and compared among each other. The bases were used to train models of Bagging, Random Forest and Boosting, and its results were compared among each other and to the results obtained through the Logistics Regression model. We observed that the modified SMOTE technique to balance the base, applied to the Bagging model, was the combination that presented the best results among the explored combinations.