Nowadays machine learning (especially deep learning) techniques are being incorporated to many intelligent systems affecting the quality of human life. The ultimate purpose of these systems is to perform automated decision making, and in order to achieve this, predictive systems need to return estimates of their confidence. Powered by the rules of probability, Bayesian inference is the gold standard method to perform coherent reasoning under uncertainty. It is generally believed that intelligent systems following the Bayesian approach can better incorporate uncertainty information for reliable decision making, and be less vulnerable to attacks such as data poisoning. Critically, the success of Bayesian methods in practice, including the recent resurgence of Bayesian deep learning, relies on fast and accurate approximate Bayesian inference applied to probabilistic models. These approximate inference methods perform (approximate) Bayesian reasoning at a relatively low cost in terms of time and memory, thus allowing the principles of Bayesian modelling to be applied to many practical settings. However, more work needs to be done to scale approximate Bayesian inference methods to big systems such as deep neural networks and large-scale dataset such as ImageNet. In this thesis we develop new algorithms towards addressing the open challenges in approximate inference. In the first part of the thesis we develop two new approximate inference algorithms, by drawing inspiration from the well known expectation propagation and message passing algorithms. Both approaches provide a unifying view of existing variational methods from different algorithmic perspectives. We also demonstrate that they lead to better calibrated inference results for complex models such as neural network classifiers and deep generative models, and scale to large datasets containing hundreds of thousands of data-points. In the second theme of the thesis we propose a new research direction for approximate inference: developing algorithms for fitting posterior approximations of arbitrary form, by rethinking the fundamental principles of Bayesian computation and the necessity of algorithmic constraints in traditional inference schemes. We specify four algorithmic options for the development of such new generation approximate inference methods, with one of them further investigated and applied to Bayesian deep learning tasks.

[pt] Sistemas dinâmicos não-lineares são comuns em engenharia. Este tipo de problema é resolvido por integração numérica das equações de movimento ou por métodos analíticos aproximados (métodos de perturbação) ou semi- analíticos como o método do Balanço Harmônico. A integração numérica é um processo lento e oneroso em análises paramétricas. Já os outros métodos aproximados são extremamente rápidos, mas são menos precisos e em pro- blemas com certos tipos de não-linearidade, tais como expoentes fracionários, são de difícil, ou impossível, aplicação. Neste trabalho, são apresentados dois métodos alternativos, baseados nas séries de Taylor, para a análise de sistemas não-lineares. No primeiro método, a resposta é escrita em série de Taylor e propriedades de simetria do sistema no espaço de fase são utilizadas para se determinar a relação freqüência-amplitude ou pontos fixos da resposta. No segundo método a solução é escrita em série de Fourier e as amplitudes dos harmônicos são determinadas da mesma forma que os coeficientes da série de Taylor. A simetria do sistema agora fica implícita na solução em série de Fourier, e a relação freqüência- amplitude ou os pontos fixos da resposta são obtidos utilizando equações suplementares. Através de comparações com outros métodos, mostra-se que os métodos desenvolvidos são de fácil implementação e precisos. Estes possuem as vantagens de serem aplicados a problemas com diversos tipos de não-linearidade e de fornecerem uma resposta em série de Fourier onde as amplitudes são determinadas analiticamente resolvendo-se um sistema de equações algébricas lineares. / [en] Nonlinear dynamical systems are rather common in engineering. This class of problems is usually solved by numerical integration or through the use of ap- proximate analytical methods (perturbation methods) or semi-analytical meth- ods such as the harmonic balance method. The numerical integration is a slow and cumbersome process in parametric analyses. The other methods are usu- ally extremely fast but they are less precise and their application to problems involving certain types of non-linearity, such as fractional power non-linearities, are difficult or even impossible. In this work two alternative methodologies for the analysis of non-linear dynamical systems, based on Taylor series expan- sions, are proposed. In the first method, the solution of the initial value prob- lem is obtained by expanding the response in Taylor series and the symmetries of the response in phase space are used to obtain the frequency-amplitude rela- tion or the fixed points of the steady-state response. In the second method the response is written as a Fourier series and the modal amplitudes are obtained using the same methodology used in the previous method for the determina- tion of the coefficients of the Taylor expansion. The symmetries of the response are implicit in the Fourier series, and supplementary equations are proposed for the determination of the frequency-amplitude relation and the fixed points of the response. Comparisons with other existing methods show that the two proposed methods are precise and can be easily applied to the analysis of sev- eral dynamical systems. The main advantages of the proposed methods are that they can be applied to several types of non-linearities and that analytic expression for the Fourier coefficients can be obtained by the solution of a system of linear algebraic equations.

