[pt] Aprendizado de estruturas consiste em aprender um mapeamento de variáveis de entrada para saídas estruturadas a partir de exemplos de pares entrada-saída. Vários problemas importantes podem ser modelados desta maneira. O processamento de linguagem natural provê diversas tarefas que podem ser formuladas e solucionadas através do aprendizado de estruturas. Por exemplo, parsing de dependência envolve o reconhecimento de uma árvore implícita em uma frase. Geração de atributos é uma sub-tarefa importante do aprendizado de estruturas. Geralmente, esta sub-tarefa é realizada por um especialista que constrói gabaritos de atributos complexos e discriminativos através da combinação dos atributos básicos disponíveis na entrada. Esta é uma forma limitada e cara para geração de atributos e é reconhecida como um gargalo de modelagem. Neste trabalho, propomos um método automático para geração de atributos para problemas de aprendizado de estruturas. Este método é guiado por entropia já que é baseado na entropia condicional de variáveis locais de saída dados os atributos básicos. Comparamos experimentalmente o método proposto com dois métodos alternativos para geração de atributos: geração manual e métodos de kernel polinomial. Nossos resultados mostram que o método de geração de atributos guiado por entropia é superior aos dois métodos alternativos em diferentes aspectos. Nosso método é muito mais barato do que o método manual e computacionalmente mais rápido que o método baseado em kernel. Adicionalmente, ele permite o controle do seu poder de generalização mais facilmente do que métodos de kernel. Nós avaliamos nosso método em nove datasets envolvendo cinco tarefas de linguística computacional e quatro idiomas. Os sistemas desenvolvidos apresentam resultados comparáveis aos melhores sistemas atualmente e, particularmente para etiquetagem morfossintática, identificação de sintagmas, extração de citações e resolução de coreferência, obtêm os melhores resultados conhecidos para diferentes idiomas como Árabe, Chinês, Inglês e Português. Adicionalmente, nosso sistema de resolução de coreferência obteve o primeiro lugar na competição Conference on Computational Natural Language Learning 2012 Shared Task. O sistema vencedor foi determinado pela média de desempenho em três idiomas: Árabe, Chinês e Inglês. Nosso sistema obteve o melhor desempenho nos três idiomas avaliados. Nosso método de geração de atributos estende naturalmente o framework de aprendizado de estruturas e não está restrito a tarefas de processamento de linguagem natural. / [en] Structure learning consists in learning a mapping from inputs to structured outputs by means of a sample of correct input-output pairs. Many important problems fit into this setting. Natural language processing provides several tasks that can be formulated and solved as structure learning problems. Dependency parsing, for instance, involves the prediction of a tree underlying a sentence. Feature generation is an important subtask of structure learning which, usually, is partially solved by a domain expert that builds complex discriminative feature templates by conjoining the available basic features. This is a limited and expensive way to generate features and is recognized as a modeling bottleneck. In this work, we propose an automatic feature generation method for structure learning problems. This method is entropy guided since it generates complex features based on the conditional entropy of local output variables given the available input features. We experimentally compare the proposed method with two important alternative feature generation methods, namely manual template generation and polynomial kernel methods. Our experimental findings indicate that the proposed method is more attractive than both alternatives. It is much cheaper than manual templates and computationally faster than kernel methods. Additionally, it is simpler to control its generalization performance than with kernel methods. We evaluate our method on nine datasets involving five natural language processing tasks and four languages. The resulting systems present state-of-the-art comparable performances and, particularly on part-of-speech tagging, text chunking, quotation extraction and coreference resolution, remarkably achieve the best known performances on different languages like Arabic, Chinese, English, and Portuguese. Furthermore, our coreference resolution systems achieve the very first place on the Conference on Computational Natural Language Learning 2012 Shared Task. The competing systems were ranked by the mean score over three languages: Arabic, Chinese and English. Our approach obtained the best performances among all competitors for all the three languages. Our feature generation method naturally extends the general structure learning framework and is not restricted to natural language processing tasks.

