Séance de cours

Recherche du voisin le plus proche: Johnson-Lindenstrauss Lemma

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

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)

Mikhail Kapralov

Enseignement et PhD Doctorant·es actuel·les Weronika Wrzos-Kaminska, Guy Weissenberg, Davide Mazzali, Ekaterina Kochetkova, Kshiteej Jitesh Sheth A dirigé les thèses EPFL de Amir Zandieh, Aidasadat Mousavifar, Navid Nouri, Jakab Tardos, Grzegorz Adam Gluch, Makarov Mikhail A co-dirigé les thèses EPFL de Paritosh Garg Cours Algorithms II CS-450 Un premier cours de 2eme cycle sur les algorithmes, ce cours a peu de prerequis, mais va vite. Il couvre les techniques principales d'analyse et de

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.

Source officielle

Concepts associés (32)

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.

Fléau de la dimension

Le fléau de la dimension ou malédiction de la dimension (curse of dimensionality) est un terme inventé par Richard Bellman en 1961 pour désigner divers phénomènes qui ont lieu lorsque l'on cherche à analyser ou organiser des données dans des espaces de grande dimension alors qu'ils n'ont pas lieu dans des espaces de dimension moindre. Plusieurs domaines sont concernés et notamment l'apprentissage automatique, la fouille de données, les bases de données, l'analyse numérique ou encore l'échantillonnage.

Rentabilité

La rentabilité est le rapport entre un revenu obtenu ou prévu et les ressources employées pour l'obtenir. La notion s'applique notamment aux entreprises, mais aussi à tout autre investissement. La rentabilité rétrospective est le rapport entre un résultat comptable et les moyens en passifs mis en œuvre pour l'obtenir. La rentabilité prévisionnelle est le rapport entre un gain de trésorerie projeté et la valeur d'un investissement nécessaire pour générer ce gain.

Infrarouge

Le rayonnement infrarouge (IR) est un rayonnement électromagnétique de longueur d'onde supérieure à celle du spectre visible mais plus courte que celle des micro-ondes ou du domaine térahertz. Cette gamme de longueurs d'onde dans le vide de à se divise en infrarouge proche, au sens de proche du spectre visible, de environ, infrarouge moyen, qui s'étend jusqu'à , et infrarouge lointain. Les limites de ces domaines peuvent varier quelque peu d'un auteur à l'autre.

Table de hachage

Une table de hachage est, en informatique, une structure de données qui permet une association clé–valeur, c'est-à-dire une implémentation du type abstrait tableau associatif. Son but principal est de permettre de retrouver une clé donnée très rapidement, en la cherchant à un emplacement de la table correspondant au résultat d'une fonction de hachage calculée en O(1). Cela constitue un gain de temps très important pour les grosses tables, lors d'une recherche ou d'un besoin d'accès aux données en utilisant la clé définie.

Afficher plus

Séances de cours associées (64)

Récapitulation des réseaux neuraux : fonctions d'activation

Couvre les bases des réseaux neuronaux, des fonctions d'activation, de la formation, du traitement d'image, des CNN, de la régularisation et des méthodes de réduction de dimensionnalité.

Gaussian Naive Bayes & K-NN

Couvre les bayes naïfs gaussiens, les voisins les plus proches du K et le réglage hyperparamétrique dans l'apprentissage automatique.

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.

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.

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.

Afficher plus

Concepts associés (32)

Nonlinear dimensionality reduction

Fléau de la dimension