Premièrement, nous construisons de tels tests basés sur des approches par bootstrap ou par permutation, et étudions leurs propriétés asymptotiques dans un cadre de processus ponctuels, à travers l'étude du comportement asymptotique des lois conditionnelles des statistiques de test bootstrappée et permutée, sous l'hypothèse nulle ainsi que toute alternative. Nous les validons en pratique par simulation et les comparons à des méthodes classiques en neurosciences. Ensuite, nous nous concentrons sur les tests par permutation, connus pour contrôler non-asymptotiquement leur niveau. Les p-valeurs basées sur la notion de coïncidences avec délai, sont implémentées dans une procédure de tests multiples, appelée méthode Permutation Unitary Events, pour détecter les synchronisations entre deux neurones. Nous validons la méthode par simulation avant de l'appliquer à de vraies données. Deuxièmement, nous étudions les propriétés non-asymptotiques des tests par permutation en termes de vitesse de séparation uniforme. Nous construisons une procédure de tests agrégés, basée sur du seuillage par ondelettes dans un cadre de variables aléatoires à densité. Nous déduisons d'une inégalité fondamentale de Talagrand, une nouvelle inégalité de concentration de type Bernstein pour des sommes permutées aléatoirement qui nous permet de majorer la vitesse de séparation uniforme sur des espaces de Besov faibles et d'en déduire que cette procédure semble être optimale et adaptative au sens du minimax. / On the one hand, we construct such tests based on bootstrap and permutation approaches. Their asymptotic performance are studied in a point process framework through the analysis of the asymptotic behavior of the conditional distributions of both bootstrapped and permuted test statistics, under the null hypothesis as well as under any alternative. A simulation study is performed verifying the usability of these tests in practice, and comparing them to existing classical methods in Neuroscience. We then focus on the permutation tests, well known for their non-asymptotic level properties. Their p-values, based on the delayed coincidence count, are implemented in a multiple testing procedure, called Permutation Unitary Events method, to detect the synchronization occurrences between two neurons. The practical validity of the method is verified on a simulation study before being applied on real data. On the other hand, the non-asymptotic performances of the permutation tests are studied in terms of uniform separation rates. A new aggregated procedure based on a wavelet thresholding method is developed in the density framework. Based on Talagrand's fundamental inequalities, we provide a new Bernstein-type concentration inequality for randomly permuted sums. In particular, it allows us to upper bound the uniform separation rate of the aggregated procedure over weak Besov spaces and deduce that this procedure seems to be optimal and adaptive in the minimax sens.

De multiples problèmes en apprentissage automatique consistent à minimiser une fonction lisse sur un espace euclidien. Pour l’apprentissage supervisé, cela inclut les régressions par moindres carrés et logistique. Si les problèmes de petite taille sont résolus efficacement avec de nombreux algorithmes d’optimisation, les problèmes de grande échelle nécessitent en revanche des méthodes du premier ordre issues de la descente de gradient. Dans ce manuscrit, nous considérons le cas particulier de la perte quadratique. Dans une première partie, nous nous proposons de la minimiser grâce à un oracle stochastique. Dans une seconde partie, nous considérons deux de ses applications à l’apprentissage automatique : au partitionnement de données et à l’estimation sous contrainte de forme. La première contribution est un cadre unifié pour l’optimisation de fonctions quadratiques non-fortement convexes. Celui-ci comprend la descente de gradient accélérée et la descente de gradient moyennée. Ce nouveau cadre suggère un algorithme alternatif qui combine les aspects positifs du moyennage et de l’accélération. La deuxième contribution est d’obtenir le taux optimal d’erreur de prédiction pour la régression par moindres carrés en fonction de la dépendance au bruit du problème et à l’oubli des conditions initiales. Notre nouvel algorithme est issu de la descente de gradient accélérée et moyennée. La troisième contribution traite de la minimisation de fonctions composites, somme de l’espérance de fonctions quadratiques et d’une régularisation convexe. Nous étendons les résultats existants pour les moindres carrés à toute régularisation et aux différentes géométries induites par une divergence de Bregman. Dans une quatrième contribution, nous considérons le problème du partitionnement discriminatif. Nous proposons sa première analyse théorique, une extension parcimonieuse, son extension au cas multi-labels et un nouvel algorithme ayant une meilleure complexité que les méthodes existantes. La dernière contribution de cette thèse considère le problème de la sériation. Nous adoptons une approche statistique où la matrice est observée avec du bruit et nous étudions les taux d’estimation minimax. Nous proposons aussi un estimateur computationellement efficace. / Many problems in machine learning are naturally cast as the minimization of a smooth function defined on a Euclidean space. For supervised learning, this includes least-squares regression and logistic regression. While small problems are efficiently solved by classical optimization algorithms, large-scale problems are typically solved with first-order techniques based on gradient descent. In this manuscript, we consider the particular case of the quadratic loss. In the first part, we are interestedin its minimization when its gradients are only accessible through a stochastic oracle. In the second part, we consider two applications of the quadratic loss in machine learning: clustering and estimation with shape constraints. In the first main contribution, we provided a unified framework for optimizing non-strongly convex quadratic functions, which encompasses accelerated gradient descent and averaged gradient descent. This new framework suggests an alternative algorithm that exhibits the positive behavior of both averaging and acceleration. The second main contribution aims at obtaining the optimal prediction error rates for least-squares regression, both in terms of dependence on the noise of the problem and of forgetting the initial conditions. Our new algorithm rests upon averaged accelerated gradient descent. The third main contribution deals with minimization of composite objective functions composed of the expectation of quadratic functions and a convex function. Weextend earlier results on least-squares regression to any regularizer and any geometry represented by a Bregman divergence. As a fourth contribution, we consider the the discriminative clustering framework. We propose its first theoretical analysis, a novel sparse extension, a natural extension for the multi-label scenario and an efficient iterative algorithm with better running-time complexity than existing methods. The fifth main contribution deals with the seriation problem. We propose a statistical approach to this problem where the matrix is observed with noise and study the corresponding minimax rate of estimation. We also suggest a computationally efficient estimator whose performance is studied both theoretically and experimentally.