[pt] O objetivo dessa dissertação é inferir o caráter das forças que governam os sistemas complexos modelados por equações de Langevin, utilizando quantificadores provenientes da teoria de informação. Avaliamos em detalhes as medidas de entropia de permutação (PE) e de complexidade estatística de permutação (PSC) para duas classes de similaridade de modelos estocásticos, caracterizadas por propriedades de arrasto ou de reversão, respectivamente, empregando-as como referência para a inspeção de séries reais. Encontramos novos parâmetros relevantes dos modelos para as medidas de PE e PSC, em relação a medidas tradicionais de entropia. Determinamos as curvas de PE e PSC de acordo com esses parâmetros para diferentes ordens de permutação n e inferimos as medidas limites para uma ordem arbitrariamente grande. Apesar de a medida PSC apresentar comportamento fortemente dependente da ordem de permutação considerada, encontramos um importante resultado n-invariante, que permite identificar a natureza (de arrasto ou de reversão) das fontes determinísticas subjacentes ao sinal complexo. Concluímos investigando a presença de tendências locais em séries de preços de ações. / [en] The scope of this dissertation is to infer the character of the forces controlling complex systems modeled by Langevin equations, by recourse to information-theory quantifiers. We evaluate in detail the permutation entropy (PE) and the permutation statistical complexity (PSC) measures for two classes of similarity of stochastic models characterized by drifting and reversion properties, respectively, employing them as a framework for the inspection of real series. We found new relevant model parameters for PE and PSC measures as compared to standard entropy measures. We determine the PE and PSC curves according to these parameters for different permutation orders n and infer the limiting measures for arbitrary large order. Although the PSC measure presents a strongly scaledependent behavior, a key n-invariant outcome arises, enabling one to identify the nature (drifting or reversion) of the deterministic sources underlying the complex signal. We conclude by investigating the presence of local trends in stock price series.

[pt] A presente dissertação aborda o algoritmo de Seleção de Variáveis Baseada em Informação Mútua sob Distribuição de Informação Uniforme (MIFS-U) e expõe um método alternativo para estimação da entropia e da informação mútua, medidas que constituem a base deste algoritmo de seleção. Este método tem, por fundamento, a informação mútua quadrática de Cauchy-Schwartz e a entropia quadrática de Rényi, combinada, no caso de variáveis contínuas, ao método de estimação de densidade Janela de Parzen. Foram realizados experimentos com dados reais de domínio público, sendo tal método comparado com outro, largamente utilizado, que adota a definição de entropia de Shannon e faz uso, no caso de variáveis contínuas, do estimador de densidade histograma. Os resultados mostram pequenas variações entre os dois métodos, mas que sugerem uma investigação futura através de um classificador, tal como Redes Neurais, para avaliar qualitativamente tais resultados à luz do objetivo final que consiste na maior exatidão de classificação. / [en] This dissertation approaches the algorithm of Selection of Variables under Mutual Information with Uniform Distribution (MIFS-U) and presents an alternative method for estimate entropy and mutual information, measures that constitute the base of this selection algorithm. This method has, for foundation, the Cauchy-Schwartz quadratic mutual information and the quadratic Rényi entropy, combined, in the case of continuous variables, with Parzen Window density estimation. Experiments were accomplished with real public domain data, being such method compared with other, broadly used, that adopts the Shannon entropy definition and makes use, in the case of continuous variables, of the histogram density estimator The results show small variations among the two methods, what suggests a future investigation through a classifier, such as Neural Networks, to evaluate this results, qualitatively, in the light of the final objective that consists of the biggest sort exactness.