Dans cette thèse nous étudions deux types de pavages : des pavages par une paire de carres et des pavages sur le réseau tri-hexagonal (Kagome). Nous considérons différents problèmes combinatoires et probabilistes. Nous commençons par le cas des carres 1x1 et 2x2 sur des bandes infinies de hauteur k et obtenons des résultats sur la proportion moyenne des carres 1x1 pour les cas planaire et cylindrique pour k < 11. Nous considérons également des questions échantillonnage et comptage approximatif. Pour obtenir un échantillon aléatoire nous définissons des chaines de Markov pour les pavages par des carres et sur le réseau Kagome. Nous montrons des bornes polynomiales pour le temps de mélange pour les pavages par des carres 1x1 et sxs des régions n log net les pavages Kagome des régions en forme de losange. Nous considérons aussi des chaines de Markov avec des poids w sur les tuiles. Nous montrons le mélange rapide avec des conditions spécifiques sur w pour les pavages par des carres 1x1 et sxs et pavages Kagome. Nous présentons des simulations qui suggèrent plusieurs conjectures, notamment l'existence des régions gelées pour les pavages aléatoires par des carres et sur le réseau Kagome des régions avec des bords non plats. / In this thesis we study two types of tilings : tilings by a pair of squares and tilings on the tri-hexagonal (Kagome) lattice. We consider different combinatorial and probabilistic problems. First, we study the case of 1x1 and 2x2 squares on infinite stripes of height k and get combinatorial results on proportions of 1x1 squares for k < 11 in plain and cylindrical cases. We generalize the problem for bigger squares. We consider questions about sampling and approximate counting. In order to get a random sample, we define Markov chains for square and Kagome tilings. We show ergodicity and find polynomial bounds on the mixing time for nxlog n regions in the case of tilings by 1x1 and sxs squares and for lozenge regions in the case of restrained Kagome tilings. We also consider weighted Markov chains where weights are put on the tiles. We show rapid mixing with conditions on for square tilings by 1x1 and sxs squares and for Kagome tilings. We provide simulations that suggest different conjectures, one of which existence of frozen regions in random tilings by squares and on the Kagome lattice of regions with non flat boundaries.

Lecanosticta acicola is a heterothallic ascomycete that causes brown spot needle blight (BSNB) on native and non-native Pinus spp. in many regions of the world. The aim of this thesis was to elucidate the origin of L. acicola populations in Europe and consider the reproductive mode of the pathogen in affected areas. In order to study the population genetics of L. acicola, eleven polymorphic microsatellite markers were developed. In addition, mating type markers that amplify both mating type idiomorphs (MAT1-1 and MAT1-2) were designed and the protocols for their applications were optimised. Collections of diseased material were obtained from 17 host species in Asia, Europe and America. In total, 201 isolates from diseased pine needles were obtained. All isolates were screened with the microsatellite markers and the mating type idiomorph determined with the mating type markers. For 87 individuals, part of the Translation Elongation Factor 1-alfa gene was sequenced. The isolates from Central America were unique, highly diverse and most likely represent a new cryptic species. The isolates from East Asia formed a discrete group. Two distinct populations were identified in both North America and Europe. Approximate Bayesian Computation analyses strongly suggest independent introductions of two populations from North America into Europe. Microsatellite data and mating type distributions showed the presence of sexual reproduction in North America and in Europe. Results from this thesis have showed that European populations of L. acicola originate from North America. This is the first study of L. acicola populations on a global scale.

