[pt] O principal objetivo desta dissertação é comparar o desempenho de modelos lineares e não-lineares de previsão de retornos de 23 ativos do mercado acionário americano. Propõe-se o modelo STAR-Tree Heterocedástico, que faz uso da metodologia do STAR-Tree (Smooth Transition AutoRegression Tree) aplicada a séries temporais heterocedásticas. Com a disponibilidade de dados de retorno e da volatilidade realizada de ações intra-diários, as séries de retornos são transformadas através da divisão de cada retorno pela sua volatilidade realizada. A série transformada apresenta variância constante. O modelo é uma combinação da metodologia STAR (Smooth Transition AutoRegression) e do algoritmo CART (Classification and Regression Tree). O modelo resultante pode ser interpretado como uma regressão de múltiplos regimes com transição suave. A especificação do modelo é feita através de testes de Multiplicadores de Lagrange, que indicam o nó a ser dividido e a variável de transição correspondente. Os modelos de comparação usados são o modelo Média, o método Naive, modelos lineares ARX e Redes Neurais. As previsões dos modelos foram avaliadas através de medidas estatísticas e financeiras. Os resultados financeiros baseam-se em uma regra de negociação automática que informa o momento de comprar e vender cada ativo. O modelo STAR-Tree Heterocedástico teve resultados estatísticos equivalentes aos dos outros modelos, porém apresentou um desempenho financeiro superior para a maioria das séries. A volatilidade realizada também foi estimada usando a metodologia STAR-Tree, e sua previsão foi utilizada para fazer uma análise de alavancagem financeira. / [en] The main goal of this dissertation is to compare the performance of linear and nonlinear models to forecast 23 assets of the American Stocks Market. The Heteroscedastic STAR-Tree Model is proposed using the STAR- Tree (Smooth Transition AutoRegression Tree) methodology applied to heteroscedastic time series. As assets returns and realized volatility intraday data are available, the returns series are transformed by dividing each return by its realized volatility, which gives homocedastic series. The model is a combination of the STAR (Smooth Transition AutoRegression) methodology and the CART (Classification and Regression Tree) algorithm. The resulting model can be interpreted as a smooth transition multiple regime regression. The model specification is done by Lagrange Multiplier tests that indicate the node to be split and the corresponding transition variable. The comparison models used are the Mean model, Naive method, ARX linear models and Neural Networks. The forecasting models were evaluated through statistical and financial measures. The financial results are based on an automatic trading rule that signals buy and hold moments in each stock. The Heteroscedastic STAR-Tree Model statistical performance was equivalent to the other models, however its financial performance was superior for most of the series. The STAR-Tree methodology was also applied for forecasting the realized volatility, and the forecasts were used in financial leverage analysis.

[pt] O resgate automático, mais conhecido por autocall, de produtos estruturados vem se tornado uma prática usual no mercado internacional no que se refere à indexação dos contratos que visam a alavancagem de capital por meio de estratégias de financiamento envolvendo derivativos. O objetivo focal deste trabalho é a análise do apreçamento por meio da dinâmica do autocall em uma emissão de notas de cupom com barreira baseadas em ADRs (data inicial em 02/04/2011 e final em 02/04/2012) da maior companhia de mineração e metais do país, a Vale S.A. (VALE).Neste estudo, pretende-se explicar detalhadamente a dinâmica do autocall: como ele se estrutura; como estes são afetados pelo tempo nas datas de resgate; a probabilidade de serem resgatados (callables) em cada data; a determinação do pagamento devido na data de cupom e como esses pagamentos são dependentes de instrumentos característicos e os principais produtos estruturados com autocall. O modelo numérico de análise será pautado em uma modificação do modelo de Árvore Trinomial. Nesta variação proposta, adicionaram-se as condicionais (autocall, barreira e knock-in) e a modificação para cálculo do valor presente do produto estruturado. Logo, por meio deste estudo, busca-se colocar em prática o desenvolvimento de um novo cálculo de apreçamento envolvendo autocall, a fim de fazer a avaliação de produtos estruturados (com uma tipologia similar a esta emissão da VALE), e introduzir este assunto no meio acadêmico brasileiro já que nenhum outro trabalho lidou com este tema antes. / [en] The automatic redemption, best known as autocall, of structured products has become an usual practice in the international market with regard to the indexation of contracts that aim capital leverage through financing strategies involving derivatives. The focal goal in this work is the pricing analysis by autocall’s dynamic in an issue of coupon barrier notes based in ADRs (starts on 02/04/2011 and ends on 04/02/2012) from the largest mining and metal company in the country, Vale S.A. (VALE). This study intend to explain in details the dynamics of autocall: how it is structured, how they are affected by the time in the redemption dates; the probability of being rescued (callables) on each date; the determination of the due payment in the coupon date and how these payments are dependents from these characteristic instruments and the main structured products structured with autocall. The numerical analysis model will be based on a modification of the trinomial tree model. In this proposal variation, were added the conditionals (autocall, barrier and knock-in) and the modification to calculate the present value of the structured product. Thus, through this article, the idea is to put a new development of calculus that involves autocall pricing in practice in order to make the valuation of structured products (with a similar typology to this issue of VALE), and introduce this subject in the Brazilian academic field as any other article dealt with this subject before.

