L'ambition du présent mémoire est la présentation d'un ensemble de principes appelés la théorie PAC-Bayes. L'approche offre des garanties de type PAC aux algorithmes d'apprentissage bayésiens généralisés. Le mémoire traite essentiellement des cas où la distribution prior dépend des données. Le mémoire est divisé en trois chapitres. Le premier chapitre détaille les notions de base en apprentissage automatique. Il s'agit d'idées nécessaires à la bonne compréhension des deux chapitres subséquents. Le deuxième chapitre présente et discute de la théorie PAC-Bayes. Finalement, le troisième chapitre aborde l'idée d'une garantie PAC-Bayes où le prior dépend des données. Il y a deux contributions principales. La première contribution est une formulation analytique du risque empirique espéré pour les distributions elliptiques. La seconde contribution est une extension du travail de Parrado-Hernández et al. (34). En effet, il s'agit du développement d'une garantie PAC-Bayes avec un prior espérance non sphérique. / The ambition of this thesis is to present a set of principles called the PAC-Bayes theory. The approach provides PAC-like guarantees for generalised Bayesian learning algorithms. This thesis deals essentially with cases where the prior distribution is data dependent. The paper is divided into three chapters. The first chapter details the core concepts of machine learning. These are ideas that are necessary for a good understanding of the two subsequent chapters. The second chapter presents and discusses the PAC-Bayes theory. Finally, the third chapter addresses the idea of a PAC-Bayes guarantee where the prior depend on the data. There are two main contributions. The first contribution is an analytical formulation of the empirical expected risk for elliptical distributions. The second contribution is an extension of the work of Parrado-Hernández et al. (34). Indeed, it is the development of a PAC-Bayes guarantee with a non-spherical prior expectation.

Titre de l'écran-titre (visionné le 26 juin 2023) / En apprentissage automatique, des algorithmes sont utilisés pour apprendre des modèles mathématiques à partir de données recueillies afin de résoudre une tâche. Trouver une représentation appropriée pour décrire les données d'entrée est une étape essentielle pour obtenir un résultat favorable. Initialement, les données d'un problème spécifique étaient représentées par des attributs élaborés manuellement dans le cadre d'un processus long et ardu. Cette étape a été révolutionnée avec l'avènement de l'apprentissage de représentations, un ensemble de techniques permettant de construire automatiquement une représentation pour une tâche donnée. En pratique, les succès de l'apprentissage de représentations ont conduit à des percées remarquables dans divers domaines, notamment grâce aux méthodes d'apprentissage profond des dernières années. Cependant, ces réalisations empiriques manquent souvent d'analyse théorique solide pour fournir des garanties statistiques et une compréhension poussée. La théorie de l'apprentissage statistique, telle que la théorie PAC-Bayésienne, est un outil puissant pour étudier les algorithmes d'apprentissage automatique et les performances de généralisation des modèles. La théorie PAC-Bayésienne exprime des garanties de généralisation sur des prédicteurs qui sont construits comme une agrégation de plusieurs prédicteurs plus simples. Dans ce travail, nous nous concentrons sur l'utilisation de la théorie PAC-Bayésienne pour développer de nouvelles techniques d'apprentissage de représentations ayant des propriétés intéressantes. Tout d'abord, nous explorons l'apprentissage par noyau en nous appuyant sur la méthode des attributs aléatoires de Fourier interprétée comme un vote de majorité et analysée dans le cadre PAC-Bayésien. Nous proposons deux approches d'apprentissage : un algorithme d'alignement de noyaux et un apprentissage par mesure de similarité basée sur des points de repère. Ensuite, nous adaptons nos travaux d'apprentissage par noyau à un cadre non supervisé en utilisant des données non étiquetées avec des informations de similarité afin d'apprendre des représentations pertinentes. Finalement, nous analysons les réseaux de neurones profonds avec activation binaire en utilisant la théorie PAC-Bayésienne. Nous développons une approche pour apprendre de tels réseaux et nous obtenons des garanties de généralisation non triviales pour nos modèles. / In machine learning, algorithms are used to learn mathematical models from gathered data to solve a task. Finding a suitable representation to describe the input data is an essential step towards a favorable outcome. Originally, hand-crafted features were designed in a time-consuming process to represent data for a specific problem. This was revolutionized with the advent of representation learning, which is a set of techniques to automatically build a representation for a given task. The practical successes of representation learning led to remarkable breakthroughs in various domains, notably driven by deep learning methods in recent years. However, those empirical achievements often lack a sound theoretical analysis to provide statistical guarantees and in-depth insights. A powerful tool to study machine learning algorithms and the generalization performance of models is statistical learning theory, such as the PAC-Bayesian theory. PAC-Bayes express generalization guarantees on predictors that are built as an aggregation of multiple simpler predictors. In this work, we focus on leveraging the PAC-Bayesian theory to develop novel representation learning techniques with advantageous properties. First, we explore kernel learning by building upon the kernel random Fourier features method interpreted as a majority vote and analyzed in the PAC-Bayesian framework. We propose two learning approaches: a kernel alignment algorithm and a landmarks-based similarity measure learning. Then, we adapt our kernel learning work for an unsupervised setting using unlabeled data with similarity information to learn relevant representations. Finally, we analyze deep neural networks with binary activation using the PAC-Bayesian theory. We develop a framework to train such networks, and we obtain nonvacuous generalization bounds for our approach.