[pt] Neste trabalho apresentaremos a teoria de frações contínuas enfatizando a interação entre a teoria de números (expansões de números, aproximações diofantinas e boas aproximações) e a teoria ergódica. Estudaremos a transformação de Gauss e construiremos uma medida ergódica desta transformação. Usando o Teorema Ergódico de Birkhoff obteremos resultados sobre a expansão em frações contínuas de quase todo número real em [0,1). Obteremos propriedades sobre a aproximação de números reais por racionais, sobre a frequência com que aparecem determinados números na expansão em frações contínuas, etc. Estudaremos também o shift de Bernolli e sua relação com a transformação de Gauss. Finalmente, calcularemos a entropia desta transformação. / [en] We study the theory of continued fractions emphasizing the interaction between theory of numbers (expansion of numbers, diophantine approximations, best approximations) and ergodic theory. We study the Gauss transformation and construct its ergodic measure. Using the Birkhoff Ergodic Theorem we obtain results about the expansion in continued fractions of almost every real number in [0, 1). We obtain properties about the approximation of real numbers by rational ones, the frequency of digits in the expansion by continued fractions, etc. We also study the Bernoulli shift and its relation with the Gauss map. Finally, we calculate the entropy of such a transformation

[pt] Nos anos 50, Henrry Markowitz criou um modelo que maximiza a razão entre a média e o desvio padrão [Markowitz, 1952 & 1959]. Esse modelo é muito utilizado até os dias de hoje. Porém ele supõe que os retornos dos ativos do portifólio sejam normalmente distribuídos, e isso não é tão comum, logo seu uso é limitado. Esse trabalho propõe um modelo mais robusto em termos de risco, que possa ser utilizado sem restrições de distribuições, não necessitando do conhecimento a priori das distribuições e que seja uma aproximação do modelo de Markowitz, caso os retornos dos ativos sejam normalmente distribuídos. Para possibilitar isso, o índice maximizado pelo modelo de Markowitz é escrito como uma função da média e da entropia. A seleção do portifólio é dada pelo portifólio que obtiver o maior índice proposto dentro da amostra selecionada. / [en] In the 50 s, Henrry Markowitz created a model that maximizes the mean to standard deviation ratio [Markowitz, 1952]. This model is largely use in the financial market. However, it assumes that portfolio s equities returns are normally distributed, and this not always happens, therefore limiting its use. This work proposes a more robust model in risk measure that can be used without any distribution constraint, however it reduces to Markowitz model if the assets returns are normal distributed. To make it possible, the index maximized by Markowitz will be written as a function of the mean and the entropy. The portfolio selection is that one witch has the largest proposed index in the selected sample.

[pt] Esta dissertação apresenta resultados teóricos e experimentais relativos ao problema de clusterização de um conjunto de vetores (que possam ser interpretados como distribuições de probabilidade) com o objetivo de minimizar uma medida de impureza da partição resultante. Por meio de uma conexão entre o problema geométrico de k-médias e o problema de clusterização para minimizar a impureza ponderada de Gini da partição, prova-se que este último é NP-completo e APX-difícil. Também analisamos uma família de algoritmos para clusterização com base nas componentes dominantes (as maiores componentes) dos vetores a serem particionados. Mostra-se que, em alguns casos, dois desses algoritmos conseguem obter bons resultados em termos da entropia ponderada da partição resultante, em um tempo bem menor do que os algoritmos considerados como o estado da arte. / [en] We present theoretical and experimental results related to the problem of clustering a set of vectors (which can be interpreted as probability distributions) with the goal of minimizing a weighted impurity measure of the resulting partition. The problem of clustering while minimizing the weighted Gini impurity of the partition is shown to be NP-complete and APX-hard, via a connection with the geometrical k-means problem. We also analyze a family of algorithms for information-theoretic clustering that rely on the dominant (largest) component of the vectors to be clustered. These algorithms are shown to be very fast compared to the state of the art, while able to achieve comparable results in terms of the resulting partition s weighted entropy.

[pt] A Igualdade de Jarzynski (IJ) é um tipo especial de Teorema de Flutuação, de trabalho, que caracteriza sistemas termodinâmicos microscópicos fora do equilíbrio. A IJ pode ser usada como uma calibração de experimentos e simulações, o que nos permite estudar comportamentos não triviais da dinâmica desses sistemas. Um desses comportamentos é a troca de entropia e informação que o sistema realiza junto a um banho térmico de contato. Neste ensejo, modelamos via uma dinâmica não-Markoviana, i.e., uma dinâmica com memória, que leva a fluxos reversos de informação do reservatório para o sistema. / [en] The Jarzynski Equality (JE) is a special kind of Fluctuation Theorem, of work, which characterizes non-equilibrium small thermodynamics systems. The JE can be used as gauge of experiments and simulations allowing us to study the non-trivial behaviours of these systems dynamics. One of these behaviours is the entropy and information flow the system makes in contact with a thermal bath. In this framework, we modelled through a non-Markovian dynamic, i.e., with a memory effect, leading to reverse flows of information from the reservoir to the system.