[pt] Neste trabalho, apresentamos algoritmos aproximativos para dois problemas de otimização em árvores. Na primeira parte, consideramos o Problema de Atribuição de k-Hotlinks. Seja G= (V,E) um grafo direcionado acíclico representando um web site, onde nós correspondem a páginas e arcos correspondem a hyperlinks. Nesse contexto, hotlink são definidos como atalhos (novos arcos) adicionados às páginas de G de modo a reduzir o tempo gasto pelos usuários para alcançarem as informações desejadas. Neste trabalho consideramos o problema onde G é uma árvore enraizada e o objetivo é minimizar o tempo médio gasto pelos usuários atribuindo no máximo k hotlinks a cada nó. Para a versão mais estudada desse problema onde no máximo um hotlink pode ser atribuído a cada nó, provamos a existência de um FPTAS. Isso representa uma significante melhora em relação ao algoritmo com aproximação constante obtido recentemente em [Jacobs, WADS 2007]. Além disso, desenvolvemos o primeiro algoritmo com aproximação constante para a versão mais geral onde k hotlinks podem ser atribuídos a cada nó. Na segunda parte deste trabalho, consideramos o problema de computar estratégias eficientes para realizar buscas em árvores. Como uma generalização da tradicional busca binária em listas ordenadas, suponha que se deseja encontrar um nó específico (porém desconhecido) de uma árvore realizando consultas em seus arcos, onde cada consulta indica a extremidade do arco mais próxima ao nó desejado. Dada a probabilidade de cada nó ser aquele procurado, o objetivo é computar uma estratégia de busca que minimize o número esperado de consultas. Aplicações práticas desse problema incluem sincronização de file systems e testes de software. Apresentamos um algoritmo linear que obtém a primeira aproximação constante para esse problema. Isso representa uma melhora significativa em relação à O(log n)-aproximação anterior. / [en] Here we present a study on two optimization problems in trees: the k- Hotlink Assignment Problem and the problem of Binary Searching in Trees. As a result, we obtain improved approximation algorithms for both problem. The k-Hotlink Assignment Problem can be defined as follows. Let G = (V,E) be a directed acyclic graph representing a web site, where nodes correspond to pages and arcs to hyperlinks. In this context, hotlinks are defined as shortcuts (new arcs) added to web pages of G in order to reduce the time spent by users to reach their desired information. Here we consider the problem where G is a rooted directed tree and the goal is minimizing the expected time spent by users by assigning at most k hotlinks to each node. For the most studied version of this problem where at most one hotlink can be assigned from each node, we prove the existence of an FPTAS, improving upon the constant factor algorithm recently obtained in [Jacobs, WADS 2007]. In addition, we develop the first constant factor approximation algorithm for the most general version where k hotlinks can be assigned from each node. In the second part of this work, we consider the problem of computing efficient strategies for searching in trees. As a generalization of the classical binary search for ordered lists, suppose one wishes to find a (unknown) specific node of a tree by asking queries to its arcs, where each query indicates the endpoint closer to the desired node. Given the likelihood of each node being the one searched, the objective is to compute a search strategy that minimizes the expected number of queries. Practical applications of this problem include file system synchronization and software testing. Here we present a linear time algorithm which is the first constant factor approximation for this problem. This represents a significant improvement over previous O(log n)-approximation.