vii, 124 p. : ill. A print copy of this thesis is available through the UO Libraries. Search the library catalog for the location and call number. / This dissertation is a study of the relationship between minimal dynamical systems on the product of the Cantor set ( X ) and torus ([Special characters omitted]) and their corresponding crossed product C *-algebras. For the case when the cocyles are rotations, we studied the structure of the crossed product C *-algebra A by looking at a large subalgebra A x . It is proved that, as long as the cocyles are rotations, the tracial rank of the crossed product C *-algebra is always no more than one, which then indicates that it falls into the category of classifiable C *-algebras. In order to determine whether the corresponding crossed product C *-algebras of two such minimal dynamical systems are isomorphic or not, we just need to look at the Elliott invariants of these C *-algebras. If a certain rigidity condition is satisfied, it is shown that the crossed product C *-algebra has tracial rank zero. Under this assumption, it is proved that for two such dynamical systems, if A and B are the corresponding crossed product C *-algebras, and we have an isomorphism between K i ( A ) and K i ( B ) which maps K i (C(X ×[Special characters omitted])) to K i (C( X ×[Special characters omitted])), then these two dynamical systems are approximately K -conjugate. The proof also indicates that C *-strongly flip conjugacy implies approximate K -conjugacy in this case. We also studied the case when the cocyles are Furstenberg transformations, and some results on weakly approximate conjugacy and the K -theory of corresponding crossed product C *-algebras are obtained. / Committee in charge: Huaxin Lin, Chairperson, Mathematics Daniel Dugger, Member, Mathematics; Christopher Phillips, Member, Mathematics; Arkady Vaintrob, Member, Mathematics; Li-Shan Chou, Outside Member, Human Physiology

Metadados bibliográficos duplicados são registros que correspondem a referências bibliográficas semanticamente equivalentes, ou seja, que descrevem a mesma publicação. Identificar metadados bibliográficos duplicados em uma ou mais bibliotecas digitais é uma tarefa essencial para garantir a qualidade de alguns serviços como busca, navegação e recomendação de conteúdo. Embora diversos padrões de metadados tenham sido propostos, eles não resolvem totalmente os problemas de interoperabilidade porque mesmo que exista um mapeamento entre diferentes esquemas de metadados, podem existir variações na representação do conteúdo. Grande parte dos trabalhos propostos para identificar duplicatas aplica uma ou mais funções sobre o conteúdo de determinados campos no intuito de captar a similaridade entre os registros. Entretanto, é necessário escolher um limiar que defina se dois registros são suficientemente similares para serem considerados semanticamente equivalentes ou duplicados. Trabalhos mais recentes tratam a deduplicação de registros como um problema de classificação de dados, em que um modelo preditivo é treinado para estimar a que objeto do mundo real um registro faz referência. O objetivo principal desta tese é o desenvolvimento de um método efetivo e automático para identificar metadados bibliográficos duplicados, combinando o aprendizado de múltiplos classificadores supervisionados, sem a necessidade de intervenção humana na definição de limiares de similaridade. Sobre o conjunto de treinamento são aplicadas funções de similaridade desenvolvidas especificamente para o contexto de bibliotecas digitais e com baixo custo computacional. Os escores produzidos pelas funções são utilizados para treinar múltiplos modelos de classificação heterogêneos, ou seja, a partir de algoritmos de diversos tipos: baseados em árvores, regras, redes neurais artificiais e probabilísticos. Os classificadores aprendidos são combinados através da estratégia de empilhamento visando potencializar o resultado da deduplicação a partir do conhecimento heterogêneo adquirido individualmente pelos algoritmo de aprendizagem. O modelo de classificação final é aplicado aos pares candidatos ao casamento retornados por uma estratégia de blocagem de dois níveis bastante eficiente. A solução proposta é baseada na hipótese de que o empilhamento de classificadores supervisionados pode aumentar a qualidade da deduplicação quando comparado a outras estratégias de combinação. A avaliação experimental mostra que a hipótese foi confirmada quando o método proposto é comparado com a escolha do melhor classificador e com o voto da maioria. Ainda são analisados o impacto da diversidade dos classificadores no resultado do empilhamento e os casos de falha do método proposto. / Duplicated bibliographic metadata are semantically equivalent records, i.e., references that describe the same publication. Identifying duplicated bibliographic metadata in one or more digital libraries is an essential task to ensure the quality of some services such as search, navigation, and content recommendation. Although many metadata standards have been proposed, they do not completely solve interoperability problems because even if there is a mapping between different metadata schemas, there may be variations in the content representation. Most of work proposed to identify duplicated records uses one or more functions on some fields in order to capture the similarity between the records. However, we need to choose a threshold that defines whether two records are sufficiently similar to be considered semantically equivalent or duplicated. Recent studies deal with record deduplication as a data classification problem, in which a predictive model is trained to estimate the real-world object to which a record refers. The main goal of this thesis is the development of an effective and automatic method to identify duplicated bibliographic metadata, combining multiple supervised classifiers, without any human intervention in the setting of similarity thresholds. We have applied on the training set cheap similarity functions specifically designed for the context of digital libraries. The scores returned by these functions are used to train multiple and heterogeneous classification models, i.e., using learning algorithms based on trees, rules, artificial neural networks and probabilistic models. The learned classifiers are combined by stacked generalization strategy to improve the deduplication result through heterogeneous knowledge acquired by each learning algorithm. The final model is applied to pairs of records that are candidate to matching. These pairs are defined by an efficient two phase blocking strategy. The proposed solution is based on the hypothesis that stacking supervised classifiers can improve the quality of deduplication when compared to other combination strategies. The experimental evaluation shows that the hypothesis has been confirmed by comparing the proposed method to selecting the best classifier or the majority vote technique. We also have analyzed the impact of classifiers diversity on the stacking results and the cases for which the proposed method fails.