[pt] Estudaremos dinâmicas simbólicas associadas a alfabetos finitos. Consideraremos seqüências bi-infinitas e espaços com memória finita. Estudaremos propriedades invariantes por conjugação. Analisaremos a relação entre os espaços de seqüências e propriedades de matrizes não negativas. O principal exemplo desta correlação é o Teorema de Perron- Frobenius que relaciona a entropia de um espaço de seqüências e os autovalores de uma matriz não negativa associada ao espaço. Neste contexto, certos grafos e suas propriedades aparecem de forma natural. / [en] We study symbolic dynamics associated to finite alphabets. We consider bi-infinite sequences and spaces with finite memory. We pay attention to properties which are invariant by conjugations. We analyze the relation between spaces of sequences and properties of non-negative matrices. The main example is given by the Perron-Frobenius theorem relating the entropy of a space of sequences and the eigerrvalues of a non-negative matrix associated to the space. In this setting, certain graphs and their properties appear in a natural way.

[pt] Esta tese busca utilizar os novos conceitos físicos relacionados à física do estado sólido e à mecânica estatística - teoria do caos e geometria fractal - na análise do comportamento de sistemas dinâmicos não-lineares. Mais pormenorizadamente, trata-se de estudar o comportamento de um modelo numérico elasto-plástico com função de escoamento de Mohr-Coulomb, usualmente empregado em simulações de materiais geológicos - cimentados ou não -, quando submetido a carregamentos externos, situação esta geralmente encontrada em problemas afeitos à mecânica dos solos e das rochas (p/ex., estabilidade de taludes e escavações subterrâneas). Mostra-se que tal modelo geomecânico de muitos corpos (many-body) interagentes é conduzido espontaneamente, ao longo de sua evolução temporal, à chamada criticalidade auto-organizada (self- organized criticality - SOC), estado caracterizado por apresentar evolução na fronteira entre ordem e caos, sensibilidade extrema a qualquer pequena perturbação, e desenvolvimento de interações espaço-temporais de longo alcance. Como a evolução de qualquer sistema dinâmico pode ser vista como um fluxo ininterrupto de informações entre suas partes constituintes, avaliou-se, para tal sistema, a entropia de Tsallis, formulação original proposta pelo físico brasileiro Constantino Tsallis, do Centro Brasileiro de Pesquisas Físicas (CBPF), tendo se mostrado adequada à sua descrição. Em especial, determinou-se para tal sistema, pela primeira vez, o valor do índice entrópico, que parametriza a aludida forma entrópica alternativa. Ademais, como é característico de sistemas fora do equilíbrio regidos por uma dinâmica de limiar, mostra-se que tal sistema geomecânico, durante o seu desenvolvimento, teve a sua simetria translacional inicial quebrada, sendo substituída pela simetria por escala, auto-semelhante (i.é., fractal). Em decorrência, o modelo exibe a chamada invariância discreta de escala (discrete scale invariance - DSI), fruto do processo mesmo de ruptura progressiva do material heterogêneo. Especificamente, as simulações numéricas sugeriram que o processo de ruptura progressiva do material elasto-plástico se dá por uma transferência multiplicativa de tensões, em diferentes escalas de observação hierarquicamente dispostas, acarretando o aparecimento de sinais bastante peculiares, caracterizados por desvios oscilatórios sistemáticos do padrão em lei de potência, o que possibilita a previsão de sua ruína, quando ainda em fase preparatória. Assim, esta pesquisa mostrou a eficiência de tal método de previsão, aplicado, pela primeira vez, não somente aos resultados das simulações numéricas do referido modelo geomecânico, como aos ensaios de laboratório em rochas sedimentares, realizados no Centro de Pesquisas da Petrobrás (CENPES). Por fim, é interessante assinalar que o material elasto-plástico investigado neste trabalho teve seu comportamento compartilhado por um modelo matemático bastante simples, fundamentado na função binomial multifractal, reconhecida por descrever processos multiplicativos em diferentes escalas. / [en] This thesis aims at applying new concepts from solid state physics and statistical mechanics - chaos theory and fractal geometry - to the study of nonlinear dynamic systems. More precisely, it deals with a two-dimensional continuum elastoplastic Mohr-Coulomb model, commonly used to simulate pressure-sensitive materials (e.g., soils, rocks and concrete) subjected to stress-strain fields, normally found in general soil or rock mechanics problems (e.g., slope stability and underground excavations). It is shown that such many-body system is spontaneously driven to a state at the edge of chaos, called self- organized criticality (SOC), capable of developing long- range interactions in space and long-range memory in time. A new entropic form proposed by C. Tsallis is presented and shown that it is the suitable theoretical framework to deal with these problems. Furthermore, the index q of the Tsallis entropy, which measures the degree of non- additivity of the system, is calculated, for the first time, for an elastoplastic model. In addition, as is usual in non-equilibrium systems with threshold dynamics, the model changes its symmetry, from translational to fractal (that is, self-similar), leading to what is called discrete scale invariance. It is shown that this special type of scale invariance, characterized by systematic oscillatory deviations from the fundamental power-law behavior, can be used to predict the failure of heterogeneous materials, while the process is still being build-up, i.e., from precursory signals, typical of progressive failure processes. Specifically, this framework was applied, for the first time, not only to the elastoplastic geomechanical model, but to laboratory tests in sedimentary rocks as well. Finally, it is interesting to realize that the above- mentioned behaviors are also displayed by the binomial multifractal function, known to adequately describe multiplicative cascading processes.