В данной работе был разработан и реализован комплексный подход к анализу и интерпретации пользовательских данных, собранных в рамках системы веб-аналитики. Применяя методы машинного обучения и аналитики данных, были исследованы и выявлены ключевые события пользователей, влияющие на определенные бизнес-метрики. Начальные этапы проекта включали сбор и предварительную обработку данных, с последующей кластеризацией для выявления скрытых взаимосвязей и структур. Использовались или тестировались различные библиотеки для объяснимости работы моделей машинного обучении, такие как Eli5 и SHAP. Для решения задачи тестировались кластеризации, включая K-средних, DBSCAN, спектральную кластеризацию и OPTICS. В качестве алгоритмов применялась логистическая регрессия, случайны лес и CatBoost. Применялась нейронная сеть. Для определения значимости признаков использовались методы Permutation Importance, с применением моделей логистической регрессии, случайного леса и нейронной сети. Основным результатом стала разработка скрипта, осуществляющего автоматический сбор, обработку данных и определение наиболее значимых событий. Полученный инструментарий значительно облегчает задачу аналитиков, помогая определять ключевые аспекты поведения пользователей и строить более эффективные стратегии взаимодействия. Применение полученных результатов имеет высокий потенциал для улучшения бизнес–решений и оптимизации работы с пользовательской аудиторией. / In this work, an integrated approach to the analysis and interpretation of user data collected within the framework of a web analytics system was developed and implemented. Using machine learning and data analytics methods, key user events that impact certain business metrics were investigated and identified. The initial stages of the project included data collection and pre-processing, followed by clustering to identify hidden relationships and structures. Various libraries have been used or tested to make machine learning models explainable, such as Eli5 and SHAP. Clusterings including K-means, DBSCAN, spectral clustering, and OPTICS were tested to solve the problem. The algorithms used were logistic regression, random forest and CatBoost. A neural network was used. To determine the significance of features, Permutation Importance methods were used using logistic regression, random forest and neural network models. The main result was the development of a script that automatically collects, processes data and determines the most significant events. The resulting tools greatly facilitate the task of analysts, helping to identify key aspects of user behavior and build more effective interaction strategies. The application of the results obtained has high potential for improving business decisions and optimizing work with the user audience.