Dois dos principais fatores do aumento da performance em aplicações single-thread – frequência de operação e exploração do paralelismo no nível das instruções – tiveram pouco avanço nos últimos anos devido a restrições de potência. Neste contexto, considerando a natureza tolerante a imprecisões (i.e.: suas saídas podem conter um nível aceitável de ruído sem comprometer o resultado final) de muitas aplicações atuais, como processamento de imagens e aprendizado de máquina, a computação aproximativa torna-se uma abordagem atrativa. Esta técnica baseia-se em computar valores aproximados ao invés de precisos que, por sua vez, pode aumentar o desempenho e reduzir o consumo energético ao custo de qualidade. No atual estado da arte, a forma mais comum de exploração da técnica é através de redes neurais (mais especificamente, o modelo Multilayer Perceptron), devido à capacidade destas estruturas de aprender funções arbitrárias e aproximá-las. Tais redes são geralmente implementadas em um hardware dedicado, chamado acelerador neural. Contudo, essa execução exige uma grande quantidade de área em chip e geralmente não oferece melhorias suficientes que justifiquem este espaço adicional. Este trabalho tem por objetivo propor um novo mecanismo para fazer computação aproximativa, baseado em reúso aproximativo de funções e trechos de código. Esta técnica agrupa automaticamente entradas e saídas de dados por similaridade, armazena-os em uma tabela em memória controlada via software. A partir disto, os valores quantizados podem ser reutilizados através de uma busca a essa tabela, onde será selecionada a saída mais apropriada e desta forma a execução do trecho de código será substituído. A aplicação desta técnica é bastante eficaz, sendo capaz de alcançar uma redução, em média, de 97.1% em Energy-Delay-Product (EDP) quando comparado a aceleradores neurais. / Two of the major drivers of increased performance in single-thread applications - increase in operation frequency and exploitation of instruction-level parallelism - have had little advances in the last years due to power constraints. In this context, considering the intrinsic imprecision-tolerance (i.e., outputs may present an acceptable level of noise without compromising the result) of many modern applications, such as image processing and machine learning, approximate computation becomes a promising approach. This technique is based on computing approximate instead of accurate results, which can increase performance and reduce energy consumption at the cost of quality. In the current state of the art, the most common way of exploiting the technique is through neural networks (more specifically, the Multilayer Perceptron model), due to the ability of these structures to learn arbitrary functions and to approximate them. Such networks are usually implemented in a dedicated neural accelerator. However, this implementation requires a large amount of chip area and usually does not offer enough improvements to justify this additional cost. The goal of this work is to propose a new mechanism to address approximate computation, based on approximate reuse of functions and code fragments. This technique automatically groups input and output data by similarity and stores this information in a sofware-controlled memory. Based on these data, the quantized values can be reused through a search to this table, in which the most appropriate output will be selected and, therefore, execution of the original code will be replaced. Applying this technique is effective, achieving an average 97.1% reduction in Energy-Delay-Product (EDP) when compared to neural accelerators.