[pt] Neste trabalho, apresentamos uma metodologia para obter probabilidades de classificação e rebaixamento de equipes em campeonatos de futebol. A metodologia consiste basicamente em quatro etapas. Na primeira etapa, ajustamos modelos de séries temporais para dados de contagem a séries de gols a favor e sofridos pelas equipes em partidas sucessivas do campeonato, utilizando variáveis explicativas para considerar o efeito do mando de campo, da participação de determinados jogadores e de mudanças de técnico. Alguns problemas referentes à construção de intervalos de confiança e testes de hipóteses para os hiperparâmetros dos modelos foram solucionados via bootstrap. Na segunda etapa, obtivemos as distribuições de probabilidade associadas aos resultados das partidas futuras do campeonato, utilizando o Princípio da Máxima Entropia para combinar as distribuições preditivas dos modelos ajustados. Na terceira etapa, utilizamos as distribuições dos resultados das partidas futuras para simular cenários para o campeonato e, na quarta e última etapa, estimamos as probabilidades de classificação e rebaixamento das equipes, pela freqüência relativa da ocorrência destes eventos em um grande número de cenários gerados. A metodologia foi aplicada no Campeonato Brasileiro/1999 e na Copa João Havelange/2000. / [en] In this thesis, we develop a methodology to obtain the probabilities of qualifying and relegating of teams, in soccer championships. The methodology consists of four steps. In the first step, we fit time series models to the series of number of goals scored in soccer matches. We account for the effects of playing at home, soccer players and changes of coaches, by introducing explanatory variables. Confidence intervals and hipothesis tests are obtained by bootstrap. In the second step, we get probability distributions of the future matches results, by combining preditive distributions of the fitted models via the Maximum Entropy Principle. In the third step, we use the distributions of the matches results to generate simulation sceneries for the champhionship. In the forth and last step, we finally estimate the probabilities of qualifying and relegating of the teams, through the relative frequencies of these events, in a great number of sceneries generated. The empirical work was carried out using data from Brazilian Champhionship/1999 and João Havelange Cup/2000.