Genervte Nutzer, verunsicherte Admins, panische Mailserver: Die täglich zu Tausenden eintreffenden unerwünschten Mails - Spam - gefährden die Mailinfrastruktur.Der Vortrag wird Vor- und Nachsorgemöglichkeiten für geplagte Nutzer und Administratoren erläutern. Techniken der Spamerkennung werden vorgestellt.

以貝氏方法來處理部分區分(partially-classified)或是失去部分訊息資料的類別抽樣(categorical sampling with censored data)，大部分建立在「誠實回答」(truthful reporting)以及「無價值性失去部分訊息」(non-informative censoring)的前提下。Dr.Jiang(1995)取消以上兩個限制，提出quasi-Bayes method來近似這類問題的貝氏解。另外我們也嘗試利用Gelfand and Smith(1990)針對Gibbs sampler所提出的收斂方法來估計。本文重點在比較此兩種方法的估計值準確性，並考慮先驗參數(prior)對估計精準的影響。

In analysis of the contingency tables, the Fisher's exact test is a very important statistical significant test that is commonly used to test independence between the two variables. However, the Fisher' s exact test is based upon the assumption of the fixed margins. That is, the Fisher's exact test uses information beyond the table so that it is conservative. To solve this problem, we allow the margins to be random. This means that instead of fitting the count data to the hypergeometric distribution as in the Fisher's exact test, we model the margins and one cell using multinomial distribution, and then we use the likelihood ratio to test the hypothesis of independence. Furthermore, using Bayesian inference, we consider the Bayes factor as another test statistic. In order to judge the test performance, we compare the power of the likelihood ratio test, the Bayes factor test and the Fisher's exact test. In addition, we use our methodology to analyse data gathered from the Worcester Heart Attack Study to assess gender difference in the therapeutic management of patients with acute myocardial infarction (AMI) by selected demographic and clinical characteristics.