[pt] Os códigos de prefixo têm importância fundamental na comprenssão e transmissão de dados. Estes códigos também apresentam relações com problemas de busca. Neste tese, apresentamos novos resultados estruturais e algorítimos sobre a classe dos códigos de prefixo. Explicamos teoricamente as boas taxas de compressão observadas para alguns métodos utilizados na prática. Propomos também algoritmos eficientes para construção de códigos de prefixo ótimos e variantes. Os principais resultados aqui descritos são os seguintes: - um novo algoritmo paralelo para construção de códigos de prefixos ótimos: - uma cota superior para a perda de compressão introduzida pela restrição de comprimento nos códigos de prefixo: - uma cota superior para a perda de compressão introduzida pela restrição de comprimento nos códigos de prefixo alfabéticos: - um algoritmo aproximativo e linear para construção de códigos de prefixo com restrição de comprimento: - um algoritmo aproximativo com complexidade 0(n log n) para construção de códigos de prefixo alfabéticos com restrição de comprimento: - uma nova versão de algoritmo WARM-UP com complexidade fortemente polinomial: - um algoritmo linear para reconhecer códigos de prefixo ótimos com restrição de comprimento: - uma prova afirmativa da conjectura de Vitter sobre o desempenho dos códigos de Huffmann dinâmicos construídos pelo algoritmo FGK (Faller, Gallanger e Knuth) / [en] The prefix codes play an important role in data compression and data communication. These codes also present relation with search problems. In this thesis, we present new structural and algorithmic results concerning the prefix code class. We theoretically explain results related to the high compression rates of some methods that have been used for pratical purposes. We also propose efficient algorthims for constructing optimal prefix codes and some variants. The major results are listed below: -a new parallel algorithm for constructing optimal prefix codes: -a sharp upper bound for the compression loss introduced due usage of length restricted prefix codes: -an upper bound for the compression loss introduced due the usage of length restricted alphabetic prefix codes: -an 0(n log n) time approximative algorithm for constructing lenght restricted prefix code: -a 0(n log n) time approximative algorithm for constructing lenght restricted alphabetic prefix code: -a strongly polinomial version for the WARM-UP algorithm: -a linear time algorithm for recognizing optimal length restricted prefix codes: -a proof for Vitter´s conjecture about the perfomance of the Dynamic Huffman Codes constructed by FGK (Faller, Gallager and Knuth) algorithm.

[pt] O problema de minimizar o custo de avaliar uma função discreta lendo sequencialmente as suas variáveis é um problema que surge em diversas aplicações, entre elas sistemas de diagnóstico automático e aprendizado ativo. Neste problema, cada variável da função está associada a um custo, que se deve pagar para checar o seu valor. Além disso, pode existir uma distribuição de probabilidades associadas aos pontos onde a função está definida. A maioria dos trabalhos nesta área se concentra ou na minimização do custo máximo ou na minimização do custo esperado gasto para avaliar a função. Nesta dissertação, mostramos como obter uma Ômicron logaritmo de N aproximação em relação à minimização do pior custo (a melhor aproximação possível assumindo que P é diferente de NP). Nós também mostramos um procedimento polinomial para avaliar uma função otimizando simultaneamente o pior custo e o custo esperado. / [en] The problem of minimizing the cost of evaluating a discrete function by sequentially reading its variables is a problem that arises in several applications, among them automatic diagnosis design and active learning. In this problem, each variable of the function is associated with a cost, that we have to pay in order to check its value. In addition, there may exist a probability distribution associated with the points where the function is defined. Most of the work in the area has focussed either on the minimization of the maximum cost or on the minimization of the expected cost spent to evaluate the function. In this dissertation, we show how to obtain an Ômicron logarithm of N approximation with respect to the worst case minimization (the best possible approximation under the assumption that P is different from NP). We also show a polynomial time procedure for evaluate a function that simultaneously optimizes both the worst and the expected costs.