Após a chegada dos conquistadores europeus, as populações nativas americanas foram dizimadas por diversas razões, como guerras e doenças, o que possivelmente levou diversas linhagens genéticas autóctones à extinção. Entretanto, durante essa invasão, houve miscigenação entre os colonizadores e os povos nativos e muitos estudos genéticos têm mostrado uma importante contribuição matrilinear nativa americana na formação da população colonial. Portanto, se muitos indivíduos na atual população urbana brasileira carregam linhagens nativas americanas no seu DNA mitocondrial (mtDNA), muito da diversidade genética nativa perdida durante o período colonial pode ter se mantido, por miscigenação, nas populações urbanas. Assim, essas populações representam, efetivamente, um importante reservatório genético de linhagens nativas americanas no Brasil e em outros países americanos, constituindo o reflexo mais fiel da diversidade genética pré-colombiana em populações nativas. Baseado nisso, este estudo teve como objetivos 1) comparar os padrões de diversidade genética de linhagens nativas americanas do mtDNA em populações nativas do Sul do Brasil e da população urbana (miscigenada) adjacente; e 2) comparar, através de Computação Bayesiana Aproximada (ABC), a história demográfica de ambas populações para chegar a uma estimativa do nível de redução do tamanho efetivo populacional (Ne) das populações indígenas aqui tratadas. Foram utilizados dados já publicados da região hipervariável (HVS-I) do mtDNA de linhagens nativas de 396 indivíduos Nativos Americanos (NAT) pertencentes aos grupos Guarani, Caingangue e Charrua e de 309 indivíduos de populações miscigenadas urbanas (URB) do Sul do Brasil e do Uruguai As análises de variabilidade e estrutura genética, bem como testes de neutralidade, foram feitos no programa Arlequin 3.5 e a rede de haplótipos mitocondriais foi estimada através do método Median-Joining utilizando o programa Network 5.0. Estimativas temporais do tamanho populacional efetivo foram feitas através de Skyline Plot Bayesiano utilizando o pacote de programas do BEAST 1.8.4. Por fim, o programa DIYABC 2.1 foi utilizado para testar cenários evolutivos e para estimar o Ne dos nativos americanos pré- (Nanc) e pós-contato (Nnat), para assim, se estimar o impacto da redução de variação genética causada pela colonização europeia. Os resultados deste estudo indicam que URB é a melhor preditora da diversidade nativa ancestral, possuindo uma diversidade substancialmente maior que NAT, pelo menos na região Sul do Brasil e no Uruguai (H = 0,96 vs. 0,85, Nhap = 131 vs. 27, respectivamente). Ademais, a composição de haplogrupos é bastante diferente entre as populações, sugerindo que a população nativa tenha tido eventos de gargalo afetando os haplogrupos B2 e C1 e super-representando o haplogrupo A2. Em relação à demografia histórica, observou-se que URB mantém sinais de expansão remetendo à entrada na América, contrastando com NAT em que esses sinais estão erodidos, apenas retendo sinais de contração populacional recente. De acordo com as estimativas aqui geradas, o declínio populacional em NAT foi de cerca de 300 vezes (84 – 555). Em outras palavras, a população efetiva nativa amricana nessa região corresponderia a apenas 0,33% (0,18% – 1,19%) da população ancestral– 99,8%, corroborando os achados de outros estudos genéticos e também com os registros históricos. / After the arrival of the European conquerors, the Native American populations were decimated due to multiple reasons, such as wars and diseases, which possibly led many autochtonous genetic lineages to extinction. However, during the European invasion of the Americas, colonizers and indigenous people admixed, and many genetic studies have shown an important Native American matrilineal contribution to the formation of the Colonial population. Therefore, if many individuals in the current urban population harbor Native American lineages in their mitochondrial DNA (mtDNA), much of Native American genetic diversity that have been lost during the Colonial Era may have been mantained by admixture in urban populations. In this case, these populations effectively represent an important reservoir of Native lineages in Brazil and other American countries, constituting the most accurate portrait of pre-Columbian genetic diverstity of Native populations. Based on this, the aims of the presente study were 1) to compare the patterns of genetic diversity of Native American mtDNA lineages in Native populations from Southern Brazil and the surrounding admixed urban populations; and 2) to compare, using Approximate Bayesian Computation (ABC), the demographic history of both groups to estimate the level of reduction in the effective population size (Ne) for the indigenous groups present here. We used mtDNA hypervariable segment (HVS-I) data of indigenous origin already published from 396 Native American individuals (NAT) belonging to the Guarani, Kaingang, and Charrua groups, and 309 individuals from Southern Brazilian and Uruguayan admixed urban populations (URB) The analyzes of variability and genetic structure, as well as the neutrality tests were accomplished using Arlequin 3.5, and the mitochondrial haplotype network estimated through the Median-Joining method available in Network 5.0. Time estimates for effective population size were performed using Bayesian Skyline Plot available in the BEAST 1.8.4 package. Finally, the DIYABC 2.1 software was used to test evolutionary scenarios and to estimate the pre (Nanc) and post-contact (Nnat) Native American Ne, and estimate the impact of the colonization process on the Native American genetic variability. The results indicate that URB is the best predictor of ancestral Native diversity, having substancially greater genetic diversity than NAT, at least in the Southern Brazilian and Uruguayan regions (H = 0.96 vs. 0.85, Nhap = 11 vs. 27, respectively). Moreover, the haplogroup compositions are very distinct between these groups, suggesting that the Native population passed through bottleneck events affecting the haplogroups B2 and C1, and overrepresenting the haplogroup A2. In relation to demographic history, we observed that URB retains signals of population expansion back to the entry in the Americas. In contrast, these signals are eroded in NAT, which maintains only signals of recent population contraction. According to our estimates, the population decline in NAT was around 300x (84 – 555x). In other words, the effective Native American population in this region would correspond to only 0.33% (0.18% – 1.19%) of the ancestral population, corroborating the findings of other genetic studies and historical records.