This thesis investigates language acquisition and evolution, using the methodologies of Bayesian inference and expression-induction modelling, making specific reference to colour term typology, and syntactic acquisition. In order to test Berlin and Kay�s (1969) hypothesis that the typological patterns observed in basic colour term systems are produced by a process of cultural evolution under the influence of universal aspects of human neurophysiology, an expression-induction model was created. Ten artificial people were simulated, each of which was a computational agent. These people could learn colour term denotations by generalizing from examples using Bayesian inference, and the resulting denotations had the prototype properties characteristic of basic colour terms. Conversations between these people, in which they learned from one-another, were simulated over several generations, and the languages emerging at the end of each simulation were investigated. The proportion of colour terms of each type correlated closely with the equivalent frequencies found in the World Colour Survey, and most of the emergent languages could be placed on one of the evolutionary trajectories proposed by Kay and Maffi (1999). The simulation therefore demonstrates how typological patterns can emerge as a result of learning biases acting over a period of time. Further work applied the minimum description length form of Bayesian inference to modelling syntactic acquisition. The particular problem investigated was the acquisition of the dative alternation in English. This alternation presents a learnability paradox, because only some verbs alternate, but children typically do not receive reliable evidence indicating which verbs do not participate in the alternation (Pinker, 1989). The model presented in this thesis took note of the frequency with which each verb occurred in each subcategorization, and so was able to infer which subcategorizations were conspicuously absent, and so presumably ungrammatical. Crucially, it also incorporated a measure of grammar complexity, and a preference for simpler grammars, so that more general grammars would be learned unless there was sufficient evidence to support the incorporation of some restriction. The model was able to learn the correct subcategorizations for both alternating and non-alternating verbs, and could generalise to allow novel verbs to appear in both constructions. When less data was observed, it also overgeneralized the alternation, which is a behaviour characteristic of children when they are learning verb subcategorizations. These results demonstrate that the dative alternation is learnable, and therefore that universal grammar may not be necessary to account for syntactic acquisition. Overall, these results suggest that the forms of languages may be determined to a much greater extent by learning, and by cumulative historical changes, than would be expected if the universal grammar hypothesis were correct.

Zugl.: Dresden, Techn. Univ., Diss., 2009

This thesis investigates language acquisition and evolution, using the methodologies of Bayesian inference and expression-induction modelling, making specific reference to colour term typology, and syntactic acquisition. In order to test Berlin and Kay�s (1969) hypothesis that the typological patterns observed in basic colour term systems are produced by a process of cultural evolution under the influence of universal aspects of human neurophysiology, an expression-induction model was created. Ten artificial people were simulated, each of which was a computational agent. These people could learn colour term denotations by generalizing from examples using Bayesian inference, and the resulting denotations had the prototype properties characteristic of basic colour terms. Conversations between these people, in which they learned from one-another, were simulated over several generations, and the languages emerging at the end of each simulation were investigated. The proportion of colour terms of each type correlated closely with the equivalent frequencies found in the World Colour Survey, and most of the emergent languages could be placed on one of the evolutionary trajectories proposed by Kay and Maffi (1999). The simulation therefore demonstrates how typological patterns can emerge as a result of learning biases acting over a period of time. Further work applied the minimum description length form of Bayesian inference to modelling syntactic acquisition. The particular problem investigated was the acquisition of the dative alternation in English. This alternation presents a learnability paradox, because only some verbs alternate, but children typically do not receive reliable evidence indicating which verbs do not participate in the alternation (Pinker, 1989). The model presented in this thesis took note of the frequency with which each verb occurred in each subcategorization, and so was able to infer which subcategorizations were conspicuously absent, and so presumably ungrammatical. Crucially, it also incorporated a measure of grammar complexity, and a preference for simpler grammars, so that more general grammars would be learned unless there was sufficient evidence to support the incorporation of some restriction. The model was able to learn the correct subcategorizations for both alternating and non-alternating verbs, and could generalise to allow novel verbs to appear in both constructions. When less data was observed, it also overgeneralized the alternation, which is a behaviour characteristic of children when they are learning verb subcategorizations. These results demonstrate that the dative alternation is learnable, and therefore that universal grammar may not be necessary to account for syntactic acquisition. Overall, these results suggest that the forms of languages may be determined to a much greater extent by learning, and by cumulative historical changes, than would be expected if the universal grammar hypothesis were correct.

Thesis (doctoral)--Universiẗat, Frankfurt (Main), 2003.

Diplomová práce se zabývá nevyžádanými e-mailovými dopisy neboli spamem. V práci jsou popsány základy komunikace využívané u elektronické pošty a de?nice spamu. V práci jsou shrnuty druhy spamů a možnosti, jak se nevyžádaným zpravám bránit, a to jak na straně odesílatele, tak na straně příjemce. Naznačeny jsou také postupy, jakými lze tyto obrany obejít. V praktické části je pak ukázáno, jak lze postupy pro obelstění antispamových ?ltrů využít.