[pt] Esta dissertação visa analisar como o modelo de apreçamento de opções, utilizando o conceito de árvore trinomial implícita, pode ser aplicado no mercado acionário brasileiro, com resultados mais consistentes, se comparado ao modelo de Black-Scholes. Esse modelo incorpora o conceito de volatilidade implícita, sendo consideradas as expectativas futuras em relação ao preço de um ativo. A volatilidade implícita apresenta diferentes valores para diferentes preços de exercício ao longo do tempo. A denominação sorriso de volatilidade deve-se ao formato da curva da volatilidade implícita em função do preço de exercício. O formato do sorriso varia de acordo com o ativo-objeto da opção. Assim, a volatilidade varia ao longo tempo no cálculo da árvore, pois leva em considerando as oscilações do mercado, o que, conseqüentemente, impacta no preço do ativo e sua opção. / [en] This Paper aims to analyze how the option pricing model, using the concept of Implied Trinomial Trees can be applied to the Brazilian stock market, achieving more accurate results, if compared to the Black-Scholes model. This model includes the Implied Volatility concept, which means that future expectations are considered to price an asset. It presents different values for different Strike Prices through time. The volatility smile is named this way because of the shape of the Implied Volatility x Strike Price curve, which reminds a smile. Its shape changes according to the asset to be priced. Thus, as volatility varies with time, the option pricing using Implied Trinomial Trees is affected by the market’s oscillations, whose consequences can be observed in the asset’s price and its option price, consequently.

[pt] Problemas de classificação foram amplamente estudados na literatura de aprendizado de máquina, gerando aplicações em diversas áreas. No entanto, em diversos cenários, custos por erro de classificação podem variar bastante, o que motiva o estudo de técnicas de classificação sensível ao custo. Nesse trabalho, discutimos o uso de árvores de decisão para o problema mais geral de Aprendizado Sensível ao Custo do Exemplo (ASCE), onde os custos dos erros de classificação variam com o exemplo. Uma das grandes vantagens das árvores de decisão é que são fáceis de interpretar, o que é uma propriedade altamente desejável em diversas aplicações. Propomos um novo método de seleção de atributos para construir árvores de decisão para o problema ASCE e discutimos como este pode ser implementado de forma eficiente. Por fim, comparamos o nosso método com dois outros algoritmos de árvore de decisão propostos recentemente na literatura, em 3 bases de dados públicas. / [en] Classification problems have been widely studied in the machine learning literature, generating applications in several areas. However, in a number of scenarios, misclassification costs can vary substantially, which motivates the study of Cost-Sensitive Learning techniques. In the present work, we discuss the use of decision trees on the more general Example-Dependent Cost-Sensitive Problem (EDCSP), where misclassification costs vary with each example. One of the main advantages of decision trees is that they are easy to interpret, which is a highly desirable property in a number of applications. We propose a new attribute selection method for constructing decision trees for the EDCSP and discuss how it can be efficiently implemented. Finally, we compare our new method with two other decision tree algorithms recently proposed in the literature, in 3 publicly available datasets.