The topic of the thesis is Search (approximate) methods for detecting alcohol in the human body. The aim of the thesis was to evaluate and compare methods and technical means that are used to detect alcohol in the human body for forensic purposes, self-control, corporate control and other purposes. The theoretical part is focused on the description of the chemical properties of alcohol, its physiological effect, metabolism and occurrence in breath. The theoretical part includes also an overview of methods which are used to detect alcohol in the human body. The practical part of the thesis deals with the availability of detection tools and their basic sorting. On the basis of used methodology, which included a survey of domestic and foreign sources and targeted interview, all gained knowledge were thoroughly evaluated and systematically described. The thesis is structured in a way that it can be used as an overview of this issue for the general public, national institutions, companies and other organizations that try to prevent alcohol addiction and abuse of minors. The thesis could also be beneficial for education as a study material.

Approximate computing has been an emerging programming and system design paradigm that has been proposed as a way to overcome the power-wall problem that hinders the scaling of the next generation of both high-end and mobile computing systems. Towards this end, a lot of researchers have been studying the effects of approximation to applications and those hardware modifications that allow increased power benefits for reduced reliability. In this work, we focus on runtime system modifications and task-based programming models that enable software-controlled, user-driven approximate computing. We employ a systematic methodology that allows us to evaluate the potential energy and performance benefits of approximate computing using as building blocks unreliable hardware components. We present a set of extensions to OpenMP 4.0 that enable the programmer to define computations suitable for approximation. We introduce task-significance, a novel concept that describes the contribution of a task to the quality of the result. We use significance as a channel of communication from domain specific knowledge about applications towards the runtime-system, where we can optimise approximate execution depending on user constraints. Finally, we show extensions to the Linux kernel that enable it to operate seamlessly on top of unreliable memory and provide a user-space interface for memory allocation from the unreliable portion of the physical memory. Having this framework in place allowed us to identify what we call the refresh-by-access property of applications that use dynamic random-access memory (DRAM). We use this property to implement techniques for task-based applications that minimise the probability of errors when using unreliable memory enabling increased quality and power efficiency when using unreliable DRAM.