Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Séance de cours

Recherche du voisin le plus proche: Johnson-Lindenstrauss Lemma

Dans cours

CS-450: Algorithms II

A first graduate course in algorithms, this course assumes minimal background, but moves rapidly. The objective is to learn the main techniques of algorithm analysis and design, while building a repertory of basic algorithmic solutions to problems in many ...

Description

Cette séance de cours couvre l'algorithme de recherche le plus proche du voisin, en se concentrant sur le lemme de Johnson-Lindenstrauss pour la réduction de la dimensionnalité. L'instructeur explique le concept de recherche du plus proche voisin et l'importance du lemme de Johnson-Lindenstrauss dans la réduction de la dimensionnalité. La séance de cours traite du processus de prétraitement des données pour améliorer l'efficacité de la recherche et l'utilisation du hachage sensible à la localité pour la recherche approximative du voisin le plus proche. Diverses techniques, telles que les familles de hachage et le hachage sensible, sont explorées pour optimiser le processus de recherche.

Enseignant·e·s (3)

Ola Nils Anders Svensson

Alessandro Chiesa

Alessandro Chiesa is a faculty member in computer science. He conducts research in complexity theory, cryptography, and security, with a focus on the theoretical foundations and practical implementations of cryptographic proofs that are short and easy to verify. He is a co-author of several zkSNARK libraries, and is a co-inventor of the Zerocash protocol. He has co-founded Zcash and StarkWare Industries. He is a recipient of a Sloan Research Fellowship (2021), an Okawa Foundation Research Grant (2020), and Google Faculty Research Awards (2018 and 2017). He was included in MIT Technology Review's "35 Innovators Under 35" list in 2018.

Mikhail Kapralov

Source officielle

Concepts associés (32)

Recherche des plus proches voisins

La recherche des plus proches voisins, ou des k plus proches voisins, est un problème algorithmique classique. De façon informelle le problème consiste, étant donné un point à trouver, dans un ensemble d'autres points, quels sont les k plus proches. La recherche de voisinage est utilisée dans de nombreux domaines, tels la reconnaissance de formes, le clustering, l'approximation de fonctions, la prédiction de séries temporelles et même les algorithmes de compression (recherche d'un groupe de données le plus proche possible du groupe de données à compresser pour minimiser l'apport d'information).

Méthode des k plus proches voisins

En intelligence artificielle, plus précisément en apprentissage automatique, la méthode des k plus proches voisins est une méthode d’apprentissage supervisé. En abrégé KPPV ou k-PPV en français, ou plus fréquemment k-NN ou KNN, de l'anglais k-nearest neighbors. Dans ce cadre, on dispose d’une base de données d'apprentissage constituée de N couples « entrée-sortie ». Pour estimer la sortie associée à une nouvelle entrée x, la méthode des k plus proches voisins consiste à prendre en compte (de façon identique) les k échantillons d'apprentissage dont l’entrée est la plus proche de la nouvelle entrée x, selon une distance à définir.

Locality sensitive hashing

Locality sensitive hashing (LSH) est une méthode de recherche approximative dans des espaces de grande dimension. C'est une solution au problème de la malédiction de la dimension qui apparait lors d'une recherche des plus proches voisins en grande dimension. L'idée principale est d'utiliser une famille de fonction de hachage choisies telles que des points proches dans l'espace d'origine aient une forte probabilité d'avoir la même valeur de hachage. La méthode a de nombreuses applications en vision artificielle, traitement automatique de la langue, bio-informatique.

Réduction de la dimensionnalité

vignette|320x320px|Animation présentant la projection de points en deux dimensions sur les axes obtenus par analyse en composantes principales, une méthode populaire de réduction de la dimensionnalité La réduction de la dimensionnalité (ou réduction de (la) dimension) est un processus étudié en mathématiques et en informatique, qui consiste à prendre des données dans un espace de grande dimension, et à les remplacer par des données dans un espace de plus petite dimension.

Nonlinear dimensionality reduction

Nonlinear dimensionality reduction, also known as manifold learning, refers to various related techniques that aim to project high-dimensional data onto lower-dimensional latent manifolds, with the goal of either visualizing the data in the low-dimensional space, or learning the mapping (either from the high-dimensional space to the low-dimensional embedding or vice versa) itself. The techniques described below can be understood as generalizations of linear decomposition methods used for dimensionality reduction, such as singular value decomposition and principal component analysis.

Afficher plus

Séances de cours associées (33)

Analyse des données textuelles: réduction de la classification et de la dimensionnalité

Explore la classification des données textuelles, en se concentrant sur des méthodes telles que les bayes naïques et les techniques de réduction de la dimensionnalité telles que l'analyse des composantes principales.

Méthodes de réduction des dimensions non linéaires

Explore les méthodes de réduction des dimensions non linéaires préservant les quartiers dans les espaces de dimensions inférieures.

Introduction à l'apprentissage automatique: modèles linéaires

Introduit des modèles linéaires pour l'apprentissage supervisé, couvrant le suréquipement, la régularisation et les noyaux, avec des applications dans les tâches d'apprentissage automatique.

Clustering: Apprentissage sans supervision

Explore la réduction de la dimensionnalité, les algorithmes de clustering et l'état de l'apprentissage automatique.

Comprendre les auto-encodeurs

Explore les autoencodeurs, des mappages linéaires en PCA aux mappages non linéaires, aux autoencodeurs profonds et à leurs applications.

Afficher plus

Concepts associés (32)

Recherche des plus proches voisins

Méthode des k plus proches voisins

Locality sensitive hashing

Réduction de la dimensionnalité

Nonlinear dimensionality reduction

Afficher plus