[pt] A construção de árvores de decisão é um problema central em diversas áreas da ciência da computação, por exemplo, teoria de banco de dados e aprendizado computacional. Este problema pode ser visto como o problema de avaliar uma função discreta, onde para verificar o valor de cada variável da função temos que pagar um custo, e os pontos onde a função está definida estão associados a uma distribuição de probabilidade. O objetivo do problema é avaliar a função minimizando o custo gasto (no pior caso ou no caso médio). Nesta tese, apresentamos quatro contribuições relacionadas a esse problema. A primeira é um algoritmo que alcança uma aproximação de O(log(n)) em relação a tanto o custo esperado quanto ao pior custo. A segunda é um método que combina duas árvores, uma com pior custo W e outra com custo esperado E, e produz uma árvore com pior custo de no máximo (1+p)W e custo esperado no máximo (1/(1-e-p))E, onde p é um parâmetro dado. Nós também provamos que esta é uma caracterização justa do melhor trade-off alcançável, mostrando que existe um número infinito de instâncias para as quais não podemos obter uma árvore de decisão com tanto o pior custo menor que (1 + p)OPTW(I) quanto o custo esperado menor que (1/(1 - e - p))OPTE(I), onde OPTW(I) (resp. OPTE(I)) denota o pior custo da árvore de decisão que minimiza o pior custo (resp. custo esperado) para uma instância I do problema. A terceira contribuição é um algoritmo de aproximação de O(log(n)) para a minimização do pior custo para uma variante do problema onde o custo de ler uma variável depende do seu valor. Nossa última contribuição é um algoritmo randomized rounding que, dada uma instância do problema (com um inteiro adicional (k > 0) e um parâmetro 0 < e < 1/2, produz uma árvore de decisão oblivious com custo no máximo (3/(1 - 2e))ln(n)OPT(I) e que produz no máximo (k/e) erros, onde OPT(I) denota o custo da árvore de decisão oblivious com o menor custo entre todas as árvores oblivious para a instância I que produzem no máximo k erros de classificação. / [en] Decision tree construction is a central problem in several areas of computer science, for example, data base theory and computational learning. This problem can be viewed as the problem of evaluating a discrete function, where to check the value of each variable of the function we have to pay a cost, and the points where the function is defined are associated with a probability distribution. The goal of the problem is to evaluate the function minimizing the cost spent (in the worst case or in expectation). In this Thesis, we present four contributions related to this problem. The first one is an algorithm that achieves an O(log(n)) approximation with respect to both the expected and the worst costs. The second one is a procedure that combines two trees, one with worst costW and another with expected cost E, and produces a tree with worst cost at most (1+p)W and expected cost at most (1/(1-e-p))E, where p is a given parameter. We also prove that this is a sharp characterization of the best possible trade-off attainable, showing that there are infinitely many instances for which we cannot obtain a decision tree with both worst cost smaller than (1+p)OPTW(I) and expected cost smaller than (1/(1-e-p))OPTE(I), where OPTW(I) (resp. OPTE(I)) denotes the cost of the decision tree that minimizes the worst cost (resp. expected cost) for an instance I of the problem. The third contribution is an O(log(n)) approximation algorithm for the minimization of the worst cost for a variant of the problem where the cost of reading a variable depends on its value. Our final contribution is a randomized rounding algorithm that, given an instance of the problem (with an additional integer k > 0) and a parameter 0 < e < 1/2, builds an oblivious decision tree with cost at most (3/(1 - 2e))ln(n)OPT(I) and produces at most (k/e) errors, where OPT(I) denotes the cost of the oblivious decision tree with minimum cost among all oblivious decision trees for instance I that make at most k classification errors.

[pt] As decisões estratégicas das empresas são afetadas pelas oportunidades de investimento e as ações das suas concorrentes. Imai e Watanabe propõem um modelo de opções reais para determinar a decisão de investimento ótima de uma empresa, considerando um jogo de múltiplos estágios com duas firmas sob um processo trinomial multiperíodo em um modelo discreto. Utilizamos o modelo de Imai e Watanabe para determinar o momento estratégico ótimo para investimento em uma nova tecnologia em função da variação do custo de investimento e da demanda inicial, considerando duas empresas concorrentes no mercado brasileiro de telecomunicações, onde uma empresa é líder (L) e a outra é seguidora (S). Considerando que ambas empresas já atuam no mercado e pretendem investir em uma nova tecnologia que permitirá a expansão dos seus negócios, determinamos a curva de gatilho do custo do investimento e da demanda inicial dos serviços que delimitam a estratégia de investimento ótima da empresa líder. / [en] Corporate strategic decisions are affected by investment opportunities and actions of rival firms. Imai and Watanabe suggest a real option and game theory model to determine optimal investment decision considering a two firms multistage game following a multiperiod trinomial process in a discret model. Imai & Watanabe model is used to define this optimal time to invest in a new tecnology as a function of the cost of investment and initial demand. We consider two competing firms in the Brazilian telecommunication market where one firm is leader (L) and the other is the follower (S). We assume both firms are already active in this market and intend to invest in a new technology that will allow them to expand their business. We define a trigger curve of cost of investment and initial demand of the services that define optimal investment strategy for the leading firm.

[pt] Nesta dissertação é apresentado um framework para desenvolver critérios de split para lidar com atributos nominais multi-valorados em árvores de decisão. Critérios gerados por este framework podem ser implementados para rodar em tempo polinomial no número de classes e valores, com garantia teórica de produzir um split próximo do ótimo. Apresenta-se também um estudo experimental, utilizando datasets reais, onde o tempo de execução e acurácia de métodos oriundos do framework são avaliados. / [en] In this dissertation we propose a framework for designing splitting criteria for handling multi-valued nominal attributes for decision trees. Criteria derived from our framework can be implemented to run in polynomial time in the number of classes and values, with theoretical guarantee of producing a split that is close to the optimal one. We also present an experimental study, using real datasets, where the running time and accuracy of the methods obtained from the framework are evaluated.