The unique problems encountered when analyzing weather data sets - that is, measurements taken while conducting a meteorological experiment- have forced statisticians to reconsider the conventional analysis methods and investigate permutation test procedures. The problems encountered when analyzing weather data sets are simulated for a Monte Carlo study, and the results of the parametric and permutation t-tests are compared with regard to significance level, power, and the average coilfidence interval length. Seven population distributions are considered - three are variations of the normal distribution, and the others the gamma, the lognormal, the rectangular and empirical distributions. The normal distribution contaminated with zero measurements is also simulated. In those simulated situations in which the variances are unequal, the permutation test procedure was performed using other test statistics, namely the Scheffe, Welch and Behrens-Fisher test statistics. / Mathematical Sciences / M. Sc. (Statistics)

壹、引言 近年來，訊號傳送的途徑，已擺脫了傳統上著重管線傳送的優勢；有愈來愈多的訊號 彌漫在廣闊的空間裡，而這種無線式的傳送所需面臨的問題是：不具有排它性，任何 有接收器材的非原始接收者都可以截聽到訊息，由於因應而生的保密技術格外受矚目 ，密碼學（CRYPTOGRAPHY）便是滿足此需要的學問。本論文所探討的排列多項式（PE RMUTATION POLYNOMIAL）是密碼學中重要的工具之一。 貳、論文主體 所謂排列多項式，即是佈於代數體上的多項式，把此多項式當成函數而作用於代數體 （FIELD ）上，如果此函數具有一對一的性質，則是排列多項式。即 ｆ（ｘ）＝ａ。+ ａ1 ｘ1 + ....ａnｘn ≡ Ｆq〔Ｘ〕且 ｆ（ａ）╪ｆ（ｂ），ａ，ｂ≡Ｆｑ，ａ╪ｂ． 在論文中，介紹先進學者對排列多項式的認識。如：LAGRANGE'S INTERPOLATION是利 用函數值來描繪多項式，著名的學者CARLITZ ，利用特殊多項式來合成出排列多項式 ，論文中有更進一步的合成法提出，而HERMITE 跟DICKSON 學者則提出Ft函數其冪次 的變化情形，來判別排列多項式之是否，是最通俗的判別理論。 此外，由吾人所蒐集的資料中發現，在祗有兩項的多項式中，被發現到其它更簡捷快 速的判別方法，故二項式的多項式的探討是本論文的第一主題，對於 k j Ｘ＋ｂｘ ≡Ｆｑ〔Ｘ〕， 給予固定類型的ｑ，ｋ，ｊ情形下，祗須檢定ｂ是否具特 殊性質就可決定是否為排列多項式，這是一種方法。另有學者並不固定ｑ，ｋ，ｊ， 反而從ｑ，ｋ，ｊ數字下手，找尋出某種關連性，其結果使得係數ｂ，只有當ｂ＝０ ，時才有機會是排列多項式，乘下單項式的判別過程，就很容易了。另外還有一種方 法也是找尋ｑ，ｋ，ｊ間的關係，不過其結果在找出：多項式為非排列多項式，是比 較特別的地方。上述三方法，本論文網羅大部份有關論文，綜合各家之長，並適當給 予一同於原作者的新觀點證明方法。 至於本論文第二主題是著名的CARLITZ'S CONJECTURE此預測敘述：對於任何具有最高 冪次是偶數的多項式，必定存在一個自然數ｋ，使得給定的代數體，其元素個數只要 超過ｋ，則此多項式必定不是排列多項式。此預測當degree n=10,12,14, and 2m 時 已被證實為真。本論文僅就n=2m，做系統地探討及重新證明。 參、結語 本論文所論的兩主題，對於佈於代數體上的多項式是否為排列多項式，在判別的過程 上應有相當的助益才是。

在統計學上，高維度常造成許多分析上的問題，如進行多變量迴歸的假設檢定時，當樣本個數小於樣本維度時，其樣本共變異數矩陣之反矩陣不存在，使得檢定無法進行，本文研究動機即為在進行兩群多維常態母體的平均數檢定時，所遇到的高維度問題，並引發在分類上的研究，試圖尋找解決方法。本文研究目的為在兩種不同的正則化方法中，比較何者在檢定與分類上表現較佳。本文研究方法為以 Warton 與 Friedman 的正則化方法來分別進行檢定與分類上的分析，根據其檢定力與分類錯誤的表現來判斷何者較佳。由分析結果可知，兩種正則化方法並沒有絕對的優劣，須視母體各項假設而定。 / High dimensionality causes many problems in statistical analysis. For instance, consider the testing of hypotheses about multivariate regression models. Suppose that the dimension of the multivariate response is larger than the number of observations, then the sample covariance matrix is not invertible. Since the inverse of the sample covariance matrix is often needed when computing the usual likelihood ratio test statistic (under normality), the matrix singularity makes it difficult to implement the test . The singularity of the sample covariance matrix is also a problem in classification when the linear discriminant analysis (LDA) or the quadratic discriminant analysis (QDA) is used. Different regularization methods have been proposed to deal with the singularity of the sample covariance matrix for different purposes. Warton (2008) proposed a regularization procedure for testing, and Friedman (1989) proposed a regularization procedure for classification. Is it true that Warton's regularization works better for testing and Friedman's regularization works better for classification? To answer this question, some simulation studies are conducted and the results are presented in this thesis. It is found that neither regularization method is superior to the other.

