Estimation par noyau

En statistique, l’estimation par noyau (ou encore méthode de Parzen-Rosenblatt ; en anglais, kernel density estimation ou KDE) est une méthode non-paramétrique d’estimation de la densité de probabilité d’une variable aléatoire. Elle se base sur un échantillon d’une population statistique et permet d’estimer la densité en tout point du support. En ce sens, cette méthode généralise astucieusement la méthode d’estimation par un histogramme. Définition Si est un échantillon i.i.d. d'une variable aléatoire, alors l'estimateur non-paramétrique par la méthode du noyau de la densité est : où est un noyau (kernel en anglais) et un paramètre nommé fenêtre, qui régit le degré de lissage de l'estimation. Bien souvent, est choisi comme la densité d'une fonction gaussienne standard (espérance nulle et variance unitaire) : Intuition La méthode de Parzen est une généralisation de la méthode d'estimation par histogramme. Dans un histogramme, la densité en un point es

Sketches, metrics and fast algorithms

Navid Nouri

As it has become easier and cheaper to collect big datasets in the last few decades, designing efficient and low-cost algorithms for these datasets has attracted unprecedented attention. However, in most applications, even storing datasets as acquired has become extremely costly and inefficient, which motivates the study of sublinear algorithms. This thesis focuses on studying two fundamental graph problems in the sublinear regime. Furthermore, it presents a fast kernel density estimation algorithm and data structure. The first part of this thesis focuses on graph spectral sparsification in dynamic streams. Our algorithm achieves almost optimal runtime and space simultaneously in a single pass. Our method is based on a novel bucketing scheme that enables us to recover high effective resistance edges faster. This contribution presents a novel approach to the effective resistance embedding of the graph, using locality-sensitive hash functions, with possible further future applications.The second part of this thesis presents spanner construction results in the dynamic streams and the simultaneous communication models. First, we show how one can construct a

\tilde{O}(n^{2/3})

-spanner using the above-mentioned almost-optimal single-pass spectral sparsifier, resulting in the first single-pass algorithm for non-trivial spanner construction in the literature. Then, we generalize this result to constructing

\tilde{O}(n^{2/3(1-\alpha)})

-spanners using

\tilde{O}(n^{1+\alpha})

space for any

\alpha \in [0,1]

, providing a smooth trade-off between distortion and memory complexity. Moreover, we study the simultaneous communication model and propose a novel protocol with low per player information. Also, we show how one can leverage more rounds of communication in this setting to achieve better distortion guarantees. Finally, in the third part of this thesis, we study the kernel density estimation problem. In this problem, given a kernel function, an input dataset imposes a kernel density on the space. The goal is to design fast and memory-efficient data structures that can output approximations to the kernel density at queried points. This thesis presents a data structure based on the classical near neighbor search and locality-sensitive hashing techniques that improves or matches the query time and space complexity for radial kernels considered in the literature. The approach is based on an implementation of (approximate) importance sampling for each distance range and then using near neighbor search algorithms to recover points from these distance ranges. Later, we show how to improve the runtime, using recent advances in the data-dependent near neighbor search data structures, for a class of radial kernels that includes the Gaussian kernel.

EPFL2022

Integration of Urban Structures in Point Process Analysis

Loïc Gasser

Traditionally, spatial analysis of point pattern has been mostly focused on Euclidean space. As many human related phenomena take place on a network, the assumption of a continuous isotropic space fails to describe events which actually occur on a one-dimensional subset of this space. Thus, recently, researchers have begun integrating network structure constraints to study point patterns. The focus of this report is primarily aimed at the integration of the network structure constraints in studying the first order property of point processes with Kernel Density Estimation (KDE). Two different approaches and the computational methods used to calculate network based kernel density estimation (NetKDE) are described, and are then compared to each other as well as to KDE. An original approach which aim is to replace the conventional search area in flat disk through Euclidean space is introduced. In urban context, polygons of various shapes can be generated and used over the network as an approximation of the potential accessible area for a given distance. As a first case-study, network based density values for various types of economic activities are generated for each building in Geneva. The integration of urban structures in the characterization of neighborhood attributes is an innovative approach which possesses many advantages. A classification based on the attributes generated with this method is performed, and a detailed analysis of the results is carried out. In a second case-study in urban environment, time is considered as an additional dimension in kernel density estimates. A three dimensional KDE approach is used in an attempt to monitor the risk associated with the explosions of improvised explosive devices (IED) in Baghdad through space and time. An animation of the simulations is presented as a visualization technique to detect sensitive areas.

2011

Sketches, metrics and fast algorithms

Navid Nouri

\tilde{O}(n^{2/3})

\tilde{O}(n^{2/3(1-\alpha)})

-spanners using

\tilde{O}(n^{1+\alpha})

space for any

\alpha \in [0,1]

EPFL2022

Sketches, metrics and fast algorithms

Integration of Urban Structures in Point Process Analysis

Supervised Classification with Variable Kernel Estimators

Sketches, metrics and fast algorithms

Integration of Urban Structures in Point Process Analysis

Supervised Classification with Variable Kernel Estimators