Nous avons développé un cryptosystème à clé symétrique hautement sécuritaire qui est basé sur un réseau de substitutions et de permutations. Il possède deux particularités importantes. Tout d'abord, il utilise de très grandes S-Boxes incompressibles dont la taille peut varier entre 256 Kb et 32 Gb bits d'entrée et qui sont générées aléatoirement. De plus, la phase de permutation est effectuée par un ensemble de fonctions linéaires choisies aléatoirement parmi toutes les fonctions linéaires possibles. Chaque fonction linéaire est appliquée sur tous les bits du bloc de message. Notre protocole possède donc une structure simple qui garantit l'absence de portes dérobées. Nous allons expliquer que notre cryptosystème résiste aux attaques actuellement connues telles que la cryptanalyse linéaire et la cryptanalyse différentielle. Il est également résistant à toute forme d'attaque basée sur un biais en faveur d'une fonction simple des S-Boxes. / We developed a new symmetric-key algorithm that is highly secure. Our algorithm is SPN-like but with two main particularities. First of all, we use very large random incompressible s-boxes. The input size of our s-boxes vary between 256 Kb and 32 Gb.Secondly, for the permutation part of the algorithm, we use a set of random linear functions chosen uniformly and randomly between every possible fonctions. The input of these functions is all the bits of the block of messages to encode. Our system has a very simple structure that guarantees that there are no trap doors in it. We will explain how our algorithm is resistant to the known attacks, such as linear and differential cryptanalysis. It is also resistant to any attack based on a bias of the s-boxes to a simple function.

La distance de Kendall-τ compte le nombre de paires en désaccord entre deux permuta- tions. La distance d’une permutation à un ensemble est simplement la somme des dis- tances entre cette permutation et les permutations de l’ensemble. À partir d’un ensemble donné de permutations, notre but est de trouver la permutation, appelée médiane, qui minimise cette distance à l’ensemble. Le problème de la médiane de permutations sous la distance de Kendall-τ, trouve son application en bio-informatique, en science politique, en télécommunication et en optimisation. Ce problème d’apparence simple est prouvé difficile à résoudre. Dans ce mémoire, nous présentons plusieurs approches pour résoudre le problème, pour trouver une bonne solution approximative, pour le séparer en classes caractéristiques, pour mieux com- prendre sa compléxité, pour réduire l’espace de recheche et pour accélérer les calculs. Nous présentons aussi, vers la fin du mémoire, une généralisation de ce problème et nous l’étudions avec ces mêmes approches. La majorité du travail de ce mémoire se situe dans les trois articles qui le composent et est complémenté par deux chapitres servant à les lier. / The Kendall-τ distance counts the number of pairwise disagreements between two permutations. The distance between a permutation and a set is simply the sum of the distances between the considered permutation and the permutations of the set. Given a set of permutations, we want to find the permutation, called median, that minimise that distance to the set. The problem of finding a median of permutations under the Kendall-τ distance, finds applications in bioinformatics, political science, telecommunications and optimization. This simple appearing problem is proven difficult to solve. In this master thesis, we present a few approaches to solve the problem, to find a good approximate solution, to separate it into caracteristic classes, to deepen our understanding of its complexity, to reduce the search space and to accelerate calculations. We also present, at the end of this thesis, a generalization of this problem and we study it with the same approaches. The majority of the work in this thesis is located in the three papers which compose it and is complemented by two chapters, that bound them all together.

Dans cette thèse nous étudions la caractérisation et l'énumération de polyominos définis par des contraintes de convexité et ou d'évitement de motifs. Nous nous intéressons à l'énumération des polyominos k-convexes selon le semi périmètre, qui n'était connue que pour k=1,2. Nous énumérons une sous classe, les polyominos k-parallélogrammes, grâce à une décomposition récursive dont nous déduisons la fonction génératrice qui est rationnelle. Cette fonction génératrice s'exprime à l'aide des polynômes de Fibonacci, ce qui nous permet d'en déduire une bijection avec les arbres planaires ayant une hauteur inférieure ou égale à k+2. Dans la deuxième partie, nous examinons la notion d'évitement de motif, qui a été essentiellement étudiée pour les permutations. Nous introduisons ce concept dans le contexte de matrices de permutations et de polyominos. Nous donnons des définitions analogues à celles données pour les permutations et nous explorons ses propriétés ainsi que celles du poste associé. Ces deux approches peuvent être utilisées pour traiter des problèmes ouverts sur les polyominos ou sur d'autres objets combinatoires. / In this thesis, we consider the problem of characterising and enumerating sets of polyominoes described in terms of some constraints, defined either by convexity or by pattern containment. We are interested in a well-known subclass of convex polyominoes, the k-convex polyominoes for which the enumeration according to the semi-perimeter is known only for k=1,2. We obtain, from recursive decomposition, the generating function of the class of k-convex parallelogram polyominoes, which turns out to be rational. Noting that this generating function can be expressed in terms of the Fibonacci polynomials, we describe a bijection between the class of k-parallelogram polyominoes and the class of planted planar trees having height less than k+3. In the second part of the thesis we examine the notion of pattern avoidance, which has been extensively studied for permutations. We introduce the concept of pattern avoidance in the context of matrices, more precisely permutation matrices and polyomino matrices. We present definitions analogous to those given for permutations and in particular we define polyomino classes, i.e. sets downward closed with respect to the containment relation. So, the study of the old and new properties of the redefined sets of objects has not only become interesting, but it has also suggested the study of the associated poset. In both approaches our results can be used to treat open problems related to polyominoes as well as other combinatorial objects.

Estudamos o problema de obtenção de estimadores/preditores ótimos para combinações lineares de respostas coletadas de uma população finita por meio de amostragem aleatória simples. Nesse contexto, estendemos o modelo misto para populações finitas proposto por Stanek, Singer & Lencina (2004, Journal of Statistical Planning and Inference) para casos em que se incluem erros de medida (endógenos e exógenos) e informação auxiliar. Admitindo que as variâncias são conhecidas, mostramos que os estimadores/preditores propostos têm erro quadrático médio menor dentro da classe dos estimadores lineares não viciados. Por meio de estudos de simulação, comparamos o desempenho desses estimadores/preditores empíricos, i.e., obtidos com a substituição das componentes de variância por estimativas, com aquele de competidores tradicionais. Também, estendemos esses modelos para análise de estudos com estrutura do tipo pré-teste/pós-teste. Também por intermédio de simulação, comparamos o desempenho dos estimadores empíricos com o desempenho do estimador obtido por meio de técnicas clássicas de análise de medidas repetidas e com o desempenho do estimador obtido via análise de covariância por meio de mínimos quadrados, concluindo que os estimadores/ preditores empíricos apresentaram um menor erro quadrático médio e menor vício. Em geral, sugerimos o emprego dos estimadores/preditores empíricos propostos para dados com distribuição assimétrica ou amostras pequenas. / We consider optimal estimation of finite population parameters with data obtained via simple random samples. In this context, we extend a finite population mixed model proposed by Stanek, Singer & Lencina (2004, Journal of Statistical Planning and Inference) by including measurement errors (endogenous or exogenous) and auxiliary information. Assuming that variance components are known, we show that the proposed estimators/predictors have the smallest mean squared error in the class of unbiased estimators. Using simulation studies, we compare the performance of the empirical estimators/predictors obtained by replacing variance components with estimates with the performance of a traditional estimator. We also extend the finite population mixed model to data obtained via pretest-posttest designs. Through simulation studies, we compare the performance of the empirical estimator of the difference in gain between groups with the performance of the usual repeated measures estimator and with the performance of the usual analysis of covariance estimator obtained via ordinary least squares. The empirical estimator has smaller mean squared error and bias than the alternative estimators under consideration. In general, we recommend the use of the proposed estimators/ predictors for either asymmetric response distributions or small samples.