Apprentissage Automatique et Réseaux Neuronaux - page 31

Nouveau commentaire
 

Cours 17. Synchronisation sans verrous



Cours 17. Synchronisation sans verrous

Charles Leiserson explore le concept de synchronisation sans verrous dans une vidéo YouTube. Il fournit un exemple qui démontre la nécessité d'un ordre linéaire global d'instructions pour assurer une exécution séquentielle, et explique comment l'exclusion mutuelle peut être obtenue grâce à la cohérence séquentielle, en évitant les difficultés et les problèmes potentiels liés à l'utilisation de verrous. Leiserson présente l'algorithme de Peterson comme une solution qui utilise uniquement les opérations de chargement et de stockage pour accéder aux sections critiques sans interférence des processus concurrents. La vidéo couvre également les défis de la synchronisation via la mémoire en raison de la réorganisation du matériel et le concept de clôtures de mémoire pour maintenir l'ordre relatif avec d'autres instructions. Leiserson soutient que la prise en charge de la cohérence séquentielle pour les machines parallèles est bénéfique mais difficile à réaliser pour les concepteurs de matériel.

La deuxième partie de la vidéo traite de l'utilisation des clôtures de mémoire et des instructions de synchronisation pour prévenir les erreurs dans les programmes parallèles. L'orateur explore différentes manières d'implémenter des clôtures de mémoire, implicitement ou explicitement, et l'importance d'une ingénierie et d'une coordination minutieuses entre différentes équipes travaillant sur différents aspects d'un processeur. En outre, le conférencier discute de l'utilisation des instructions CAS dans le cadre de l'algorithme sans verrouillage dans la norme de langage C11 pour implémenter des mutex d'algorithmes d'exclusion mutuelle sans blocage à n fils utilisant uniquement un espace constant. Charles Leiserson explique le problème de l'utilisation de verrous dans un système multithread et la solution consistant à utiliser CAS à la place, car un thread qui maintient le verrou pendant une longue période peut potentiellement bloquer d'autres threads en attente d'accéder à la même ressource. De plus, la vidéo met en évidence le problème potentiel du problème ABA avec la comparaison et l'échange et encourage les personnes intéressées par le sujet à en savoir plus sur les algorithmes sans verrouillage.

  • 00:00:00 et leurs instructions sont entrelacées pour produire un ordre linéaire global de toutes les instructions. C'est l'idée derrière le modèle de mémoire de cohérence séquentielle, qui est le modèle de mémoire le plus important d'un point de vue théorique. Il est important de comprendre les modèles de mémoire car, en l'absence de verrous, le comportement des programmes parallèles dépend du modèle de mémoire. Un exemple présenté dans le cours illustre ce point en demandant s'il est possible que deux processeurs aient tous les deux la valeur 0 après avoir exécuté leur code en parallèle, ce qui dépend du modèle de mémoire utilisé.

  • 00:05:00 Dans cette section, Charles Leiserson discute du concept de synchronisation sans verrous où les charges et les magasins doivent sembler obéir à un ordre linéaire global pour que l'exécution soit séquentielle. Il utilise l'exemple de l'entrelacement de diverses valeurs pour démontrer différents chemins d'exécution qui peuvent se produire et comment le matériel peut faire ce qu'il veut. Il explique également que même s'il peut y avoir de nombreuses façons différentes d'entrelacer des valeurs, il doit apparaître comme si les charges et les magasins suivaient un ordre linéaire pour que l'exécution soit cohérente. En fin de compte, Leiserson conclut qu'il n'y a pas d'exécution qui se termine avec les deux valeurs nulles, et il est intéressant de noter que des ordinateurs modernes, aucun d'entre eux ne fournit une cohérence séquentielle.

  • 00:10:00 Dans cette section, le concept de cohérence séquentielle est abordé, ce qui implique de comprendre la relation qui se produit avant entre les instructions et leur ordre, la relation linéaire entre la connexion de la flèche droite, l'ordre du processeur et le séquencement des instructions. De plus, l'exclusion mutuelle peut être accomplie sans utiliser d'instructions ou de verrous lourds en pensant à la cohérence séquentielle et en implémentant la structure de données partagée grâce à l'utilisation de charges et de magasins. Les notes de cours décrivent des méthodes utilisant des opérations spécialisées telles que tester et définir ou comparer et échanger, mais la solution présentée évite de créer des blocages ou d'autres mauvaises choses qui se produisent lors de l'utilisation de verrous.

  • 00:15:00 Dans cette section, Charles Leiserson explique l'algorithme de Peterson pour réaliser l'exclusion mutuelle dans un programme simultané en utilisant uniquement les opérations de chargement et de stockage. L'algorithme permet à deux processus simultanés, Alice et Bob, d'exécuter du code sans interférer l'un avec l'autre en utilisant un ensemble de variables et un mécanisme de tour de rôle. Le code garantit qu'un seul processus à la fois peut entrer dans une section critique et modifier une ressource partagée. Contrairement aux verrous, l'algorithme de Peterson ne repose pas sur l'acquisition ou la libération d'un verrou et utilise à la place des charges et des magasins pour parvenir à une exclusion mutuelle.

  • 00:20:00 Dans cette section, l'orateur discute de l'algorithme de Peterson pour réaliser l'exclusion mutuelle dans la section critique sans utiliser de verrous. Il explique qu'une seule personne à la fois peut entrer dans la section critique, et l'algorithme garantit que quelqu'un qui veut entrer dans la section critique peut le faire s'il est le seul à vouloir y aller. L'orateur présente ensuite une preuve de l'algorithme, qui consiste à supposer qu'Alice et Bob se retrouvent ensemble dans la section critique et à en déduire une contradiction. La preuve repose sur la relation "arrive avant" et l'ordre du programme des instructions exécutées.

  • 00:25:00 Dans cette section, l'orateur explique le processus de synchronisation sans verrouillage. Ils établissent des chaînes d'instructions et s'assurent qu'elles se produisent dans le bon ordre pour éviter les erreurs de synchronisation. Ils utilisent l'exemple de Bob et Alice voulant accéder à une ressource partagée comme démonstration. Ils expliquent que lors de la synchronisation, les ingénieurs doivent être prudents et examiner les « événements qui se produisent avant » pour s'assurer qu'ils se produisent dans le bon ordre.

  • 00:30:00 Dans cette section, Charles Leiserson discute du concept de vérification de modèle et de son utilisation dans l'analyse des protocoles de réseau, de sécurité et de cache. Il poursuit ensuite en expliquant les propriétés de l'algorithme de Peterson, qui garantit l'absence de famine mais ne fonctionne pas avec plus de deux processus. Leiserson explore également les défis de la synchronisation via la mémoire et le manque de cohérence séquentielle dans les processeurs modernes, ce qui conduit à une cohérence de mémoire détendue et à des difficultés pour obtenir une synchronisation correcte.

  • 00:35:00 est-il sûr de réorganiser les instructions sans causer de problèmes de latence de chargement ? La deuxième contrainte est lorsqu'il n'y a pas de dépendance de données entre les instructions, ce qui signifie que les instructions ne partagent pas de données ou n'utilisent pas le même emplacement en mémoire. Dans ce cas, la réorganisation des instructions peut améliorer les performances et couvrir la latence de surcharge, car la charge peut être effectuée plus tôt et d'autres travaux peuvent être effectués en attendant le résultat. La compréhension de ces concepts au niveau matériel peut aider à raisonner sur les logiciels et à optimiser les performances.

  • 00:40:00 Dans cette section, Charles Leiserson explique le concept de réorganisation en synchronisation sans verrous. Il précise que la réorganisation peut être effectuée en toute sécurité tant qu'il n'y a pas de simultanéité, en particulier lorsque le processeur fonctionne ou qu'il y a des bulles dans le flux d'instructions. En effet, dans les processeurs modernes, le matériel stocke les données dans un tampon et contourne les charges en allant directement au système de mémoire. Cependant, ce contournement peut entraîner des problèmes d'exactitude si l'un des magasins est l'objet en cours de chargement.

  • 00:45:00 Dans cette section, Charles Leiserson explique comment la réorganisation matérielle se produit et pourquoi elle ne satisfait pas la cohérence séquentielle, et comment x86 a un modèle de cohérence mémoire appelé ordre total du magasin, qui est plus faible que la cohérence séquentielle. Les règles pour la commande totale du magasin incluent de ne jamais réorganiser les charges avec les charges, les charges étant vues dans le même ordre par les processeurs externes, les magasins ne sont jamais réorganisés avec les magasins et les charges ne sont réorganisées qu'avec les magasins précédents vers un emplacement différent, mais pas avec les charges précédentes. le même endroit. Les instructions de verrouillage et l'ordre de la mémoire respectent un ordre total.

  • 00:50:00 Dans cette section, l'orateur explique comment la réorganisation des instructions peut violer la cohérence séquentielle et entraîner des valeurs incorrectes. La réorganisation peut se produire à la fois dans le matériel et dans le compilateur, et il est important de savoir que les instructions de verrouillage ne seront pas déplacées avant les autres instructions. L'orateur note également que les chargements peuvent passer avant les magasins s'ils sont à une adresse différente. Le danger de la réorganisation est démontré dans l'algorithme de Peterson, qui pourrait être complètement foutu si certaines réorganisations se produisaient. Par conséquent, il est important d'écrire du code déterministe pour éviter ces problèmes lors de la synchronisation via la mémoire.

  • 00:55:00 Dans cette section, Charles Leiserson aborde le problème de la réorganisation lors de l'écriture de code parallèle et simultané, où il est important d'éviter qu'une charge particulière ne se produise avant un magasin. Pour gérer de tels scénarios, les ingénieurs introduisent des clôtures de mémoire, qui maintiennent un ordre relatif avec d'autres instructions, mais elles se font au prix d'une complexité accrue et de bogues potentiels. Leiserson soutient également qu'il est avantageux pour les machines parallèles de prendre en charge la cohérence séquentielle, mais que c'est un défi à relever pour les concepteurs de matériel.

  • 01:00:00 Dans cette section, l'orateur discute de l'importance des clôtures de mémoire et des instructions de synchronisation pour empêcher les programmes parallèles de rencontrer des erreurs. L'orateur décrit différentes manières d'implémenter les clôtures de mémoire, par exemple explicitement sous forme d'instruction ou implicitement via d'autres instructions de synchronisation telles que le verrouillage et l'échange. Cependant, il existe des cas dans lesquels une barrière de mémoire peut en fait ralentir un programme, ce qui montre l'importance d'une ingénierie et d'une coordination minutieuses entre différentes équipes travaillant sur différents aspects d'un processeur. De plus, l'orateur conseille d'utiliser des variables volatiles et des clôtures de compilateur pour empêcher le compilateur d'optimiser les variables absentes et de provoquer des erreurs dans le code parallèle.

  • 01:05:00 Dans cette section, le conférencier discute de la synchronisation sans verrous dans la norme de langage C11. La norme définit un modèle de mémoire faible, qui permet de déclarer des éléments comme atomiques, nécessitant l'utilisation d'opérations coûteuses telles que la clôture de mémoire ou une comparaison et un échange atomiques pour un algorithme d'exclusion mutuelle sans blocage. Ici, l'instruction CAS (Compare-and-Swap) est explorée dans le cadre de l'algorithme sans verrouillage. L'instruction vérifie si la valeur en mémoire est la même que l'ancienne valeur avant de la remplacer par la nouvelle valeur, le tout de manière atomique. L'utilisation de CAS permet d'implémenter des mutex d'algorithmes d'exclusion mutuelle sans blocage à n threads en utilisant uniquement un espace constant. Une instruction de verrouillage, qui tourne jusqu'à ce qu'elle obtienne la valeur true, est utilisée pour échanger en true indiquant que quelqu'un détient le verrou.

  • 01:10:00 Dans cette section, le professeur Charles Leiserson explique comment utiliser la comparaison et l'échange (CAS) pour résoudre les problèmes de synchronisation. Il montre comment utiliser CAS comme verrou et corrige un bogue dans le code présenté par un étudiant. Il présente ensuite un code incorrect utilisé pour calculer la somme des valeurs dans un tableau, ce qui conduit à une condition de concurrence. Il présente les verrous mutex comme une solution typique et explique le problème potentiel d'un thread échangé après l'acquisition du verrou, conduisant à d'autres threads attendant le verrou, entravant ainsi la progression.

  • 01:15:00 Dans cette section, Charles Leiserson explique le problème de l'utilisation de verrous dans un système multithread et la solution consistant à utiliser CAS à la place. Avec les verrous, un thread peut potentiellement conserver le verrou pendant une longue période, bloquant d'autres threads attendant d'accéder à la même ressource. Cependant, avec CAS, un chargement de x est suivi d'un stockage de x après avoir calculé une temp tout en ayant les variables old et new pour stocker l'ancien résultat et ajouter le résultat temporaire à cette ancienne valeur pour produire une nouvelle valeur qui peut être échangé si l'ancienne valeur n'a pas changé. Charles mentionne également le problème ABA avec la comparaison et l'échange et encourage les personnes intéressées par le sujet à en savoir plus sur les algorithmes sans verrouillage.
 

Cours 18. Langages spécifiques à un domaine et réglage automatique



Cours 18. Langages spécifiques à un domaine et réglage automatique

Dans cette vidéo, le professeur Saman Amarasignhe du département EECS du MIT discute des avantages de l'utilisation de langages spécifiques à un domaine (DSL) et de l'autoréglage dans l'ingénierie des performances. Il souligne l'importance des DSL, qui capturent des domaines spécifiques à un domaine difficiles à décrire dans des langages à usage général, permettant aux programmeurs de tirer parti des connaissances des experts du domaine pour de meilleures performances. Singh discute de l'optimisation des processus de graphes à l'aide de DSL, y compris le partitionnement de graphes et l'importance de la forme du graphe dans le calcul. Il introduit le DSL Halide pour le traitement d'image, qui permet une optimisation rapide du code et une portabilité entre les machines. Il discute de l'utilisation de Halide dans diverses industries comme Google et Adobe. En fin de compte, il souligne l'importance d'expérimenter différentes approches pour optimiser le code tout en se concentrant sur le parallélisme, la localité et le travail redondant.

La vidéo parle également des défis de l'ingénierie des performances et de la recherche des paramètres optimaux pour qu'un programme fonctionne efficacement. L'orateur suggère que le réglage automatique peut résoudre ce problème en recherchant automatiquement le grand espace de paramètres pour trouver les valeurs optimales. Il note que la recherche exhaustive peut être peu pratique et que les solutions basées sur l'heuristique peuvent ne pas être optimales. Le réglage automatique, qui définit un espace de valeurs acceptables et itère en fonction des résultats de performance, peut accélérer le processus de recherche de solutions optimales. L'orateur discute également de l'application de l'autotuning dans la génération d'horaires pour Try, qui a été en mesure de produire des horaires plus efficacement que la recherche exhaustive.

  • 00:00:00 Dans cette section, le professeur Saman Amarasignhe, professeur au département EECS du MIT, parle des langages spécifiques à un domaine et de l'auto-réglage. Il explique que ces langages présentent des avantages techniques car ils capturent des domaines spécifiques à un domaine spécifique qui sont difficiles à décrire dans un langage à usage général. Les langages spécifiques à un domaine sont beaucoup plus faciles à comprendre et à maintenir, et ils permettent au programmeur de tirer parti des connaissances des experts du domaine pour obtenir de très bonnes performances. De plus, s'il est construit correctement, un langage spécifique à un domaine peut laisser la décision de niveau inférieur au compilateur, ce qui simplifie considérablement le processus d'optimisation.

  • 00:05:00 Dans cette section, l'orateur discute de l'utilisation des langages spécifiques au domaine (DSL) dans l'ingénierie des performances. Ils encouragent à laisser les performances au compilateur dans la mesure du possible et introduisent trois langages de programmation/frameworks différents pour le traitement des graphes : Graffiti, Halide et OpenTuner. Ils soulignent que les graphiques sont partout, des recherches Google aux moteurs de recommandation, et approfondissent l'algorithme PageRank utilisé par Google pour classer les pages Web. L'algorithme PageRank examine les voisins d'une page Web et calcule un nouveau classement en fonction de leur influence, montrant l'importance du traitement des graphes dans l'ingénierie des performances.

  • 00:10:00 Dans cette section, l'orateur discute des algorithmes de graphe, qui peuvent impliquer le traitement d'énormes quantités de données et l'itération de calculs pour l'ensemble du graphe. Pour optimiser les performances du code, un DSL peut être utilisé. Le type d'algorithmes utilisés pour le traitement des graphes comprend des algorithmes basés sur la topologie, où le graphe entier participe au calcul, et des algorithmes basés sur les données, où le traitement est effectué sur une petite région ou une partie du graphe. Il existe également plusieurs façons de faire des inversions de graphique, et chaque façon a un ensemble de résultats différent.

  • 00:15:00 Dans cette section, le sujet du partitionnement de graphes est abordé, où un grand graphe est divisé en plus petits morceaux. L'avantage du partitionnement d'un graphe est qu'il permet le parallélisme et qu'il fournit également une bonne localité, ce qui signifie que les nœuds sur lesquels on travaille sont suffisamment petits pour tenir dans le cache. Le partitionnement des graphes a également un impact sur les graphes des réseaux sociaux car ils ont une relation de loi de puissance. Cela signifie que certains nœuds ont plus de connexions ou un impact plus important que d'autres, et lors du traitement de ces graphes, certaines connexions et certains nœuds doivent faire l'objet de plus d'attention compte tenu de leur importance.

  • 00:20:00 Dans cette section, l'orateur discute de l'importance de la forme d'un graphe dans le calcul, en particulier de la façon dont la taille et la localité d'un graphe peuvent affecter l'efficacité des algorithmes de parallélisme. Des facteurs tels que le parallélisme, la localité et le travail supplémentaire nécessaire doivent être soigneusement équilibrés pour obtenir les meilleures performances pour un algorithme donné, et la bonne méthode doit être sélectionnée en fonction du type de graphique, du type d'algorithme et du matériel utilisé. Un langage spécifique au domaine a été développé pour séparer l'algorithme constant des méthodes de traitement afin de mieux optimiser ces facteurs.

  • 00:25:00 cette section, l'orateur explique comment les langages spécifiques au domaine (DSL) peuvent être utilisés pour écrire du code à un niveau supérieur, le rendant plus simple et plus élégant. Ils donnent des exemples de différents algorithmes et comment les DSL fournissent un moyen simple de les calculer. De plus, le conférencier explique comment la planification des DSL peut être optimisée pour obtenir la meilleure vitesse possible, même en permettant un traitement parallèle. Le code peut varier en fonction des modifications du graphe ou de la machine, mais l'algorithme reste le même. Le conférencier insiste sur l'importance des DSL offrant une simplicité de programmation tout en étant suffisamment puissants pour générer des horaires optimisés.

  • 00:30:00 Dans cette section, l'orateur aborde un autre langage spécifique à un domaine, Halide, qui se concentre sur le traitement d'images avec des structures régulières denses. Halide aide à réduire la quantité de programmation nécessaire pour obtenir des performances optimales et augmente la portabilité du programme sur différentes machines. L'orateur fournit un exemple de flou trois par trois pour démontrer le fonctionnement de Halide. Halide a un modèle similaire au langage graphique discuté précédemment en termes d'optimisation des performances grâce à différentes combinaisons de diverses techniques.

  • 00:35:00 Dans cette section, l'orateur discute de l'utilisation des langages spécifiques au domaine (DSL) et de l'autoréglage pour optimiser les performances du code. Il fournit un exemple de filtre d'image qui s'exécute plus rapidement en utilisant un DSL appelé Halide, par rapport à un code C valide. Halide permet de découpler l'algorithme de la planification, ce qui permet une optimisation simple du pipeline de fonctions pures en cours d'exécution. Enfin, l'orateur insiste sur la nécessité d'un compromis entre localité, parallélisme et travail redondant pour obtenir les meilleures performances à partir des ressources informatiques disponibles.

  • 00:40:00 Dans cette section, l'orateur discute de l'importance de la localité en matière de traitement d'image. Lors du traitement d'une grande image, il n'est pas efficace d'appliquer des filtres qui agissent sur l'intégralité de l'image en une seule fois car elle ne tient pas dans le cache. Au lieu de cela, l'orateur suggère de décomposer l'image en sections plus petites et d'appliquer des filtres à chaque section, en se concentrant sur la localité et le parallélisme. Ceci peut être réalisé en utilisant un cadre de planification et en optimisant la bande passante de calcul et la granularité de stockage. Cela peut également nécessiter un travail redondant pour obtenir une meilleure localité et un meilleur parallélisme.

  • 00:45:00 Dans cette section, l'orateur discute des langages spécifiques au domaine et de l'autoréglage, en se concentrant sur l'utilisation de Halide. Halide peut fusionner des fonctions de bibliothèque, ce qui est plus rapide que d'appeler des bibliothèques car il y a plus de localité. Le conférencier montre comment Halide peut optimiser les processus de calcul tels que le calcul de filtres bilatéraux et les algorithmes de segmentation. Dans un exemple, un algorithme de segmentation écrit en MATLAB, qui appelait des bibliothèques optimisées à la main, était 70 fois plus rapide lorsqu'il était écrit en Halide. Halide est une partie importante de Google, et il a été intégré dans les téléphones Android et a été utilisé dans Google Glass.

  • 00:50:00 Dans cette section, l'orateur discute de l'efficacité de l'utilisation de Halide pour le traitement frontal et de la manière dont il est de plus en plus utilisé dans différentes industries. Halide bénéficie d'une augmentation de 4 à 5 % de la vitesse par rapport aux versions précédentes, ce qui est significatif pour Google compte tenu du nombre de vidéos téléchargées. Adobe a également annoncé que des filtres Photoshop entiers sont écrits en Halide. Le processeur d'image Snapdragon et Intel commencent également à utiliser Halide. L'orateur explique également comment Halide et Graph partagent des similitudes en termes de capacité à automatiser l'optimisation, ce qui facilite le travail de l'ingénieur de performance. Cependant, lorsqu'il s'agit d'optimisation algorithmique, il s'agit d'un changement de niveau supérieur qui nécessite des connaissances contextuelles spécifiques, ce qui le rend difficile à automatiser. Néanmoins, des outils tels que les langages programmés offrent aux utilisateurs la possibilité d'essayer différentes approches et d'obtenir de meilleures performances.

  • 00:55:00 Dans cette section, l'orateur discute de la complexité des systèmes informatiques modernes et du fait qu'il n'y a pas une seule bonne façon d'optimiser le code. Ils soulignent l'importance d'essayer différentes approches et l'importance des caches, de la localité et du parallélisme. Ils discutent également de la façon dont les gens de divers domaines, tels que la biologie et la physique, passent beaucoup de temps à optimiser le code plutôt qu'à poursuivre la recherche, car ils sont incapables d'écrire des programmes assez rapidement en raison de la complexité du code. L'orateur suggère que trouver des domaines où les gens passent le plus clair de leur temps à pirater et à créer des abstractions peut être un domaine intéressant à explorer pour la recherche. Dans l'ensemble, l'espace sur lequel opérer pour optimiser les programmes comprend le parallélisme, la localité et le travail redondant, et jouer dans cet espace est crucial pour les ingénieurs de performance.

  • 01:00:00 Dans cette section, le conférencier aborde les défis de l'ingénierie de la performance, qui consiste à trouver les bons paramètres pour qu'un programme fonctionne de manière optimale. Il explique qu'il existe de nombreux paramètres qui peuvent être ajustés, tels que l'allocation de mémoire et la taille des blocs, mais qu'il peut être difficile de déterminer les bonnes valeurs pour chaque paramètre pour chaque programme. Cependant, l'orateur suggère que l'auto-réglage peut résoudre ce problème, en recherchant automatiquement le grand espace de paramètres pour trouver les valeurs optimales. Il explique que les solutions basées sur l'heuristique, qui impliquent des règles de codage en dur pour certaines situations, peuvent fonctionner la plupart du temps mais ne sont pas toujours optimales. L'orateur note également que la construction de modèles du système peut être problématique car le modèle ne tient pas compte de tous les facteurs importants, ce qui peut conduire à des résultats sous-optimaux.

  • 01:05:00 Dans cette section, le conférencier discute des défis de trouver des solutions optimales face à l'évolution de la technologie ou à l'évolution des exigences. Il note qu'il existe une variété d '«heuristiques» que les programmeurs utilisent pour guider leurs solutions, souvent basées sur des directives ou des règles empiriques qui peuvent ne plus être applicables. Une option est la recherche exhaustive, mais cela peut s'avérer peu pratique étant donné le grand nombre de permutations possibles. Pour résoudre ce problème, l'orateur recommande l'utilisation de l'autoréglage comme moyen d'élaguer l'espace de recherche et de trouver plus rapidement des solutions optimales. Le réglage automatique consiste à définir un espace de valeurs acceptables, à choisir au hasard une valeur à tester, puis à itérer en fonction des résultats de performance. OpenTuner est un exemple de framework qui utilise un ensemble de techniques, telles que les grimpeurs et la recherche aléatoire, pour accélérer ce processus itératif.

  • 01:10:00 Dans cette section, le conférencier discute du concept de réglage automatique et de la manière dont il peut être appliqué à la génération de programmes pour Try. En comprenant les graphiques et le rythme impliqués, le réglage automatique peut être utilisé pour générer un calendrier plus efficacement qu'une recherche exhaustive. Cette méthode a permis de produire des horaires en moins de deux heures, et dans certains cas, même mieux que ce que l'on pensait à l'origine être le meilleur horaire possible.
 

Cours 19. Leiserchess Codewalk



Cours 19. Leiserchess Codewalk

Dans cette vidéo YouTube intitulée "19. Leiserchess Codewalk", Helen Xu explique les règles du Lesierchess, un jeu joué par deux équipes dans le but de tirer sur le roi de l'équipe adverse ou de faire tirer votre roi. Le jeu a deux types de mouvements, les mouvements de base et de swat, et une règle Ko qui rend un mouvement illégal s'il annule le mouvement le plus récent de l'adversaire. Xu plonge dans divers aspects du jeu, y compris la méthode de contrôle du temps Fisher, la notation Forsythe-Edwards, l'autotesteur Cloud et l'organisation du projet, l'évaluation et la comparaison des bots à l'aide des évaluations Elo, la génération de mouvements, l'évaluation statique et les algorithmes de recherche tels que alpha-bêta, variation de principe, élagage des sous-arbres et tables de transposition. Elle discute également de l'importance de l'infrastructure de test pour optimiser le programme et le fichier eval.c, qui contient des heuristiques qui évaluent chaque case du plateau en fonction du type de pièce et de sa couleur.

L'orateur se penche également sur l'aspect de la couverture laser du jeu, expliquant le système compliqué de génération de tous les mouvements possibles pour une position basée sur la couleur du joueur à l'aide d'une déclaration while-true. Ils expliquent également l'importance de l'exactitude du code et comment le tester, suggérant la conversion de la représentation pour garantir l'exactitude avant l'optimisation des performances. L'orateur discute également de la grande flexibilité offerte par l'interface Leiserchess UCI, qui permet aux utilisateurs d'éditer des tableaux et des commandes à leur guise, et rassure les téléspectateurs sur le fait que le code mort sera nettoyé et que tout autre bogue doit être signalé pour être corrigé.

  • 00:00:00 Dans cette section, Helen parcourt les règles du jeu Lesierchess et explique comment y jouer. Le jeu est joué par deux équipes, orange et lavande, chaque équipe ayant sept pions et un roi. L'objectif du jeu est de tirer sur le roi de l'équipe adverse ou de faire tirer votre roi. Le jeu propose deux types de mouvements, les mouvements de base et les mouvements de swat. Le jeu a en outre une règle Ko qui rend un mouvement illégal s'il annule le mouvement le plus récent de l'adversaire en revenant simplement à l'endroit où se trouvait l'équipe adverse. Il y a match nul s'il y a eu 50 coups de chaque équipe sans qu'un pion ne soit zappé, la même position se répète ou les deux équipes s'accordent sur le match nul.

  • 00:05:00 Dans cette section, l'orateur explique la méthode de contrôle du temps de Fisher utilisée dans le leiserchess. Chaque joueur commence avec un budget de temps initial et un incrément de temps. Dans l'exemple utilisé, chaque joueur commence avec 60 secondes, et lorsqu'il termine son coup, il obtient 0,5 seconde supplémentaire. Mais le délai réel peut être n'importe quoi. L'orateur montre ensuite comment jouer au leiserchess en demandant au public de suggérer des mouvements à la mandarine pour zapper le pion en F5 tout en évitant les contre-attaques. Cependant, l'orateur met en garde contre les subtilités du jeu, comme tuer naïvement toutes les pièces, car cela pourrait ouvrir l'adversaire.

  • 00:10:00 Dans cette section, Helen Xu discute de la notation Forsythe-Edwards en tant qu'outil de représentation d'une position d'échecs à l'aide d'une chaîne, ce qui est utile à des fins de débogage, permettant de revenir facilement à une position spécifique. Elle explique également comment lire les journaux de parties d'échecs, où elle décompose chaque coup et leurs annotations correspondantes. De plus, elle montre comment utiliser le serveur de mêlée pour tester les bots avec d'autres équipes de la classe, ainsi que comment défier d'autres équipes et voir les matchs joués.

  • 00:15:00 Dans cette section, Helen Xu discute de l'autotesteur Cloud et de l'organisation du projet pour Lesierchess. Alors que le serveur de mêlée n'autorise qu'un seul jeu à la fois, l'autotesteur Cloud peut exécuter plusieurs jeux et binaires sur un contrôle de temps qui peut être personnalisé selon les préférences de chaque utilisateur. L'organisation du projet dans le référentiel comprend les répertoires doc, auto tester, pgnstates, tests, player et webgui. Le testeur automatique est un testeur automatique local Java utilisé pour tester les modifications localement, tandis que dans le répertoire des tests, des configurations peuvent être spécifiées pour les tests automatiques. Helen Xu présente également l'interface thoracique universelle (UCI), un protocole de communication utilisé par Lesierchess pour s'interfacer avec le testeur automatique.

  • 00:20:00 Dans cette section, l'orateur explique comment les bots seront mesurés et comparés à l'aide des cotes Elo, qui est un système de notation basé sur le niveau de compétence relatif dans les jeux à somme nulle. La cote Elo n'est pas uniquement basée sur le temps, mais également sur les nœuds par seconde recherchés à l'aide de l'UCI. L'orateur plonge ensuite plus en détail sur le jeu, comme la génération de mouvements, la représentation du tableau et la structure utilisée pour stocker la position. De plus, le mouvement est représenté à l'aide de 28 bits, qui incluent le type de pièce, l'orientation, le carré, le carré intermédiaire et les deux carrés. L'implantation de référence génère tous les mouvements en fonction du tour en parcourant le tableau et en générant tous les mouvements à partir de cette pièce particulière. L'orateur mentionne l'utilisation de la fonction de débogage perft pour s'assurer que la génération de mouvement modifiée renvoie les mêmes mouvements à partir de chaque position.

  • 00:25:00 Dans cette section, l'orateur explique comment déterminer si un mouvement est bon grâce à une évaluation statique, qui génère un score basé sur une position à l'aide d'heuristiques. Les heuristiques incluent celles axées sur le roi, les pions et la distance, et peuvent aider à déterminer si une position est bonne ou non. L'orateur explique également comment les programmes de jeu utilisent des arbres de recherche pour jouer au jeu et choisir le meilleur coup en fonction de l'évaluation. Pour réduire le nombre de nœuds, l'orateur détaille la recherche de quiescence et la recherche min-max, ce qui peut améliorer le nombre de nœuds évalués et conduire à de meilleures performances.

  • 00:30:00 Dans cette section, l'orateur aborde l'algorithme appelé alpha beta, qui est utilisé lors d'une recherche à partir d'un nœud avec une fenêtre alpha beta. Si la valeur de la recherche tombe en dessous de l'alpha, le mouvement n'est pas assez bon et vous continuez à chercher. La bêta signifie essentiellement qu'un côté essaie de maximiser et l'autre essaie de minimiser. Par conséquent, si la valeur tombe au-dessus de la bêta, vous générez alors un seuil de bêta, car l'adversaire ne vous laisserait pas faire ce mouvement, car ce serait trop bien. L'orateur explique ensuite le principe de la recherche de variation, qui suppose que le premier coup est le meilleur, et vous lancez une recherche de reconnaissance, également appelée recherche de fenêtre zéro, sur les coups restants pour vérifier qu'ils sont pires. Cette méthode de recherche est une variante de l'algorithme alpha-bêta.

  • 00:35:00 Dans cette section, le concept d'élagage des sous-arbres dans les algorithmes de recherche minimax est discuté. L'idée derrière l'élagage des sous-arbres est de supprimer les sous-arbres qui ont des scores inférieurs au meilleur score trouvé jusqu'à présent. Cela réduit le nombre de nœuds évalués et accélère le processus de recherche. L'adversaire recherche également le meilleur coup et essaie de minimiser les scores du joueur. L'équilibre entre maximiser le score du joueur et minimiser le score de l'adversaire est crucial, et le but est de trouver un mouvement qui soit bon pour le joueur et aussi quelque chose que l'adversaire autoriserait.

  • 00:40:00 Dans cette section, Helen Xu explique le concept d'élagage des variations principales où l'hypothèse est faite que le sous-arbre le plus à gauche est le meilleur chemin et des sorties précoces sont prises si l'hypothèse est vraie. Si l'hypothèse est fausse, le sous-arbre entier doit être recherché. La recherche Scout est utilisée pour l'appliquer de manière récursive aux sous-arbres inférieurs, avec des passes initiales pour vérifier les hypothèses. Cette méthode améliore l'élagage et traite la majeure partie de l'arborescence du jeu sans aucune recherche de fenêtre.

  • 00:45:00 Dans cette section, nous découvrons les optimisations de recherche pour le programme Leiserchess. L'une des optimisations les plus importantes est l'utilisation d'une table de transposition pour stocker les positions précédemment rencontrées, ce qui permet de gagner du temps en évitant les recherches inutiles. D'autres optimisations incluent l'utilisation du hachage Zobrist pour générer des hachages uniques pour chaque position, la table des mouvements tueurs pour stocker les bons mouvements afin qu'ils n'aient pas à être recalculés, et l'élagage futile pour ignorer les mouvements d'exploration qui n'augmenteraient pas le score alpha. La mise en place d'un meilleur livre d'ouverture est également recommandée pour mémoriser les positions pré-calculées en début de partie et gagner du temps dans la recherche.

  • 00:50:00 Dans cette section, l'orateur discute de quelques outils utiles pour optimiser un programme d'échecs, y compris des livres d'ouverture et des bases de données de fin de partie qui peuvent être pré-calculées. Il est important de tester et d'avoir une bonne infrastructure de test pour pouvoir innover et progresser sans problèmes de débogage. L'utilisation de tables de transposition dans la programmation parallèle rend important de pouvoir les désactiver à des fins de test, et il est recommandé d'effectuer des recherches à profondeur fixe lors des tests. Dans l'ensemble, disposer d'une bonne infrastructure de test est crucial pour progresser et éviter des problèmes de débogage importants.

  • 00:55:00 Dans cette section, l'orateur discute du fichier eval.c du projet Leiserchess et comment il peut sembler écrasant à première vue en raison de sa taille et de sa complexité. Cependant, au fur et à mesure que les utilisateurs se familiariseront avec lui, ils gagneront en confiance dans la gestion d'un morceau de code de taille décente. Le fichier eval.c contient des heuristiques telles que p entre, p central, k face et k agressif qui évaluent chaque case du plateau en fonction du type de pièce et de sa couleur. L'heuristique p entre détermine si un pion est entre les deux rois, tandis que p central donne un bonus basé sur la proximité du pion par rapport au centre du plateau. Les heuristiques k face et k agressive donnent des bonus en fonction de l'orientation du roi et de sa distance par rapport à l'adversaire et aux bords du plateau.

  • 01:00:00 Dans cette section, l'orateur explique la couverture laser, qui est un aspect compliqué du jeu. La couverture laser génère tous les mouvements possibles d'une position particulière en fonction de la couleur du joueur. Ensuite, il fournit une liste de mouvements, et l'orateur explique comment cette carte remplit sa fonction avec une déclaration while-true. Le chemin laser rebondit sur certains pions tout en dessinant le chemin et augmente la distance pour chaque case. Après avoir généré la carte, le processus est répété et la distance est divisée par la distance réelle du laser. Ce système compliqué optimise les itérations nécessaires dans la méthode d'évaluation pour trouver chaque pièce sur le plateau, ce qui ralentit le processus, et l'orateur ajoute que représenter le plateau différemment et affirmer que les deux fonctions de conversion donnent le même résultat est une bonne façon de faire décisions d'optimisation.

  • 01:05:00 Dans cette section de la vidéo, les intervenants discutent de l'importance de maintenir l'exactitude du code et de la façon de le tester. Ils expliquent que la conversion d'une représentation à une autre peut ralentir le processus mais est nécessaire pour garantir l'exactitude avant d'optimiser les performances. Une façon de tester l'exactitude consiste à suivre le nombre de nœuds et à s'assurer qu'ils restent les mêmes après avoir apporté des modifications. Ils montrent également comment exécuter le code et montrent l'interface UCI dans Lesierchess.c, qui vous permet de définir des valeurs pour diverses choses sans avoir à recompiler le binaire à chaque fois. Enfin, ils passent en revue un tableau d'heuristiques et expliquent comment spécifier des valeurs pour le testeur automatique.

  • 01:10:00 Dans cette section, l'orateur discute de la grande flexibilité que le jeu Leiserchess offre pour l'édition des tables et des commandes via l'interface UCI. Cela permet aux utilisateurs d'accéder et de mettre en œuvre toutes les commandes qu'ils souhaitent, y compris de nouvelles heuristiques, et de contrôler l'analyse et la mise en œuvre. Bien qu'il existe du code mort, le professeur rassure les téléspectateurs sur le fait qu'il sera nettoyé et que tout autre bogue doit être signalé pour être corrigé. Enfin, il déclare que même si le projet n'est peut-être pas amusant à chaque minute, il procure globalement beaucoup de plaisir.
 

Cours 20. Parallélisme spéculatif & Leiserchess



20. Parallélisme spéculatif et Leiserchess

Dans cette vidéo YouTube intitulée "20. Speculative Parallelism & Leiserchess", l'instructeur présente le concept de parallélisme spéculatif, qui consiste essentiellement à deviner de manière préventive que certaines tâches peuvent être effectuées en parallèle et peuvent aboutir à un code plus rapide. Cependant, l'orateur prévient que ce code est non déterministe et ne doit être utilisé que lorsque cela est nécessaire, tout en mettant en garde contre son utilisation dans les cas où un meilleur code de série pourrait être utilisé. Une partie importante de la vidéo tourne autour de la discussion des recherches alpha-bêta parallèles, ce qui implique d'élaguer l'arbre de jeu pour optimiser le temps de recherche, et parle également des différentes structures de données et heuristiques utilisées dans le processus d'évaluation des algorithmes de recherche, en particulier pour éviter le cycle et la quiescence. recherche. La vidéo aborde également les avantages de l'approfondissement itératif et comment il conduit à un meilleur ordre des mouvements pour les recherches, tout en discutant du hachage Zobrist, une technique d'optimisation utilisée dans les algorithmes de recherche impliquant une valeur de hachage unique pour chaque position sur l'échiquier avec les mêmes pièces.

Cette vidéo traite également de diverses techniques d'optimisation pour les moteurs d'échecs telles que les tables de transposition, les réductions de coups tardifs et l'utilisation de bitboards pour la génération de coups. L'orateur parle également du sujet du "parallélisme spéculatif et du Leiserchess" où il conseille aux programmeurs d'évaluer si un mouvement affecte la trajectoire du laser et de rechercher la "couverture laser". L'orateur suggère de laisser les anciennes représentations dans le code et d'utiliser des programmes pour tester les changements. Ils ont également développé une heuristique pour mesurer la distance entre un laser et le roi dans Leiserchess. D'autres suggestions d'optimisation incluent la recherche d'un meilleur moyen d'évaluer la proximité de l'adversaire avec le laser du joueur et l'optimisation du tri des mouvements. Enfin, l'importance de refactoriser et de tester correctement le code est discutée.

  • 00:00:00 Dans cette section, l'instructeur présente le concept de parallélisme spéculatif comme moyen d'optimiser le code et de le faire fonctionner plus rapidement. Cela implique de deviner que certaines tâches peuvent être effectuées en parallèle, même si elles sont intrinsèquement en série, ce qui peut entraîner des efforts inutiles si la supposition s'avère incorrecte. L'instructeur fournit un exemple de seuillage d'une somme et montre une optimisation simple en quittant tôt si la somme partielle dépasse un seuil, bien que cela introduit une branche prévisible qui pourrait encore ralentir le code.

  • 00:05:00 Dans cette section, l'orateur explique comment atténuer le problème d'ajouter trop dans la boucle interne lors d'un fonctionnement en parallèle. Ils expliquent que l'extraction à ciel ouvert peut être utilisée pour remplacer la boucle de n itérations par une boucle de n sur quatre itérations par une boucle interne de quatre itérations, tout en vérifiant également si le seuil a été dépassé toutes les quatre itérations pour minimiser le coût de le cheque. Pour paralléliser une boucle court-circuitée, le locuteur ajoute un indicateur d'abandon au code et l'utilise de manière récursive pour vérifier si la somme est supérieure à une limite et n'a pas été interrompue avant de définir l'indicateur sur vrai. En vérifiant le drapeau avant de le placer, ils évitent une course à la détermination et empêchent les véritables courses au partage.

  • 00:10:00 Dans cette section, la vidéo traite du parallélisme spéculatif, c'est-à-dire lorsqu'un programme prédit qu'il devra effectuer un travail parallèle et génère un travail préventif. Ce code est non déterministe et ne doit être utilisé à des fins de performance que lorsque cela est nécessaire. Il est essentiel de réinitialiser l'indicateur d'abandon et de ne pas générer de travail spéculatif à moins qu'il n'y ait peu d'autre possibilité de parallélisme et qu'il y ait de bonnes chances qu'il soit nécessaire. La vidéo met en garde contre l'utilisation du parallélisme spéculatif dans les cas où un meilleur code série pourrait être utilisé, car cette approche conduit souvent à plus de travail sans accélération. Enfin, un théorème est référencé, qui souligne que pour le parallélisme, la probabilité que le travail soit inutile doit être inférieure au nombre de processeurs utilisés.

  • 00:15:00 Dans cette section, la discussion est centrée sur les recherches alpha-bêta parallèles, qui impliquent d'élaguer l'arborescence du jeu pour optimiser le temps de recherche. Burkhardt Manin et ses étudiants ont observé que dans un arbre le mieux ordonné, le degré de chaque nœud est soit 1 soit maximal. Leur idée était de supposer que le meilleur coup était sélectionné après que le premier enfant n'ait pas réussi à générer un seuil bêta. Cela permet de rechercher en parallèle les enfants restants sans perdre de travail. L'heuristique dans le code aide à garantir que les choses sont faites dans le bon ordre, comme l'utilisation de l'algorithme de pondération des jeunes frères et sœurs pour sélectionner le meilleur mouvement, même s'il est à une profondeur moindre. L'algorithme interrompt également les sous-calculs lorsqu'ils s'avèrent inutiles.

  • 00:20:00 Dans cette section de la vidéo, l'orateur discute du mécanisme consistant à grimper périodiquement dans l'arbre pour vérifier les ancêtres qui ont été avortés en parallélisation et éviter de gaspiller du travail. Ils suggèrent d'avoir un compteur ou un paramètre vaudou pour déterminer la fréquence de vérification car arracher l'arbre a un coût. L'orateur parle aussi des structures de données utilisées dans la recherche comme la table de transposition qui peut provoquer des courses dans la parallélisation. Ils suggèrent de le répliquer pour chaque travailleur ou de le verrouiller pour éviter les courses de données. Enfin, l'orateur recommande d'avoir un moyen de désactiver la spéculation et d'autres parties non déterministes du code pour déboguer plus facilement.

  • 00:25:00 Dans cette section, l'orateur parle d'un programme qui a failli remporter le championnat du monde d'échecs par ordinateur en 1999. Ils ont suggéré un changement de règle que tout le monde a accepté, mais ils ont ensuite perdu face au célèbre ordinateur IBM Deep Blue. Ils fonctionnaient sur un supercalculateur de 1824 nœuds au Sandia National Labs, et leur seule perte était Deep Blue. Ils ont décidé de laisser une course dans la table de transposition dans leur programme sans inclure de verrous pour accéder à la table car cela ralentirait le programme. Ils ont calculé que les probabilités qu'une course affecte la valeur qu'ils choisiraient et finissent par affecter le résultat du tournoi étaient faibles.

  • 00:30:00 Dans cette section de la vidéo, l'orateur discute de trois structures de données qui sont importantes pour la prise de décision dans l'IA aux échecs. Le premier est l'heuristique "tueur", qui garde une trace des meilleurs mouvements à une profondeur de code donnée et a tendance à être de nature répétitive. La seconde est la table des "meilleurs coups", qui ordonne tous les coups de rang inférieur en fonction de données statistiques. Les deux structures de données sont partagées et doivent être gérées correctement lors de la parallélisation du code. La structure de données finale est le livre d'ouverture, qui pré-calcule les meilleurs coups au début de la partie. Cependant, l'orateur suggère qu'il y a des fruits plus bas que le livre d'ouverture et que statistiquement, la plupart des jeux ne durent pas assez longtemps pour qu'un livre d'ouverture soit bénéfique.

  • 00:35:00 Dans cette section, l'orateur discute de la stratégie de construction de livres d'ouverture dans Leiserchess, un jeu où les équipes essaient de créer les robots les plus puissants qui jouent aux échecs. L'orateur note que certaines équipes ont eu du succès en créant un livre d'ouverture solide qui leur permet de gagner grâce à un départ fantastique. Ils suggèrent également qu'il est plus efficace de conserver des livres d'ouverture séparés pour chaque côté plutôt que d'en utiliser un pour les deux. De plus, l'orateur recommande d'ajouter un léger caractère aléatoire au code pour éviter la prévisibilité, mais prévient qu'il n'est pas nécessaire d'optimiser pour cela pendant la première version bêta. Enfin, ils suggèrent la stratégie d'approfondissement itératif qui consiste à effectuer des recherches à différentes profondeurs jusqu'à l'expiration du contrôle temporel. L'orateur note que c'est une bonne stratégie puisque la quantité de travail avec chaque profondeur augmente de façon exponentielle, mais les informations importantes s'accumulent au cours des premières profondeurs.

  • 00:40:00 Dans cette section, la vidéo se penche sur les avantages de l'approfondissement itératif et sur la manière dont il conduit à un meilleur ordre de déplacement pour les recherches. En passant par un approfondissement itératif, la table de transposition peut stocker les meilleures informations d'ordre de mouvement pour toutes les positions intermédiaires, ce qui rend l'élagage plus efficace à une profondeur plus profonde. De plus, en procédant à un approfondissement itératif, il fournit également un bon mécanisme de contrôle du temps. La vidéo aborde également la base de données de jeu et explique pourquoi la création d'une base de données de fin de partie est bénéfique, tout en expliquant comment éviter le cycle dans une base de données de fin de partie en stockant la distance à s'accoupler plutôt qu'une simple valeur booléenne.

  • 00:45:00 Dans cette section, l'orateur discute de différentes heuristiques utilisées dans le processus d'évaluation des algorithmes de recherche, en particulier pour éviter le cycle et la recherche au repos. Le conférencier mentionne l'importance de maintenir la distance pour gagner et d'éviter le cyclisme en recherchant une distance de gain inférieure d'une unité à la distance actuelle. Une autre heuristique utilisée est l'élagage par mouvement, où rester immobile n'est généralement pas aussi bon que faire un mouvement, et l'élagage sans mouvement, où le mouvement nul est appliqué pour simplifier la recherche lorsqu'une position est si bonne que même ne rien faire entraînerait une victoire . L'orateur discute également de Zoogs Wang aux échecs et de la façon dont les extensions de mouvement sont utilisées dans la recherche de mensonges aux échecs lorsqu'il n'y a qu'un seul mouvement forcé.

  • 00:50:00 Dans cette section, l'orateur parle de l'utilisation d'une table de transposition dans un algorithme de recherche, qui est en fait un dag (graphe acyclique dirigé) puisque la même position peut être atteinte par des mouvements transposés. La table de transposition stocke des scores de qualité déterminés par la profondeur recherchée pour établir la valeur d'un mouvement pour éviter de rechercher à nouveau la même position. Il est crucial de ne pas utiliser de mouvements de qualité trop faible car cela ne permettra pas une recherche complète et la valeur stockée peut être moins précise. De plus, un code spécial est utilisé pour stocker les positions de mat calculées en soustrayant un très grand nombre de la profondeur pour arriver au mat. Le hachage Zobrist, une technique d'optimisation utilisée dans les algorithmes de recherche, est également discuté impliquant une valeur de hachage unique pour chaque position sur le tableau avec les mêmes pièces.

  • 00:55:00 Dans cette section, le professeur Leiserson explique le concept de hachage Zobrist, qui est utilisé pour mettre à jour efficacement une fonction de hachage représentant la position de différentes pièces sur un échiquier. La fonction de hachage consiste à générer une table de nombres aléatoires correspondant à différentes combinaisons de type de pièce, de ligne, de colonne et d'orientation. La fonction de hachage utilise des opérations XOR pour calculer le hachage en prenant le XOR des valeurs de toutes les pièces et leurs orientations. Le hachage Zobrist exploite la propriété XOR pour supprimer des pièces de la fonction de hachage en XORant la valeur de la pièce supprimée pour obtenir le hachage des pièces restantes. Cela permet une mise à jour bon marché et efficace de la fonction de hachage avec seulement deux opérations XOR pour tout mouvement effectué.

  • 01:00:00 Dans cette section, l'orateur discute de diverses techniques d'optimisation pour les moteurs d'échecs. Il parle de la table de transposition, qui stocke les enregistrements de la clé Zobrist, du score, de la qualité et du type lié d'un mouvement, et vieillit les mouvements plus anciens. De plus, il mentionne le concept de réduction des mouvements tardifs, où les mouvements moins prometteurs sont recherchés moins profondément pour gagner du temps. L'orateur parle également de la représentation de l'échiquier et de la façon dont l'utilisation de bitboards peut accélérer la génération de mouvements et d'autres concepts d'échecs en utilisant des astuces pour effectuer efficacement des opérations telles que le décalage et le comptage des bits.

  • 01:05:00 Dans cette section, l'orateur aborde le thème du "parallélisme spéculatif et Leiserchess". Il explique que l'une des principales optimisations pouvant être réalisées dans le traitement d'un laser consiste à évaluer si un mouvement affecte ou non la trajectoire du laser. De plus, l'orateur suggère de rechercher la "couverture laser" car cela coûte très cher. Il conseille également aux programmeurs de laisser l'ancienne représentation dans le code et de mettre des assertions qui disent que les choses sont équivalentes et d'utiliser des programmes comme Perfectiy pour dire s'ils ont apporté des modifications. Enfin, il explique comment le programme est censé fonctionner pour rapprocher le laser du roi et l'importance de la position dans le jeu.

  • 01:10:00 Dans cette section, l'orateur discute d'une nouvelle heuristique qu'ils ont développée pour mesurer la distance entre un laser et le roi d'un adversaire dans Leiserchess. Ils évaluent chaque mouvement en calculant la distance du laser par rapport au roi, en comptant un pour chaque position qu'il éloigne et une valeur supplémentaire s'il rebondit sur un adversaire. Ils prennent le nombre minimum qu'ils peuvent obtenir sur chaque case et utilisent un multiplicateur pour pondérer à quel point il est bon d'être près du roi. Ils additionnent le tout et le multiplient par un multiplicateur constant magique pour représenter la valeur comme une fraction de pion. Le nombre résultant varie jusqu'à environ quatre en moyenne.

  • 01:15:00 Dans cette section, l'orateur discute de diverses manières d'améliorer l'efficacité du moteur d'échecs. Une suggestion est de trouver une meilleure façon d'évaluer la proximité de l'adversaire avec le laser du joueur, car la méthode actuelle est coûteuse en calcul. Un autre domaine d'optimisation est le tri des mouvements, qui peut également être coûteux, surtout s'il y a de nombreux mouvements à passer au crible. L'orateur suggère de trouver un moyen d'optimiser le tri afin que seuls les mouvements pertinents soient triés et que les tris inutiles soient évités. L'orateur mentionne également que changer les représentations du conseil peut être un processus douloureux, mais il existe des alternatives à la représentation du conseil d'administration qui peuvent être plus efficaces.

  • 01:20:00 Dans cette section, la vidéo traite de l'importance de refactoriser le code et de le tester correctement pour s'assurer que les modifications sont effectuées correctement sans casser le code. L'orateur suggère de refactoriser les accès au tableau à un appel de fonction avant de le modifier pour faciliter le changement de la représentation du tableau sans refactorisation approfondie. Des tests appropriés sont également essentiels pour s'assurer que les modifications sont correctes et ne cassent pas le code, et il est important de rendre le code déterministe pour éviter l'imprévisibilité. Le conférencier mentionne également une conférence à venir de John Bentley comme une occasion précieuse de rencontrer une célébrité et d'en apprendre davantage sur le domaine.
 

Cours 21. Réglage d'un algorithme TSP



Cours 21. Réglage d'un algorithme TSP

Cette vidéo YouTube se concentre sur le problème du voyageur de commerce (TSP), un problème NP-difficile qui existe depuis de nombreuses années. L'orateur passe par divers algorithmes et approches pour optimiser l'espace de recherche et élaguer la recherche pour accélérer l'algorithme TSP, comme la mise en œuvre d'un meilleur algorithme d'arbre couvrant minimum, l'activation de l'optimisation du compilateur et la modification du calcul de la distance pour utiliser un algorithme de recherche de table. La nécessité de limiter l'espace de recherche et de penser de manière créative pour optimiser les programmes en termes de vitesse et de performances est soulignée tout au long de la vidéo, ce qui fournit des informations précieuses sur la résolution des TSP et d'autres problèmes connexes.

Dans cette vidéo, l'orateur aborde diverses techniques d'optimisation de l'algorithme TSP, telles que la mise en cache, l'évaluation paresseuse et le stockage des données dans une table de hachage, en soulignant l'importance des données empiriques par rapport à l'intuition. Il partage également son expérience avec la résolution du problème TSP et l'importance de l'ingénierie de la performance dans sa profession. L'orateur donne un aperçu du processus d'optimisation du code, y compris le développement incrémental et la génération récursive, et encourage le public à utiliser ces techniques car elles sont faciles à mettre en œuvre. Enfin, le conférencier exprime sa gratitude pour la poursuite de l'ingénierie de la performance et le développement d'algorithmes qui améliorent divers services Google, ainsi que pour les amitiés qu'il a nouées tout au long de sa carrière.

  • 00:00:00 Dans cette section, John Bentley présente le problème du voyageur de commerce (TSP), qui est un problème NP-difficile qui existe depuis de nombreuses années. Il décrit son expérience avec le problème et comment il en est devenu accro il y a plus de 40 ans. Il discute ensuite d'une solution récursive pour énumérer tous les sous-ensembles d'un ensemble et explique le processus de comptage des nombres entiers dans un ensemble. Il note que cette méthode ne généralise pas bien mais fournit des principes qui aideront à développer des algorithmes de plus en plus rapides pour TSP.

  • 00:05:00 Dans cette section, l'orateur explique comment générer tous les ensembles de taille M de manière récursive. L'approche est de commencer avec un ensemble de taille n-1 et d'énumérer tous les ensembles de taille M avec l'ajout d'un zéro à la fin. Le nombre d'ensembles avec un zéro à la fin est calculé en prenant 2 à la puissance M moins un. L'esquisse récursive est illustrée par un exemple où chaque sous-ensemble est compté à rebours à partir de zéro, additionné d'un un à la fin. Le code de cet algorithme est simple et peut être implémenté dans la plupart des langages de programmation. L'orateur encourage le public à poser des questions et à s'exprimer, affirmant que leur créativité a peut-être été dépassée par le système éducatif. Le reste de la vidéo couvre le problème du voyageur de commerce et explique comment développer un algorithme efficace pour celui-ci.

  • 00:10:00 Dans cette section, l'orateur parle du problème du voyageur de commerce (TSP) et de son importance en tant que problème prototypique en informatique qui a été l'un des premiers problèmes à être prouvé comme NP-difficile. L'orateur partage une anecdote personnelle sur la façon dont il s'est intéressé au problème lorsque son collègue a discuté de leurs difficultés à résoudre un TSP en 16 points dans leur thèse de doctorat. L'orateur explique ensuite comment il a écrit un programme pour résoudre le même problème 20 ans plus tard, qui est devenu un sujet populaire dans une classe d'algorithmes à l'Université de Lehigh, conduisant à d'autres explorations de la façon dont l'ingénierie de la performance a changé en 40 ans.

  • 00:15:00 Dans cette section, l'orateur explique un algorithme récursif dans un programme C simple pour générer toutes les permutations factorielles de n villes pour trouver le meilleur circuit. Le facteur de branchement de l'arbre sera de 9 à chaque nœud, résultant en un grand arbre pour n = 10 avec 10 combinaisons factorielles possibles. Le programme vérifie la somme des distances entre les villes pour chaque permutation et enregistre la somme minimale trouvée jusqu'à présent. Le programme fonctionne correctement, mais sa vitesse pour n=10 n'est pas claire.

  • 00:20:00 Dans cette section, l'orateur discute du temps nécessaire pour exécuter des permutations et suggère diverses façons d'accélérer le programme. Il explique à quelle vitesse il faut exécuter quatre permutations sur un ordinateur portable rapide et comment le temps augmente considérablement à mesure que les permutations augmentent. Il envisage également des moyens d'accélérer le programme, comme choisir un démarrage et ignorer tous les autres ou utiliser la parallélisation. De plus, il mentionne la possibilité d'optimiser le programme avec des compilateurs, notamment avec GCC et -o3. Enfin, il discute des avantages d'avoir des machines plus rapides et un temps CPU plus rapide.

  • 00:25:00 Dans cette section, l'orateur explique à quel point l'algorithme TSP peut devenir plus rapide grâce à diverses optimisations. Par exemple, le simple fait d'activer les optimisations du compilateur peut entraîner une augmentation des performances jusqu'à un facteur de 25. De plus, à mesure que le matériel s'est amélioré au fil des ans, l'optimisation du noyau peut produire une vitesse d'horloge plus rapide, des chemins de données plus larges et des pipelines plus profonds, ce qui se traduit par une accélération d'un facteur 150. De plus, la modification du calcul de la distance pour utiliser un algorithme de recherche de table peut conduire à un facteur d'accélération de 2,5 à 3. Globalement, même si les vieilles intuitions sur les performances ne sont plus vraies, faites attention la modélisation peut déterminer les effets de diverses optimisations sur l'algorithme TSP.

  • 00:30:00 Dans cette section, l'orateur explique différentes manières d'optimiser un algorithme inductif pour calculer plusieurs fois la même somme afin d'éviter de calculer les mêmes pièces de manière répétitive. L'orateur montre également les temps d'exécution des quatre algorithmes et explique comment aller plus vite, par exemple en utilisant une meilleure machine et en utilisant chaque facteur de en pour créer la taille du problème par un dans le même laps de temps. Ils expliquent également comment résoudre un problème de voyageur de commerce et montrent que la tournée optimale est différente selon les aspects du problème. L'orateur conclut en encourageant la résolution du problème malgré sa longue durée d'exécution.

  • 00:35:00 Dans cette section, l'orateur discute de la magnitude de la factorielle 52 et explique comment elle est plus rapide que n'importe quelle fonction exponentielle. Il explique que c'est approximativement 2 à la puissance 225 ou 10 à la 67e, ce qui est un nombre énorme. Pour le dire au quotidien, il donne l'exemple du décompte de 52 nanosecondes factorielles et d'un pas en avant tous les millions d'années, pour finalement faire le tour de l'équateur et prélever une goutte d'eau de l'océan Pacifique. Il insiste ensuite sur la nécessité de limiter l'espace de recherche et d'élaguer la recherche pour résoudre efficacement ces problèmes.

  • 00:40:00 Dans cette section, l'orateur présente un problème que sa fille lui a donné à résoudre. Le problème est de trouver toutes les permutations des 9 entiers de 1 à 9 telles que chaque sous-chaîne initiale de longueur m soit divisible par M de sorte que le tout soit divisible par 9. L'orateur vous suggère de réfléchir avant d'écrire un programme pour résoudre le problème . Il discute ensuite d'un programme dans le langage de programmation AWK qui utilise des chaînes et des procédures récursives pour générer toutes les permutations possibles. L'exécution de ce programme prendrait environ 49 heures ! complexité temporelle.

  • 00:45:00 Dans cette section, l'orateur explique comment optimiser l'espace de recherche lors de la recherche d'une chaîne spécifique à l'aide d'un programme. Il le démontre à travers un exemple de recherche d'une chaîne avec des propriétés spécifiques, comme être divisible par certains nombres et contenir certains nombres dans des positions spécifiques. En définissant les propriétés qui doivent être présentes dans la chaîne gagnante, l'espace de recherche peut être considérablement réduit d'un tiers de million à un demi-millier de choix possibles. Cela souligne l'importance d'élaguer la recherche afin d'accélérer le processus. L'orateur insiste sur la nécessité de réfléchir à la façon d'optimiser les programmes pour la vitesse et la performance.

  • 00:50:00 Dans cette section, l'orateur discute des moyens d'élaguer la recherche afin d'accélérer l'algorithme TSP. Une façon d'élaguer la recherche est de ne pas continuer à faire ce qui ne fonctionne pas, c'est-à-dire que si la somme s'avère supérieure à la somme minimale en y ajoutant plus, alors arrêtez la recherche. Cette méthode peut rendre l'algorithme plus rapide sur la même machine en prenant moins de temps. Cependant, l'orateur introduit également d'autres idées pour élaguer la recherche et obtenir une borne inférieure, comme le calcul d'un chemin TSP ou d'un arbre couvrant minimum, qui sont plus puissants mais aussi plus coûteux.

  • 00:55:00 Dans cette section, l'orateur explique comment améliorer la limite inférieure du TSP en implémentant un meilleur algorithme d'arbre couvrant minimal, car c'est là que se passe la majeure partie du temps de calcul. Il utilise le parallélisme avec une représentation de masque binaire du sous-ensemble de villes pour calculer le MST rapidement et efficacement. Même si le calcul du MST prend n temps au carré, cette méthode est un puissant mécanisme d'élagage conduisant à une vitesse de programme plus rapide. Après plusieurs essais et défis surmontés, le programme passe de 17 secondes à 0 seconde, ce qui permet de traiter facilement des ensembles de données plus volumineux.

  • 01:00:00 Dans cette section, l'orateur décrit son expérience pour optimiser l'algorithme TSP en mettant en œuvre une évaluation paresseuse, en stockant les données dans une table de hachage et en utilisant une meilleure tournée de démarrage avec une recherche plus intelligente. Il discute des avantages de la mise en cache et de la manière d'optimiser les performances de l'algorithme en expérimentant et en testant différentes approches. L'orateur souligne que l'ingénierie de la performance doit s'appuyer sur des données empiriques et que l'intuition est souvent erronée. Il mentionne également l'ascension du mont Monadnock et la différence entre les algorithmes prévisibles et imprévisibles.

  • 01:05:00 Dans cette section de la vidéo, l'orateur explique comment rendre la recherche de l'algorithme TSP plus intelligente en la guidant plus rapidement vers la ville de départ initiale, plutôt qu'en utilisant simplement une visite aléatoire. En utilisant un simple tri par insertion et en visitant d'abord les 30 villes les plus proches, l'espace de recherche peut être élagué, ce qui fait une grande différence. L'orateur partage qu'en 1997, ils étaient heureux d'en sortir 230, mais dans 20 ans, en utilisant uniquement la loi de Moore, ils pourraient obtenir un facteur de 1 000. Cependant, en combinant la loi de Moore et la technologie du compilateur avec tous les algorithmes, ils ont pu aller jusqu'à 52. L'orateur souligne que tout ce qu'ils ont partagé pourrait être réalisé avec 160 lignes de code, et toutes ces choses sont bien dans le cadre de pratique de quelqu'un qui a terminé ce cours.

  • 01:10:00 Dans cette section, l'orateur aborde plusieurs techniques d'optimisation du code, telles que la mise en cache, le précalcul et le stockage des résultats pour éviter tout travail inutile. Il souligne également l'importance du développement logiciel incrémental et la puissance de la génération récursive. L'orateur mentionne que certaines des techniques dont il parle sont couvertes dans un vieux livre qu'il a écrit sur le réglage du code, mais certaines des idées s'appliquent encore aujourd'hui. Il mentionne également qu'il a utilisé de nombreux outils dans les coulisses, tels que des profileurs et des modèles de coûts, pour effectuer des expériences et estimer les coûts. Enfin, il encourage le public à explorer et à utiliser ces techniques, car elles sont faciles à mettre en œuvre dans la pratique.

  • 01:15:00 Dans cette section, l'orateur aborde divers sujets, allant de l'élagage alpha-bêta au problème des collisions de hachage. L'orateur partage également son expérience de résolution du problème du voyageur de commerce avec son collègue au début des années 1990. Ils ont réussi à résoudre le problème des 48 capitales d'État et en étaient ravis. Le conférencier souligne également l'importance de l'ingénierie de la performance dans sa profession et mentionne son implication dans divers systèmes informatiques, y compris le gerrymandering automatisé et le codage des appels téléphoniques. Dans l'ensemble, la section donne un aperçu de la vaste expérience de l'orateur en programmation informatique et de ses perspectives sur diverses techniques et problèmes.

  • 01:20:00 Dans cette section, l'orateur exprime sa gratitude pour la poursuite de l'ingénierie de la performance comme mode de vie. Il mentionne que cela lui a permis de développer des algorithmes qui améliorent divers services Google, ce qui a été extrêmement satisfaisant et épanouissant pour lui. L'orateur exprime également sa gratitude pour les amitiés qu'il a nouées tout au long de sa carrière et espère que l'ingénierie de la performance pourra être aussi bonne pour les autres qu'elle l'a été pour lui.
 

Cours 22. Optimisation des graphes



Cours 22. Optimisation des graphes

La vidéo traite du concept de graphe, des différentes manières de le représenter et des techniques d'optimisation pour améliorer l'efficacité des algorithmes de graphe. Le conférencier explore les applications des graphes dans la modélisation des relations et la recherche du chemin le plus court ou le moyen le moins cher pour atteindre une destination, ainsi que des moyens optimaux de stocker des graphes en mémoire pour ajouter, supprimer ou balayer des arêtes. La vidéo couvre également l'optimisation des performances du cache dans les recherches de graphes à l'aide de vecteurs de bits, ainsi que la mise en œuvre de l'algorithme de recherche parallèle en largeur d'abord avec des sommes de préfixes pour filtrer les valeurs négatives. Enfin, l'orateur parle de leurs expériences sur un graphe aléatoire à dix millions de sommets et cent millions d'arêtes, soulignant l'importance du déterminisme dans le code pour assurer la fiabilité et la cohérence.

La vidéo aborde également diverses techniques d'optimisation de graphes, notamment la mise en œuvre de l'opérateur min droit, le code BFS parallèle déterministe, la technique d'optimisation de direction et la compression de graphes. La technique d'optimisation de direction implique une approche ascendante pour explorer les arêtes entrantes lorsque la frontière est grande et a été appliquée à d'autres algorithmes de graphe, tandis que la compression de graphe vise à réduire l'utilisation de la mémoire en codant les différences entre les arêtes consécutives et en réduisant le nombre de bits utilisés. pour stocker ces valeurs. De plus, la vidéo souligne l'importance de tester les optimisations sur différents types de graphiques pour déterminer où ils fonctionnent bien et où ils ne fonctionnent pas.

  • 00:00:00 Dans cette section, l'instructeur présente le concept de graphe et explique diverses manières de le représenter et de l'utiliser pour modéliser les relations entre les objets. Les exemples incluent les réseaux sociaux, les réseaux de protéines et le Web mondial. Les sommets et les arêtes peuvent être pondérés et dirigés, et peuvent avoir des métadonnées et des types. L'instructeur présente également des applications des graphiques pour trouver le chemin le plus court d'une ville à une autre ou le moyen le moins cher pour atteindre une destination. Enfin, le cours couvre les techniques d'optimisation de graphes telles que la compression et la réorganisation pour améliorer l'efficacité des algorithmes de graphes.

  • 00:05:00 Dans cette section, l'orateur met en évidence diverses applications de l'optimisation des graphes, notamment les requêtes sur les réseaux sociaux telles que la recherche d'amis communs ou de produits d'intérêt, le regroupement pour la détection de communautés ou la détection de sites Web frauduleux, la connectomique pour étudier la structure du cerveau, et la segmentation d'images en vision par ordinateur. L'orateur explique également deux façons de représenter un graphe en mémoire : la matrice d'adjacence, qui nécessite un espace d'ordre N au carré, et la représentation par liste d'arêtes, qui nécessite un espace d'ordre M.

  • 00:10:00 Dans cette section de la vidéo, les différentes manières de représenter un graphique ont été discutées, y compris le format de liste de contiguïté et le format de ligne clairsemée compressée. Le format de liste de contiguïté implique un tableau de pointeurs, où chaque pointeur pointe vers une liste chaînée stockant les arêtes de ce sommet. Cela a un besoin d'espace de O(n + m), mais peut avoir des problèmes de performances en raison de l'accès aléatoire à la mémoire. D'autre part, le format de ligne clairsemé compressé a une utilisation de l'espace de O(n + m) et permet un calcul efficace du degré d'un sommet. De plus, les valeurs ou les poids sur les bords peuvent être stockés dans un tableau supplémentaire.

  • 00:15:00 Dans cette section, la vidéo traite des compromis dans différentes représentations de graphes, notamment le coût de stockage, la numérisation du graphe, l'ajout d'une arête, la suppression d'une arête et la recherche de tous les voisins d'un sommet particulier. La matrice d'adjacence a un coût de stockage de O(n^2), tandis que l'ajout et la suppression d'arêtes est de O(1). Pour la liste des arêtes, le coût est O(m) pour scanner le graphe et O(1) pour ajouter une arête. La suppression d'une arête est O(m). Le degré de V est nécessaire pour ajouter ou supprimer une arête dans la liste JCU, avec un coût de stockage de O(m+n). Dans le pire des cas, l'ajout d'une arête dans le format de ligne clairsemé compressé peut coûter jusqu'à O(m+n). Trouver tous les voisins d'un sommet particulier est O(n) pour la matrice de contiguïté, O(m) pour la liste des arêtes et O(degré de V) pour la liste de contiguïté.

  • 00:20:00 Dans cette section, l'orateur passe en revue différentes manières de représenter les graphiques, y compris la matrice d'adjacence, la liste des arêtes, la liste JCL et le format CSR (compressé sparse row). Il explique que la RSE est la meilleure pour traiter les graphes clairsemés dans les algorithmes statiques où il n'est pas nécessaire de mettre à jour le graphe. En effet, tous les voisins d'un sommet sont stockés de manière contiguë dans la mémoire, ce qui facilite le balayage. Il note également que les graphes du monde réel ont tendance à être clairsemés et ont une distribution de degré de loi de puissance, ce qui signifie que la plupart des sommets ont un degré faible et quelques-uns ont un degré très élevé.

  • 00:25:00 Dans cette section, l'instructeur traite de l'optimisation des graphes et de la mise en œuvre de l'algorithme de recherche en largeur d'abord. Avec une distribution asymétrique des degrés dans les graphiques, l'exécution d'un algorithme parallélisé sur les sommets peut entraîner des problèmes de déséquilibre de charge en raison du nombre variable d'arêtes dont ils disposent. L'algorithme de recherche en largeur d'abord est utilisé pour visiter les sommets dans l'ordre de leur distance par rapport au sommet source, et la sortie peut inclure le rapport des sommets visités dans l'ordre dans lequel ils ont été visités, la distance entre chaque sommet et le sommet source et la génération d'un arbre de recherche en largeur d'abord où chaque sommet de l'arbre a un parent dans le niveau précédent de recherche en largeur d'abord. L'algorithme BFS série initialise les distances à l'infini, crée une structure de données de file d'attente, définit la distance de l'itinéraire sur zéro et le place dans la file d'attente. L'algorithme continue d'itérer jusqu'à ce qu'il ne reste plus de sommets dans la file d'attente. Le travail nécessaire pour cet algorithme est discuté en termes de N et M.

  • 00:30:00 Dans cette section, l'orateur discute de la mise en œuvre d'un algorithme BFS série utilisant le format de ligne clairsemé compressé. L'algorithme consiste à initialiser deux tableaux, parent et Q, à placer un sommet source dans la file d'attente et à parcourir les voisins du sommet actuel. Cependant, la partie la plus coûteuse du code est l'accès au parent du voisin, qui constitue un accès aléatoire en mémoire. Cela se traduit par un manque de cache presque à chaque fois et peut entraîner un ralentissement des performances. Le tableau d'adresses est principalement accessible de manière séquentielle, ne nécessitant qu'un seul accès aléatoire au tableau d'arêtes par sommet, ce qui le rend plus convivial pour le cache. Le travail global de l'algorithme est déterminé comme étant d'ordre M + N.

  • 00:35:00 Dans cette section, le conférencier aborde l'analyse et l'optimisation des performances du cache dans l'optimisation des graphes. L'analyse dissèque comment les échecs de cache se produisent lors de l'initialisation séquentielle d'un tableau, en sortant les sommets du début d'une file d'attente, en calculant les degrés et en accédant aux tableaux de décalage et de bord. L'optimisation implique l'utilisation d'un vecteur de bits pour stocker si un sommet a déjà été exploré, qui est une variable d'un bit pour réduire les échecs de cache lors de l'accès à un tableau avec des informations parent. Cette optimisation réduit les échecs de cache lors de l'accès aux tableaux d'arêtes et de sommets de em à n.

  • 00:40:00 Dans cette section, le conférencier explique comment optimiser les recherches de graphes à l'aide de vecteurs de bits pour réduire le nombre d'échecs de cache. L'optimisation du vecteur de bits consiste à initialiser un vecteur de bits dit "visité" de taille environ n sur 32 et à mettre ses bits à 0 sauf pour le sommet source. Le code utilise la manipulation de vecteurs de bits pour vérifier les voisins visités et définir les bits lors de l'exploration d'un voisin. L'orateur présente également une implémentation parallèle d'un algorithme de recherche en largeur d'abord qui opère sur les frontières et génère un pointeur parent pour chaque sommet exploré. L'implémentation parallèle doit être consciente des courses potentielles lorsque plusieurs sommets sur la frontière tentent de visiter le même voisin, et l'équilibrage de charge est nécessaire pour garantir que chaque processeur a à peu près la même quantité de travail.

  • 00:45:00 Dans cette section, l'instructeur montre comment effectuer une recherche parallèle en largeur sur un graphique, en commençant par initialiser toutes les entrées parentes à moins une. L'instructeur définit ensuite le sommet source comme étant le 0e index de la frontière et, alors que la taille de la frontière est supérieure à zéro, itère sur tous les sommets de la frontière en parallèle à l'aide d'une cellule pour la boucle. Ils ont défini la "i-ième" entrée du tableau des degrés comme étant le degré du sommet sur la frontière, effectuant une somme de préfixes sur ce tableau. Ensuite, l'instructeur parcourt à nouveau la frontière et vérifie les voisins de chaque sommet pour voir s'il a été exploré, effectuant une comparaison et un échange pour échanger le sommet avec la valeur d'origine de moins un dans le parent du voisin s'il n'a pas encore été exploré .

  • 00:50:00 Dans cette section, la vidéo traite d'un algorithme Breadth-First Search (BFS) parallèle, qui fonctionne sur une somme de préfixes pour filtrer les valeurs négatives dans un tableau tout en conservant les valeurs non négatives, qui sont utilisées pour générer décalages uniques pour un tableau de sortie via la somme des préfixes. La vidéo analyse également le travail et la durée de l'algorithme, indiquant que le nombre d'itérations est limité par le diamètre du graphique, le travail par sommet est n, et que le travail global de l'algorithme est thêta de n plus M, correspondant le travail de l'algorithme sériel.

  • 00:55:00 Dans cette section, l'orateur parle de ses expériences sur un graphe aléatoire avec dix millions de sommets et cent millions d'arêtes et comment ils ont testé leur algorithme sur une machine à quarante cœurs avec un hyper-threading bidirectionnel. Ils expliquent également comment fonctionne l'hyper-threading et l'importance de déterminer s'il y a du non-déterminisme dans le code. Ils démontrent comment le non-déterminisme peut être corrigé en mettant en œuvre des processus déterministes tels que l'utilisation de l'opérateur d'écriture min et des valeurs négatives pour les sommets précédemment explorés dans le code BFS. En procédant ainsi, l'arbre BFS final généré par le code sera toujours le même, garantissant la fiabilité et la cohérence.

  • 01:00:00 Dans cette section, le présentateur discute de la mise en œuvre de l'opérateur min droit et des avantages de l'utilisation d'un code BFS parallèle déterministe. Le bon opérateur min peut être implémenté à l'aide d'une boucle avec une comparaison et un échange, et bien qu'il ne soit pas encore complètement déterministe, il produit un arbre BFS cohérent. Le code BFS parallèle déterministe est également plus facile à déboguer et à raisonner sur ses performances. Le présentateur présente également la technique d'optimisation de la direction, qui implique une méthode ascendante pour explorer les arêtes entrantes lorsque la frontière est grande et que de nombreux sommets ont déjà été explorés, ce qui permet d'économiser sur les traversées d'arêtes.

  • 01:05:00 Dans cette section, la vidéo traite des performances des approches descendantes et ascendantes dans BFS, telles qu'étudiées par Scott Beamer en 2012. L'approche descendante est plus efficace pour les petites frontières, tandis que l'approche descendante -up approche est plus efficace pour les grandes frontières. Le choix entre ces deux approches est basé sur la taille de la frontière, avec un seuil de n supérieur à 20 qui fonctionne bien en pratique. La vidéo aborde également différentes manières de représenter la frontière et compare les performances de trois approches de traversée différentes, y compris l'approche d'optimisation de la direction, qui est toujours plus rapide que les approches descendante et ascendante. L'idée d'optimisation de direction est également plus générale que BFS et a été appliquée à d'autres algorithmes de graphe.

  • 01:10:00 Dans cette section, le conférencier explique deux techniques d'optimisation de graphe : l'optimisation de direction et la compression de graphe. L'optimisation de la direction implique de choisir entre une implémentation clairsemée ou dense en fonction de la taille de la frontière. La compression de graphe vise à réduire l'utilisation de la mémoire en codant les différences entre les arêtes consécutives et en réduisant le nombre de bits utilisés pour stocker ces valeurs via des codes de longueur variable ou des codes à K bits. Un problème avec le décodage des codes de K bits est qu'il implique des branches imprévisibles, donc une optimisation implique de se débarrasser du bit de continuation en regroupant des entiers qui ont besoin du même nombre d'octets pour encoder et en utilisant un octet d'en-tête pour stocker la taille du groupe et le nombre d'octets nécessaires pour décoder chaque entier. Cela augmente légèrement l'utilisation de l'espace mais réduit le coût du décodage.

  • 01:15:00 Dans cette section, nous apprenons que pour économiser de l'espace lors de l'exécution d'algorithmes sur des graphes du monde réel volumineux mais relativement clairsemés, nous devons décoder les arêtes à la volée lorsque nous exécutons notre algorithme et les encoder dans morceaux pour éviter le déséquilibre de charge. Les expériences montrent que ces schémas de compression économisent de l'espace et bien qu'ils ne soient que légèrement plus lents que la version non compressée, ils deviennent plus rapides que la version non compressée lorsqu'ils s'exécutent en parallèle en raison de l'utilisation de la mémoire. Enfin, les optimisations pour les graphiques peuvent bien fonctionner pour certains graphiques mais peuvent ne pas fonctionner pour d'autres, et par conséquent, il est important de tester les optimisations sur différents types de graphiques pour voir où elles fonctionnent bien et où elles ne fonctionnent pas.
 

Cours 23. Haute performance dans les langages dynamiques



Cours 23. Haute performance dans les langages dynamiques

Les défis liés à l'écriture de code critique pour les performances dans des langages typés dynamiquement de haut niveau sont abordés dans cette vidéo, en mettant l'accent sur le langage de programmation Julia. Julia vise à fournir des fonctionnalités interactives de haut niveau tout en offrant le même niveau de performances que les langages de niveau inférieur tels que C et Fortran. La capacité de Julia à écrire du code générique qui fonctionne pour plusieurs types, la métaprogrammation intégrée et les chemins de code optimisés le rendent plus rapide que Python dans des situations telles que la génération de grandes matrices de vandermonde et un code optimisé pour des polynômes spécifiques dans des fonctions spéciales. De plus, les chemins de code optimisés de Julia allouent les boîtes beaucoup plus rapidement que Python, ce qui en fait un meilleur choix pour traiter les structures de données dynamiques comme les tableaux. Enfin, la vidéo traite des multiples capacités de répartition et d'inférence de type de Julia, permettant à différentes versions d'une fonction pour différents arguments et types d'être déduits de manière récursive.

Dans cette vidéo explique également comment fonctionne le polymorphisme paramétrique dans Julia et comment il permet de créer des familles infinies de types. En définissant un type paramétré, comme un type de point avec des paramètres pour X et Y, et en définissant ces paramètres sur un sous-type de réel, on peut créer un ensemble complet de types qui peuvent être « instanciés » avec un sous-type particulier. De plus, l'orateur discute des capacités et des bibliothèques de Julia pour implémenter le threading, la récupération de place et le parallélisme de mémoire distribuée, ainsi que sa large gamme de support Unicode pour les identifiants. De plus, l'importance d'avoir des variables avec des noms propres et descriptifs est soulignée, et l'orateur mentionne un projet qui explore la fusion de la technologie Julia avec la technologie Silk qui pourrait conduire à de nouveaux développements à l'avenir.

  • 00:00:00 Dans cette section, l'orateur parle des défis liés à l'écriture de code critique pour les performances dans des langages typés dynamiquement de haut niveau tels que Python et Matlab. Bien que ces langages soient populaires pour l'informatique technique et l'exploration interactive, ils ont tendance à se heurter à un mur de performances lorsqu'il s'agit d'écrire du code critique pour les performances. En conséquence, les gens utilisent traditionnellement des langages de niveau inférieur comme Fortran ou C comme solution pour écrire du code critique pour les performances, mais cela crée un saut significatif dans la complexité du codage et une perte de généralité. L'orateur présente ensuite le langage de programmation, Julia, qui vise à être aussi haut niveau et interactif que Python tout en offrant le même niveau de performances que C. Julia permet aux utilisateurs d'écrire du code générique qui fonctionne pour plusieurs types, et pendant sa sortie en 2013, sa récente version 1.0 est désormais stable et délivre les performances promises.

  • 00:05:00 Dans cette section, l'orateur discute des différences de performances entre Julia et Python lors de la génération d'une grande matrice vandermonde. Alors que Python s'appuie sur des centaines de lignes de code C pour générer la matrice, ce qui prend beaucoup de temps en raison de la complexité du code, Julia peut générer la même matrice avec seulement deux boucles imbriquées et aucune déclaration de type. Julia dispose également de techniques intégrées pour la métaprogrammation ou la génération de code, permettant une évaluation en ligne très optimisée pour des polynômes spécifiques dans des fonctions spéciales. Dans certains cas, Julia peut être deux à trois fois plus rapide que les bibliothèques C et Fortran optimisées pour des fonctions spéciales.

  • 00:10:00 Dans cette section, l'orateur explique comment les langages de haut niveau comme Julia permettent des astuces de performance qui seraient difficiles à faire dans les langages de bas niveau. Il explique comment Julia peut être rapide en le comparant à Python et en soulignant la capacité de Julia à être complètement générique tout en permettant la compilation de code à des vitesses rapides. L'orateur montre également comment utiliser un cahier dans Julia pour calculer la somme d'une liste de nombres et compare l'implémentation dans Julia à Python et C. Il montre comment les outils d'analyse comparative peuvent être utilisés pour collecter des statistiques et renvoyer le temps minimum pour l'implémentation. courir.

  • 00:15:00 Dans cette section, l'orateur explique comment utiliser une macro dans Julia pour réécrire une expression qui établit une boucle et la chronomètre. En utilisant cette méthode, il faut environ 11 millisecondes pour traiter 10 à la puissance 7. Il passe ensuite à l'analyse comparative en Python, en utilisant un package appelé pycall qui permet aux fonctions Python d'être appelées depuis Julia. Il note que si la fonction sum de Python est écrite en C et fonctionne donc relativement bien, le fait que les listes Python peuvent être composées d'éléments de n'importe quel type signifie qu'elles doivent être structurées d'une manière qui la rend plus lente que C. à Julia, qui permet l'hétérogénéité sans compromettre les performances.

  • 00:20:00 Dans cette section, l'orateur discute des défis des langages dynamiques comme Python lorsqu'il s'agit d'atteindre des performances élevées dans des structures de données comme des tableaux. L'orateur note que la combinaison d'une valeur et d'une balise de type pour chaque élément d'un tableau rend difficile pour une implémentation optimisée de lire les informations de type et les données pour chaque élément du tableau sans réaffecter la boîte pour le tableau. Ils mettent en évidence l'utilisation de numpy, une bibliothèque conçue pour améliorer les performances des tableaux, comme moyen d'optimiser les opérations sur les tableaux en tapant et en répartissant des valeurs similaires ensemble.

  • 00:25:00 Dans cette section, l'intervenant explique comment créer un compilateur Python rapide pour le code Python. Cependant, il lui manque la possibilité de fournir un chemin rapide pour vérifier si tous les types sont identiques en Python, ce qui signifie qu'à chaque itération de boucle, il doit allouer une nouvelle boîte pour le résultat et rechercher dynamiquement la fonction plus, ce qui la rend Ralentissez. Le Python intégré s'est avéré beaucoup plus lent que le code C et NumPy. Le type de tableau dans Julia a le type qui lui est attaché, ce qui le fait ressembler davantage à un tableau NumPy en mémoire, et l'équivalent d'une liste Python appelée un tableau de any s'est avéré encore plus lent que Python pur. Julia a optimisé ses chemins de code pour allouer beaucoup de boîtes beaucoup plus rapidement que Python.

  • 00:30:00 Dans cette section, l'intervenant montre comment écrire du code optimisé dans Julia à l'aide de boucles droites qui fonctionnent sur n'importe quel type de conteneur et prennent en charge une fonction plus. La fonction est complètement générique et fonctionne sur tout ce qui peut être bouclé et a une fonction plus. L'orateur explique également que la vectorisation des boucles n'est pas la valeur par défaut car la majeure partie du code ne peut pas être auto-vectorisée, ce qui augmente le temps de compilation et la taille du code. De plus, le code est mis à l'épreuve avec des nombres complexes, un tableau de quaternions et un ensemble d'entiers uniques, et cela fonctionne pour chacun d'eux. Dans l'ensemble, Julia est rapide en raison de plusieurs facteurs.

  • 00:35:00 Dans cette section, l'orateur explique comment le langage de programmation Julia compile des versions spécialisées des fonctions en fonction du type d'argument transmis à la fonction. Par exemple, si la fonction f de x est égale à x plus un reçoit un entier 64 bits, Julia compile une version spécialisée de cette fonction pour ce type. Le processus de passage des types d'entrée aux types inférés de la sortie est appelé inférence de type. L'orateur note que Julia est un langage dynamique, donc l'inférence de type peut échouer, et si c'est le cas, il se rabat sur C.

  • 00:40:00 Dans cette section, l'orateur discute de l'inférence de type et donne des exemples de la façon dont cela peut fonctionner de manière récursive. Il montre comment le compilateur LLVM peut prendre une fonction simple et l'optimiser en quelques instructions machine en effectuant un pliage constant. Il montre ensuite comment les déclarations de type peuvent être utilisées pour éviter les erreurs et faire quelque chose appelé dispatch, qui permet différentes versions d'une fonction pour différents arguments. En définissant différentes méthodes basées sur la hiérarchie des types, il montre comment une fonction peut avoir plusieurs méthodes.

  • 00:45:00 Dans cette section de la vidéo, l'orateur explique la hiérarchie des types dans Julia, avec "number" comme type principal et "integer" et "Pole real" comme sous-types. Il parle également du concept de répartition multiple dans Julia, où une méthode est déterminée non seulement par le type du premier argument mais par tous les types d'arguments. Cette généralisation de la programmation orientée objet permet de surcharger facilement une opération qui opère sur des types mixtes et de choisir la méthode la plus spécifique dans la hiérarchie. L'exemple d'une fonction plus est utilisé pour illustrer ce point.

  • 00:50:00 Dans cette section, l'orateur explique comment ajouter différents types de valeurs comme un nombre réel simple précision ou un nombre complexe à une autre valeur. Cependant, l'ajout de différents types de valeurs - comme un nombre complexe simple précision à un membre de couple double précision - peut entraîner des problèmes de propriété des méthodes. L'orateur donne l'exemple de la fonction racine carrée et comment sa valeur de retour doit être de type stable pour déduire correctement le type de l'argument. L'inférence de type garantit que le type de la valeur de retour dépend du type de l'entrée et non de la valeur de l'entrée. L'orateur mentionne également les défis liés à l'inférence de type dans des langages dynamiques comme Python et MATLAB, ce qui entraîne une diminution des performances.

  • 00:55:00 Dans cette section, l'orateur explique comment différentes langues gèrent les nombres complexes et l'arithmétique entière, et comment l'arithmétique entière par défaut de Julia utilise 64 bits, ce qui la rend moins sujette au débordement que les langues avec des tailles de bits plus petites. L'orateur parle également des avantages de la définition de types personnalisés dans Julia, en se concentrant spécifiquement sur la définition d'un type de point personnalisé pour les vecteurs bidimensionnels, ce qui peut être plus rapide et plus efficace que l'utilisation d'un tableau pour deux valeurs. Le locuteur passe par plusieurs itérations pour optimiser ce type personnalisé, pour finalement arriver à une structure immuable avec une fonction plus définie.

  • 01:00:00 Dans cette section de la vidéo, l'intervenant discute des limites de l'utilisation d'un type générique pour un objet ponctuel et des problèmes de performances qui en résultent. Avec le type de point générique, les variables X et Y doivent être des pointeurs vers des cases, ce qui entraîne une recherche de pointeur importante et des vérifications d'exécution lentes. De plus, étant donné que le type est modifiable, il doit être stocké en tant que pointeur vers un objet en mémoire, ce qui entraîne d'autres problèmes de performances. Pour résoudre ces problèmes, l'orateur propose d'utiliser une structure non modifiable avec des types d'arguments spécifiés pour X et Y, ce qui améliorerait les performances en permettant au type d'être stocké directement en mémoire au lieu d'être un pointeur vers une boîte.

  • 01:05:00 Dans cette section, l'intervenant explique comment fonctionne le polymorphisme paramétrique dans Julia et comment il permet de créer des familles infinies de types. En définissant un type paramétré, comme un type de point avec des paramètres pour X et Y, et en définissant ces paramètres sur un sous-type de réel, on peut créer un ensemble complet de types qui peuvent être « instanciés » avec un sous-type particulier. Cela permet une flexibilité dans les types de données sans sacrifier les performances ou la généralité. Le compilateur est suffisamment intelligent pour stocker ces types dans une mémoire consécutive et optimiser les fonctions de sommation avec des boucles serrées. Ces types paramétrés s'ajoutent à la syntaxe de haut niveau de Julia et suppriment la nécessité d'écrire du code C pour l'optimisation des performances.

  • 01:10:00 Dans cette section, le conférencier explique comment Julia peut gérer la frappe mixte, ce qui permet une plus grande flexibilité dans la programmation. Tant que le signe plus est utilisé pour additionner des nombres, deux types de nombres peuvent être ajoutés, le type résultant étant déterminé par le type de retour. Un exemple est donné avec des entiers 64 bits et des float64 ajoutés. De plus, le compilateur connaît tous les types d'un tableau, ce qui permet un calcul rapide de fonctions telles que sum. Alors que les compilateurs de vectorisation peuvent être limités dans leur capacité à optimiser des structures de données plus complexes, dans Julia, il existe des moyens d'utiliser des structures et des paramètres pour accélérer le calcul. L'orateur met en évidence les choix de conception clés de Julia qui permettent une compilation et une inférence de type rapides et spécialisées.

  • 01:15:00 Dans cette section, l'orateur décrit certains aspects techniques de Julia, tels que son implémentation de tableaux et de types paramétrés. Julia vise à éviter de créer trop de types privilégiés et permet à la place au code utilisateur d'être aussi bon que le code intégré. Julia a des types concrets, qui sont finaux et ne peuvent pas avoir de sous-types susceptibles de provoquer des erreurs. Par exemple, un sous-type d'un tableau ne serait pas un tableau réel de ce type mais pourrait causer des problèmes avec le compilateur pour une fonction qui utilise ce tableau. Le compilateur utilise LLVM pour générer du code machine après plusieurs passages, y compris l'analyse, la réécriture de macros et l'inférence de type. Julia dispose également de capacités de métaprogrammation, permettant aux utilisateurs de modifier la syntaxe et de réécrire le code. La génération de code est possible avec des tableaux multidimensionnels et les fonctionnalités parallèles sont moins avancées que des langages comme Silk, mais le langage n'a pas de verrou d'interpréteur global comme Python.

  • 01:20:00 Dans cette section, l'orateur discute des diverses capacités et bibliothèques fournies par Julia pour implémenter le threading, la récupération de place et le parallélisme de la mémoire distribuée. Le type BigNum et la bibliothèque BigFloat sont également introduits, ce qui permet la manipulation de nombres grands et précis. L'orateur note que Julia dispose d'un large éventail de supports Unicode en tant qu'identifiants et permet la complétion par tabulation des caractères LaTeX, ce qui peut être utile lors de la saisie d'équations. L'emprunt de cette fonctionnalité par Python est également mentionné.

  • 01:25:00 Dans cette section, l'intervenant discute de l'importance d'avoir des variables avec des noms propres et descriptifs dans les langages dynamiques. Il mentionne que le fait d'avoir des variables nommées dans un format spécifique peut rendre le code plus lisible et plus facile à comprendre. L'orateur remercie ensuite le présentateur et mentionne un projet qui explore la fusion de la technologie Julia avec la technologie Silk, ce qui pourrait conduire à de nouveaux développements à l'avenir.
 

Richard Feynman : Les machines peuvent-elles penser ?



Richard Feynman : Les machines peuvent-elles penser ?

Dans la vidéo "Richard Feynman : les machines peuvent-elles penser ?", Feynman soutient que si les machines sont meilleures que les humains dans de nombreux domaines comme l'arithmétique, la résolution de problèmes et le traitement de grandes quantités de données, les machines n'atteindront jamais une pensée et une intelligence humaines. Les machines ont du mal à reconnaître les images en raison de complexités telles que les variations de lumière et de distance, et bien que les ordinateurs reconnaissent les modèles, ils ne peuvent pas découvrir de nouvelles idées et relations par eux-mêmes. Feynman discute également de l'efficacité de l'utilisation de machines pour la prévision météorologique et d'autres tâches complexes, citant l'exemple d'un homme du nom de Lumic qui a utilisé une liste d'heuristiques pour remporter le championnat du jeu naval en Californie. Pour fabriquer des machines intelligentes, Feynman suggère aux développeurs d'éviter les distorsions psychologiques évoluant sournoisement et de se concentrer plutôt sur la recherche de nouvelles façons d'éviter le travail, car les machines montrent les faiblesses nécessaires de l'intelligence.

  • 00:00:00 Dans cette section des questions-réponses, Richard Feynman répond à la question de savoir si les machines atteindront un jour la pensée et l'intelligence humaines. Il pense que les machines ne penseront jamais comme les humains car elles sont fabriquées avec des matériaux différents et ne feront jamais les choses de la même manière. Cependant, il déclare que les machines sont meilleures que les humains dans de nombreux domaines, notamment l'arithmétique, la résolution de problèmes et le traitement de grandes quantités de données. Il soutient que les humains essaient toujours de trouver quelque chose qu'ils peuvent faire mieux que les machines, comme la reconnaissance de modèles, ce qui a été difficile à intégrer dans une procédure définie. Dans l'ensemble, Feynman offre une perspective intéressante sur les capacités des machines et leurs différences par rapport aux humains.

  • 00:05:00 Dans cette section, Feynman discute de la difficulté rencontrée par les machines pour reconnaître les images, en particulier par rapport aux humains. Ils ont du mal à tenir compte des variations de lumière, de distance, d'inclinaison et d'autres facteurs pouvant être présents dans différentes images. Alors que les humains peuvent facilement comparer les empreintes digitales, les machines ont souvent du mal à accomplir cette tâche en raison de la complexité de la correspondance parfaite des empreintes. Bien que les systèmes informatiques puissent faire des choses spécifiques que les gens peuvent faire et reconnaître des modèles, ils ne peuvent pas découvrir de nouvelles idées et relations par eux-mêmes pour le moment. L'homme a encore l'avantage sur les machines dans certains domaines, notamment dans le domaine de la reconnaissance où il existe des complications qui rendent la comparaison plus difficile.

  • 00:10:00 Dans cette section, Richard Feynman discute de l'idée d'utiliser des machines pour la prévision météorologique et d'autres tâches complexes. Il explique que les ordinateurs peuvent faire des prédictions plus précises que les humains, car ils peuvent analyser plus de cas et de variables à un rythme plus rapide. Alors que les gens ont expérimenté des approches heuristiques pour les machines, il est plus efficace de leur donner une procédure définie. Feynman cite l'exemple d'un homme nommé Lumic, qui a utilisé une liste d'heuristiques pour remporter le championnat du jeu naval en Californie. La machine de Lumic a appris de ses erreurs et est devenue plus efficace au fil du temps. Le processus d'apprentissage et de sélection de l'heuristique la plus efficace de la machine la rendait intelligente.

  • 00:15:00 Dans cette section, Richard Feynman discute d'une machine en cours de développement pour résoudre des problèmes et trouver de nouvelles heuristiques. La machine présentait un certain nombre de bogues, dont l'un impliquait une heuristique à laquelle un crédit était attribué chaque fois que la machine trouvait une solution. Cela a amené la machine à utiliser à plusieurs reprises cette heuristique, entraînant une distorsion des résultats. Feynman suggère que pour créer une machine intelligente, les développeurs devraient éviter de développer sournoisement une sorte de distorsion psychologique et se concentrer sur la recherche de nouvelles façons d'éviter le travail. Il conclut en déclarant que les machines montrent les faiblesses nécessaires de l'intelligence.
 

Regard sur l'IA : Ilya Sutskever



Regard sur l'IA : Ilya Sutskever

Ilya Sutskever aborde une variété de sujets liés à l'IA dans cette vidéo. Il partage son intérêt précoce pour l'IA et l'apprentissage automatique et décrit comment sa collaboration avec Jeff Hinton a conduit au développement du réseau neuronal convolutif AlexNet. Sutskever parle également des défis et des limites des modèles de langage, affirmant qu'ils font plus que simplement apprendre des régularités statistiques et que la représentation d'idées et de concepts est une réalisation importante. Il discute également du besoin de grandes quantités de données et de processeurs plus rapides dans la formation à l'IA et suggère la possibilité d'une forme de démocratie à large bande passante où les individus saisissent des données pour spécifier le comportement des systèmes.

  • 00:00:00 Dans cette section, Ilya Sutskever raconte son intérêt précoce pour l'IA et la conscience, et comment cela l'a amené à poursuivre l'apprentissage automatique, qu'il considérait comme l'aspect le plus important de l'intelligence artificielle à l'époque. Il note qu'en 2003, l'idée de l'apprentissage par ordinateur était encore totalement inaccessible, car la plus grande réalisation de l'IA à l'époque était Deep Blue, le moteur de jeu d'échecs. Sutskever raconte ensuite comment il a pu trouver Jeff Hinton, professeur à l'Université de Toronto, et commencer à travailler avec lui, ce qui a finalement conduit à leur collaboration sur le réseau de neurones convolutionnels, AlexNet, en 2012.

  • 00:05:00 Dans cette section de la vidéo, Ilya Sutskever parle de sa motivation précoce à contribuer à l'IA et de sa prise de conscience que la formation d'un réseau de neurones vaste et profond sur un ensemble de données suffisamment volumineux réussirait nécessairement à résoudre des tâches complexes telles que la vision . Il explique comment cette idée a conduit au succès du concours Imagenet et l'importance des réseaux de neurones convolutifs. Il explique ensuite comment le projet GPT a commencé avec l'exploration de l'idée que la prédiction du mot suivant pouvait conduire à un apprentissage non supervisé, qui était considéré comme le Saint Graal de l'apprentissage automatique avant qu'il ne soit complètement résolu. Ils utilisaient des réseaux de neurones récurrents à cette fin jusqu'à la sortie de l'article Transformer, qui leur a permis d'atteindre leurs objectifs.

  • 00:10:00 Dans cette section, Ilya Sutskever aborde les limites des grands modèles de langage, en particulier leurs connaissances contenues dans la langue sur laquelle ils sont formés et le manque de compréhension sous-jacente de la réalité. Il explique également comment la mise à l'échelle et l'apprentissage en profondeur ont fourni le tout premier moyen d'utiliser la mise à l'échelle de manière productive et d'en tirer quelque chose en retour, et à quel point ce que vous faites évoluer est important. Sutskever suggère que même s'il est difficile de parler des limites des modèles de langage, il est important de garder à l'esprit à quel point nous sommes convaincus que ces limites que nous voyons aujourd'hui seront toujours présentes dans deux ans.

  • 00:15:00 Dans cette section, Ilya Sutskever n'est pas d'accord avec l'idée que les modèles d'apprentissage automatique n'apprennent que des régularités statistiques et ne comprennent pas la nature du monde. Il soutient que l'apprentissage des régularités statistiques est une réalisation importante et ne doit pas être sous-estimé. En prédisant et en compressant les données, ces modèles acquièrent une compréhension plus profonde du monde tel qu'il est vu à travers les données, ce qui inclut la lentille du texte généré par les humains. Bien que les modèles de langage aient certaines limites pour produire de bons résultats, ils sont excellents pour apprendre des représentations d'idées, de concepts et de processus. Sutskever pense qu'en améliorant l'apprentissage par renforcement à partir de l'étape de rétroaction humaine, ce n'est qu'une question de temps avant que nous puissions limiter l'inclinaison de la machine pour les hallucinations et tirer parti de ses connaissances pour obtenir de meilleurs résultats.

  • 00:20:00 Dans cette section, Ilya Sutskever discute de la boucle de rétroaction dans la formation au réseau de neurones, où l'interface de discussion publique du GBT peut fournir des commentaires et générer une punition ou une récompense en fonction de l'interaction de l'utilisateur. Il mentionne que cette approche pourrait aider à résoudre le problème des hallucinations dans les réseaux de neurones. Sutskever commente également les travaux de Jana Kun sur les architectures prédictives d'intégration conjointe et l'idée d'un modèle mondial non linguistique sous-jacent à de grands modèles de langage. Il dit que bien que la compréhension multimodale soit souhaitable, il n'est pas nécessaire de comprendre le monde visuellement ou à partir de la vidéo, car certains concepts comme les couleurs peuvent encore être appris uniquement à partir du texte. Sutskever donne l'exemple que les incorporations de réseaux de couleurs sont similaires à la perception humaine.

  • 00:25:00 Dans cette section, l'orateur discute d'une affirmation faite dans un article selon laquelle l'un des grands défis est de prédire des vecteurs de grande dimension qui ont une incertitude à leur sujet, comme la prédiction d'une image. Cependant, l'orateur souligne que les transformateurs autorégressifs actuels ont déjà cette propriété et fonctionnent parfaitement bien, citant l'exemple du travail d'OpenAI sur igpt, où ils ont appliqué un transformateur aux pixels et généré des images de manière complexe et subtile. L'orateur soutient que les modèles pré-formés ont déjà une connaissance du langage et des processus dans le monde qui le produisent, y compris des représentations compressées des pensées, des sentiments et des interactions des gens. Par conséquent, la question d'enseigner aux modèles la réalité sous-jacente n'est pas de leur donner des connaissances mais d'automatiser le processus, ce qui, selon l'orateur, pourrait être réalisé de manière algorithmique.

  • 00:30:00 Dans cette section, Ilya Sutskever discute du processus d'enseignement des modèles pour devenir plus précis dans leurs sorties, expliquant que meilleur est le modèle de langage, meilleur est le modèle génératif, et plus la fidélité est élevée, plus il capture le processus. Il note que les modèles ont désormais les connaissances d'une "armée d'enseignants", qui utilisent l'assistance de l'IA pour devenir plus efficaces dans l'enseignement du modèle. Le processus d'apprentissage par renforcement implique que des enseignants humains examinent le comportement du modèle pour atteindre un haut niveau de fiabilité. Sutskever se concentre sur la fabrication de modèles plus fiables, contrôlables et plus rapides à apprendre tout en s'assurant qu'ils n'hallucinent pas. Il note les similitudes entre les grands modèles de langage et le cerveau humain et suggère que davantage de paramètres et de données sont nécessaires pour que les modèles plus grands puissent être gérés.

  • 00:35:00 Dans cette section, Ilya Sutskever discute du besoin de grandes quantités de données dans la formation à l'IA et déclare que même si cela est actuellement nécessaire dans les premières étapes de la formation, il peut être possible d'en apprendre davantage à partir de moins de données avec des idées créatives . Sutskever mentionne également le besoin de processeurs plus rapides pour mettre à l'échelle les modèles et la valeur potentielle des coûts si le résultat l'emporte sur eux. Sur le thème de la démocratie et de l'IA, Sutskever a exprimé son incertitude quant à la manière dont les gouvernements utiliseront la technologie pour obtenir des conseils, mais suggère qu'un processus démocratique impliquant des citoyens fournissant des informations aux réseaux de neurones pourrait être souhaitable à l'avenir.

  • 00:40:00 Dans cette section, Ilya Sutskever discute du rôle de l'IA dans la démocratie, suggérant que l'IA pourrait ouvrir une forme de démocratie à haut débit où les individus ont la possibilité de saisir des données pour spécifier le comportement des systèmes. Cependant, Sutskever soulève des questions sur la capacité de l'IA à comprendre et à analyser toutes les variables dans une situation donnée. Étant donné que même les entreprises de taille moyenne peuvent échapper à la compréhension d'un seul individu, il suggère que l'IA pourrait être incroyablement utile dans presque toutes les situations si elle est construite de la bonne manière.
 

Mathématiques pour l'apprentissage automatique - Calcul multivarié - Spécialisation en ligne complète



Mathématiques pour l'apprentissage automatique - Calcul multivarié - Spécialisation en ligne complète

  1. Cette vidéo YouTube fait partie de la spécialisation en ligne Calcul multivarié, qui vise à fournir une compréhension intuitive et graphique des concepts essentiels du calcul pour soutenir l'apprentissage automatique. La vidéo couvre une gamme de concepts, y compris la différenciation, la règle de la chaîne, la règle du produit, les fonctions de cas particuliers et la différenciation partielle, et souligne l'importance de comprendre les bases des mathématiques pour profiter pleinement de ses applications intrigantes. La vidéo présente également le calcul multivarié, qui nous permet d'appliquer le calcul pour naviguer dans des espaces de grande dimension et analyser des données multivariées à l'aide de la différenciation partielle et du concept de dérivée totale.

  2. Le concept de calcul multivarié pour l'apprentissage automatique est exploré dans cette série de vidéos. Le jacobien et le hessois sont introduits avec les techniques d'optimisation et la règle de la chaîne. Les réseaux de neurones sont couverts, avec un accent sur la formation et la rétropropagation. La série de Taylor est expliquée comme une méthode d'approximation des fonctions, et le processus de création d'approximations d'ordre supérieur à l'aide du calcul multivarié est discuté. La vidéo souligne l'importance de ces concepts dans la résolution de problèmes complexes du monde réel.

  3. La 3ème partie de la vidéo couvre divers aspects du calcul multivarié, en commençant par la série de Taylor en tant qu'outil d'approximation de fonctions en tant que série polynomiale pour construire une approximation de la fonction d'origine à des points proches. Il passe ensuite à la méthode de Newton-Raphson, qui utilise uniquement le gradient pour avancer vers la solution, et au concept de grad, un vecteur qui combine l'algèbre linéaire et le calcul. De plus, la vidéo explique la méthode des multiplicateurs de Lagrange, qui est utile pour résoudre les problèmes d'optimisation avec contraintes. Enfin, la vidéo montre comment ajuster les fonctions aux données à l'aide de la méthode des moindres carrés, ce qui peut aider à révéler les relations physiques et les hypothèses entre les variables. Dans l'ensemble, la vidéo fournit un aperçu complet des applications pratiques du calcul multivarié dans l'apprentissage automatique.

  4. Cette section de la vidéo explique comment ajuster les données à une fonction, en commençant par la régression linéaire et en passant aux modèles non linéaires. La formule de descente la plus raide pour l'ajustement des moindres carrés non linéaires est introduite, qui est utilisée pour minimiser la somme des carrés des résidus pour les modèles qui sont non linéaires dans les fonctions et les paramètres. La vidéo couvre également l'importance de générer une bonne estimation de départ pour les paramètres d'ajustement et de comparer visuellement l'ajustement aux données. Le cours fournit une compréhension introductive du calcul multivarié pour l'apprentissage automatique, de la définition d'une dérivée à ses applications dans les réseaux de neurones et la régression linéaire.

Partie 1

  • 00:00:00 Dans cette section, l'instructeur présente le cours de calcul multivarié pour les apprenants en apprentissage automatique. Le cours vise à fournir une compréhension du calcul et de ses applications à l'aide de graphiques et d'animations, le rendant plus intuitif et moins écrasant. Le cours se compose de six modules qui introduisent les concepts de calcul essentiels, en partant des bases et en développant des applications intéressantes dans les modules cinq et six. L'instructeur suggère de se concentrer sur le survol des détails et la représentation graphique des concepts pour faciliter une meilleure compréhension, mais également de fournir des liens vers des descriptions plus rigoureuses pour les personnes intéressées. Enfin, la section souligne l'importance de comprendre le travail de base ennuyeux des mathématiques, y compris ses bizarreries et sa notation, pour profiter pleinement des applications intéressantes des mathématiques telles que l'apprentissage automatique.

  • 00:05:00 Dans cette section, l'instructeur explique comment la sélection d'une fonction est l'essence créative de la science et comment le calcul nous permet d'extraire bien plus que la simple vitesse d'un graphique de vitesse en fonction du temps pour une voiture. L'accélération est définie comme le gradient local et peut également être tracée en fonction du temps pour créer un nouveau graphique à analyser. L'instructeur montre comment un graphique à vitesse constante aurait un gradient constant de zéro, tandis qu'un graphique plus complexe aurait des points variables de gradient positif et négatif. En fin de compte, le calcul infinitésimal n'est qu'un ensemble d'outils pour décrire la relation entre une fonction et le changement de ses variables, et il nous permet de les étudier et de les manipuler.

  • 00:10:00 Dans cette section, le concept de prise de la dérivée de la fonction d'accélération est discuté en prenant la pente de la fonction d'accélération en chaque point, connue sous le nom de secousse de la voiture. La vidéo explore également l'idée de la procédure primitive ou inverse, qui est étroitement liée à ce qu'on appelle l'intégrale. La discussion passe ensuite à la définition formelle d'une dérivée en définissant le concept de gradients à l'aide de la notation mathématique. Le gradient d'une fonction linéaire est expliqué à l'aide de la formule de montée sur course où la montée et la course sont respectivement les distances le long des axes vertical et horizontal. Enfin, le concept de la façon dont le schéma de notation limite peut être utilisé pour exprimer le gradient est également exploré.

  • 00:15:00 Dans cette section, la vidéo explique le concept de différenciation et comment il est utilisé pour trouver le gradient d'une fonction. Le processus consiste à prendre la limite lorsque Delta X s'approche de zéro de l'expression (f(x+Delta X) - f(x)) / Delta X, qui donne la pente de la tangente en ce point. La vidéo fournit des exemples de recherche du gradient de fonctions linéaires et quadratiques simples à l'aide de cette méthode, démontrant l'interchangeabilité de la règle de somme. Les gradients résultants sont respectivement une constante et une fonction de x.

  • 00:20:00 Dans cette section, l'instructeur explique la règle de puissance pour la différenciation. Si nous prenons une fonction f de X égale AX à la puissance B et la différencions, le résultat est f tiret de X égal ABX à la puissance B moins 1, ce qui est connu sous le nom de règle de puissance. L'instructeur mentionne également que la différenciation peut devenir fastidieuse pour les expressions longues et compliquées. Pour accélérer le processus, nous pouvons utiliser des règles telles que les règles de somme et de puissance. La vidéo passe ensuite à l'explication de trois fonctions de cas particuliers qui nous donnent des résultats intéressants lorsqu'elles sont différenciées. La première fonction est f de X égal à 1 sur X, qui montre une discontinuité à x égal à 0. L'instructeur applique l'expression de différenciation à cette fonction pour étudier son gradient.

  • 00:25:00 Dans cette section, la vidéo traite de certaines fonctions de cas particuliers dans le calcul. Premièrement, ils expliquent une fonction avec la propriété que la valeur de la fonction est toujours égale à la valeur de son propre gradient. La fonction exponentielle e aux X est la seule fonction satisfaisant tous les critères nécessaires. Ensuite, la vidéo parle des fonctions trigonométriques sinus et cosinus et de leurs dérivées. Le motif auto-répétitif de ces fonctions peut rappeler la fonction exponentielle. En fin de compte, la vidéo souligne que la différenciation est un concept simple, et même si l'on ne peut pas travailler sur toute l'algèbre, on peut simplement rechercher le gradient de montée ou de course à chaque point.

  • 00:30:00 Dans cette section, la vidéo explique la règle du produit, un raccourci pratique pour différencier le produit de deux fonctions. La règle permet aux mathématiciens d'éviter le processus fastidieux de calcul des dérivées lorsqu'il s'agit de fonctions relativement simples. La règle est décrite par l'utilisation d'un rectangle dont un côté est la fonction f de x et l'autre côté est la fonction g de x. Le produit de ces deux fonctions nous donne l'aire du rectangle, que l'on peut appeler a de x. En divisant le rectangle en quatre régions, des changements latéraux avec de petites quantités de Delta X sont effectués et le plus petit rectangle qui se rétrécira le plus rapidement peut être ignoré. L'expression finale de la dérivée de a par rapport à x est f de x fois la dérivée de G de X plus G de X fois la dérivée de f de x.

  • 00:35:00 Dans cette section de la vidéo, le concept de la règle de la chaîne est introduit et utilisé pour trouver le taux de variation du bonheur par rapport à l'argent en reliant les fonctions du bonheur et de la pizza et de la pizza et de l'argent. La règle de la chaîne est un moyen de créer une chaîne de relations dérivées et est particulièrement utile pour les fonctions compliquées où la substitution directe peut ne pas être une option. La vidéo applique ensuite la règle de la chaîne aux fonctions et obtient la fonction souhaitée du taux de variation du bonheur par rapport à l'argent. La vidéo se termine par une discussion des avantages de la règle de la chaîne et un aperçu de la manière dont toutes les règles permettant de gagner du temps seront utilisées dans la vidéo suivante.

  • 00:40:00 Dans cette section, nous voyons un exemple d'application de la règle du produit en calcul à une fraction réécrite en tant que produit. La première étape consiste à réécrire la fonction en tant que produit en déplaçant le dénominateur vers le haut et en l'élevant à la puissance moins un. Ensuite, la fonction est divisée en deux parties distinctes : G de X et H de X. La dérivée de chaque partie est calculée en utilisant une notation différente et en appliquant les règles de somme, de puissance et de chaîne. Une fois que nous avons les expressions dérivées pour les deux parties, nous pouvons appliquer la règle du produit pour obtenir la réponse finale. La section se termine par un rappel que des fonctions apparemment intimidantes peuvent être facilement apprivoisées avec les bons outils, tandis que des fonctions apparemment simples peuvent être difficiles mais aussi amusantes à utiliser.

  • 00:45:00 Dans cette section de la vidéo, l'instructeur présente le calcul multivarié, qui est une extension du concept de différenciation appris dans le module précédent. Avec plus d'une variable à analyser, le calcul peut maintenant être appliqué pour aider à naviguer dans des espaces de grande dimension. L'instructeur explique les différences subtiles entre l'utilisation des termes "multivariable" et "multivariable", bien que la distinction ne soit pas critique. La discussion se poursuit ensuite pour clarifier les subtilités des variables et des paramètres dans le contexte des applications de calcul. Dans les prochains modules, l'instructeur appliquera le calcul à certains problèmes d'analyse de données intéressants.

  • 00:50:00 Dans cette section, l'orateur explique comment utiliser la différenciation partielle pour trouver la dérivée d'une fonction par rapport à chacune de ses variables. Ils fournissent un exemple de calcul de la masse d'une canette en décomposant sa surface en différentes parties et en multipliant ces parties par l'épaisseur et la densité du métal. Ils montrent comment trouver la dérivée partielle de la masse de la canette par rapport à chacune de ses variables (rayon, hauteur, épaisseur et densité) et expliquent comment utiliser le symbole partiel bouclé pour différencier une fonction de plus d'une variable. L'orateur conclut que la différenciation partielle n'est pas beaucoup plus compliquée que le calcul univarié et est un concept essentiel en apprentissage automatique.

  • 00:55:00 Dans cette section, le concept de différenciation partielle est introduit et le didacticiel utilise l'exemple d'une fonction de trois variables pour illustrer comment trouver des dérivées partielles. Ensuite, le didacticiel présente le concept de dérivée totale et explique qu'il est utilisé pour mesurer les changements qui se produisent en raison d'un petit changement dans tous les paramètres d'une fonction. Le didacticiel explique comment calculer la dérivée totale et comment utiliser la règle de la chaîne pour résoudre des problèmes avec de nombreuses variables. Enfin, le jacobien est présenté comme un moyen d'intégrer certaines des idées de l'algèbre linéaire et de transformer ces dérivées partielles en quelque chose de particulièrement utile dans le contexte de l'optimisation et de l'apprentissage automatique.

Partie 2

  • 01:00:00 Dans cette section, le concept de jacobien est expliqué dans le contexte du calcul multivarié. Le jacobien est une expression algébrique pour un vecteur qui, lorsqu'il est donné des coordonnées XYZ spécifiques, renvoie un vecteur pointant dans la direction de la pente la plus raide d'une fonction. La vidéo explore ensuite un exemple bidimensionnel d'une fonction compliquée et attrayante avec un tracé de contour pour illustrer ce concept. On montre que les vecteurs jacobiens pointent vers le haut loin des régions basses et sombres et vers les régions hautes et lumineuses. Cet exemple clair en deux dimensions est destiné à donner confiance aux téléspectateurs pour les problèmes de dimension supérieure à explorer plus tard dans le cours.

  • 01:05:00 Dans cette section sur le calcul multivarié pour l'apprentissage automatique, le concept de vecteur jacobien et de matrice jacobienne est exploré. Le vecteur jacobien est utilisé pour trouver le champ vectoriel d'une fonction, où l'origine représente un maximum, un minimum ou une selle, et la matrice jacobienne est construite pour les fonctions qui prennent un vecteur comme entrée et sortie. Pour les fonctions linéaires, la matrice jacobienne est un gradient constant et peut être utilisée pour transformer des coordonnées entre des espaces vectoriels. Bien que de nombreuses fonctions d'apprentissage automatique soient hautement non linéaires, leur régularité permet de considérer chaque petite région de l'espace comme approximativement linéaire, et le jacobien à chaque point peut être additionné pour calculer le changement de taille.

  • 01:10:00 Dans cette section, le concept d'optimisation en mathématiques est introduit, qui fait référence à la recherche de valeurs d'entrée pour les fonctions qui correspondent aux valeurs maximales ou minimales d'un système. Le processus d'optimisation est utilisé dans une gamme de scénarios réels, tels que la planification des itinéraires, la planification de la production et la sélection des stocks. Pour trouver les maxima et les minima d'une fonction simple, le jacobien peut être construit et ses valeurs déterminées, mais pour des fonctions plus complexes, trouver les valeurs optimales peut être plus difficile. L'analogie d'une sablière avec une base inégale est utilisée pour expliquer le processus de recherche du point le plus profond d'un système à l'aide du jacobien.

  • 01:15:00 Dans cette section, le concept de matrice hessienne est introduit pour les systèmes multivariés qui peuvent être considérés comme une extension du vecteur jacobien. La matrice hessienne est une matrice carrée N sur n pour une fonction de n variables, où n est le nombre de variables dans la fonction f. Pour trouver le hessois, nous pouvons d'abord trouver le jacobien, puis différencier à nouveau ses termes. La matrice hessienne est symétrique sur la diagonale principale et peut être utilisée pour déterminer si une fonction est un maximum ou un minimum en un point. Le déterminant du hessien est utilisé pour déterminer si une fonction est un point de selle ou non.

  • 01:20:00 Dans cette section, la vidéo traite des limites des paysages bidimensionnels et des défis associés aux dimensions plus élevées, aux calculs coûteux, aux caractéristiques nettes et aux fonctions bruyantes. La méthode des différences finies est introduite comme technique d'approximation pour générer des solutions à des problèmes qui peuvent ne pas avoir de formule explicite. En faisant de petits pas dans différentes directions, le jacobien peut être approximé en utilisant cette approche, mais il est important de trouver le bon équilibre dans le choix de la taille des pas.

  • 01:25:00 Dans cette section, la vidéo commence par une discussion sur les données bruitées et les défis qui surviennent lorsqu'il s'agit de fonctions coûteuses en calcul. L'orateur souligne que l'approche la plus simple pour traiter les données bruitées consiste à calculer le gradient en utilisant quelques tailles de pas différentes et en prenant une sorte de moyenne. La vidéo présente ensuite le module 3, où la règle de chaîne univariée sera mise à niveau pour aborder les fonctions multivariées. L'orateur simplifie la notation et explique que la règle de la chaîne multivariable peut être exprimée proprement par le produit scalaire de deux expressions dérivées multivariables. La vidéo se termine en soulignant que le reste des règles de gain de temps fonctionnent déjà pour les problèmes multivariés, concluant leur discussion sur la forme généralisée de la règle de la chaîne multivariable.

  • 01:30:00 Dans cette section, la vidéo explique comment la règle de chaîne fonctionne pour plus de deux liens en utilisant un exemple univarié avec trois fonctions. La vidéo présente ensuite le cas multivarié, où la règle de chaîne fonctionne toujours mais avec une attention supplémentaire aux détails, comme la matrice jacobienne. La dérivée de F par rapport à T est le produit du jacobien de F avec le jacobien de X et le vecteur dérivé de U, conduisant à une sortie scalaire. Ce concept est crucial pour les réseaux de neurones artificiels et leur application aux problèmes du monde réel.

  • 01:35:00 Dans cette section, la vidéo présente la fonction mathématique d'un réseau de neurones. Un réseau de neurones est simplement une fonction qui prend une variable et renvoie une autre variable, où les deux variables peuvent être des vecteurs. Chaque nœud d'un réseau de neurones est appelé une activité, qui consiste en un poids, un biais et une fonction d'activation (représentée par la lettre grecque Sigma) qui donne aux réseaux de neurones leur association avec les neurones du cerveau. La vidéo montre comment créer plus de complexité dans le réseau en ajoutant plus de neurones et généralise l'expression pour prendre n entrées, poids, biais et sorties, qui peuvent être représentés sous une forme vectorielle compacte. La dernière pièce du puzzle consiste à ajouter des couches cachées de neurones entre les entrées et les sorties, qui se comportent de la même manière que les couches précédentes.

  • 01:40:00 Dans cette section, le concept de formation de réseaux de neurones à l'aide de données étiquetées et de rétropropagation est introduit. L'accent est mis sur la recherche des poids et des biais qui permettent au réseau de faire correspondre au mieux les entrées de formation à leurs étiquettes, en choisissant une structure simple, puis en mettant progressivement à jour les poids et les biais. Une fonction de coût est définie et le gradient de C par rapport à la variable W est pris pour déterminer la direction de mise à jour des poids et des biais. De plus, l'expression de règle de chaîne pour la dérivée partielle du coût est mise en surbrillance, qui peut être utilisée pour naviguer dans l'espace WB afin de minimiser le coût du réseau pour un ensemble d'exemples de formation.

  • 01:45:00 Dans cette section de la vidéo, la série de Taylor est présentée comme une approche pour construire des approximations de fonctions. La vidéo fournit un exemple de la façon dont la série Taylor peut être utilisée pour approximer les temps de cuisson des poulets. Le processus implique de faire des hypothèses sur les propriétés du four et du poulet, et d'utiliser une série de fonctions plus simples pour modéliser la relation entre la masse du poulet et le temps de cuisson. La méthode des séries de Taylor permet de dériver une fonction avec la même pente et la même hauteur que l'un des points du graphique, mais à mesure que l'on s'éloigne du point d'intérêt, l'approximation devient médiocre. La vidéo explique également que la série de Taylor peut être appelée série de puissance et fournit une expression généralisée simple pour une série de puissance.

  • 01:50:00 Dans cette section, le concept de séries tronquées et le processus de construction de fonctions par approximations sont discutés. Une série de puissances généralisées est introduite comme une série de puissances croissantes de X. La méthode des séries de Taylor permet la reconstruction d'une fonction partout ailleurs en sachant tout sur la fonction en un point. Cette méthode ne peut être utilisée que pour des fonctions continues bien comportées. L'amélioration progressive des approximations pour construire une fonction est démontrée graphiquement avec un exemple. Les premières approximations sont basées sur seulement une ou deux informations, tandis que davantage d'informations sont utilisées pour améliorer davantage les approximations.

  • 01:55:00 Dans cette section, la vidéo traite du processus de création d'approximations d'ordre supérieur d'une fonction à l'aide du calcul multivarié. Il commence par trouver les approximations du premier et du second ordre en utilisant des informations telles que F(0), F'(0) et F''(0) pour créer des équations quadratiques. La vidéo passe ensuite à la discussion des approximations des troisième et quatrième ordres, montrant que des termes d'ordre supérieur par morceaux peuvent être ajoutés tout en gardant les mêmes termes d'ordre inférieur. La vidéo note également que le coefficient devant le terme cubique dans l'approximation cubique résulte de la différenciation d'un terme cubique deux fois. Dans l'ensemble, la vidéo démontre l'utilité du calcul multivarié dans l'approximation de fonctions complexes.

Partie 3

  • 02:00:00 Dans cette section, le concept de série de puissance est appliqué plus en détail, dans lequel nous différencions la fonction "e au x" terme par terme et avons trouvé quelque chose de satisfaisant qui reste inchangé. La série de Taylor reconnaît qu'il n'y a rien de spécial à propos du point x égal à 0 et dit que si vous savez tout sur la fonction à tout moment, vous pouvez reconstruire la fonction n'importe où. En partant du point x est égal à P, on peut ajuster l'équation allemande pour permettre des points d'expansion arbitraires. Le terme d'ordre zéro sera une ligne horizontale qui utilise juste le point F de P partout, et pour construire une tangente à la courbe au point P, nous devons noter toutes les informations disponibles et utiliser le gradient de la fonction.

  • 02:05:00 Dans cette section, l'orateur présente la série de Taylor comme un outil utile pour approximer des fonctions en tant que séries polynomiales. Il montre comment convertir la série de Maclaurin en la forme générale de la série de Taylor en appliquant la dérivée seconde en un point P et en remplaçant X par X moins P. L'expression de la série de Taylor unidimensionnelle résultante peut être utilisée pour réexprimer commodément des fonctions sous forme de séries polynomiales. L'orateur montre également comment construire une extension en série de Maclaurin de la fonction cosinus et utilise cet exemple pour expliquer le modèle cyclique des cosinus et des sinus, l'absence de puissances impaires de X dans la série et l'utilisation de la notation de sommation pour décrire complètement le série. La section se termine par un rappel d'être prudent lors de la manipulation d'approximations en série et de connaître le domaine dans lequel elles sont acceptables.

  • 02:10:00 Dans cette section, l'orateur explique comment la série de Taylor peut avoir du mal à gérer une fonction qui se comporte mal comme 1/X en raison de sa discontinuité à x=0, ce qui conduit à des valeurs indéfinies. Cependant, en allant ailleurs, comme x = 1, et en appliquant la série de Taylor avec une notation de sommation soignée, une séquence d'approximations améliorées des fonctions peut être construite. La vidéo explore ensuite l'erreur attendue dans une approximation et comment utiliser l'approximation du premier ordre pour évaluer une fonction près du point P. L'orateur mentionne que l'erreur peut être calculée avec précision, ce qui permet d'estimer la précision d'une approximation donnée. .

  • 02:15:00 se rapprochant de la fonction d'origine à un point proche. Dans cette section, nous apprenons le terme d'erreur introduit dans l'approximation du premier ordre, qui est de l'ordre de Delta x au carré dans le cas d'un petit nombre. Nous voyons également comment l'approximation de la montée par rapport à la course peut nous aider à construire la définition d'une dérivée et de l'erreur dans celle-ci lorsque le deuxième point reste à une distance finie de X. Nous mettons ensuite à niveau la série de puissances vers sa forme multivariée plus générale dans le cas bidimensionnel , qui donne une fonction bidimensionnelle pour approximer la fonction d'origine en un point proche. Dans l'ensemble, ces concepts jouent un rôle important lors de l'application de méthodes numériques à la résolution de problèmes.

  • 02:20:00 Dans cette section, l'instructeur décrit comment créer des extensions de la série Taylor pour les fonctions multivariées. Une approximation d'ordre zéro est simplement une surface plane avec la même hauteur que la fonction au point d'expansion, tandis que l'approximation du premier ordre intègre les informations de gradient dans les deux directions. Pour l'approximation du second ordre, nous avons trois termes, qui sont tous des dérivées secondes, et pour faire cette somme, nous devons multiplier notre vecteur Delta X par le hessien, puis à nouveau par la transposée du vecteur Delta X. L'instructeur explique que cela se généralise immédiatement de la 2D aux hyper surfaces multidimensionnelles, en utilisant des compétences en calcul et en algèbre linéaire, ainsi que les concepts jacobiens et hessiens.

  • 02:25:00 Dans cette section, le narrateur explique une méthode pour ajuster une équation à une distribution de hauteurs en utilisant deux paramètres, moyenne et largeur, au lieu de transporter tous les points de données. Le processus implique de trouver une expression de l'adéquation du modèle aux données, puis d'examiner comment cette qualité d'ajustement change à mesure que les paramètres d'ajustement changent. Le narrateur présente ensuite la méthode Newton-Raphson, qui consiste à itérer pour deviner une solution à une équation, à l'évaluer, à générer une nouvelle supposition et à répéter le processus jusqu'à ce que la solution soit atteinte. Cette méthode est utile lorsqu'une grande fonction multidimensionnelle est ajustée aux données et qu'il est trop coûteux de la résoudre analytiquement ou de la tracer.

  • 02:30:00 Dans cette section de la vidéo, la méthode Newton-Raphson est présentée comme un moyen de résoudre des équations en utilisant uniquement le gradient pour avancer vers la solution. Cependant, la méthode peut parfois créer des problèmes, comme rester coincé dans une boucle ou diverger vers des valeurs folles. Malgré cela, la méthode est un moyen puissant d'itération vers une solution. La section suivante de la vidéo se concentre sur la façon d'appliquer cette méthode à des fonctions à plusieurs variables en trouvant le vecteur de gradient et en descendant une colline sur un tracé de contour. Cela permettra éventuellement d'optimiser et de trouver le meilleur ajustement pour les paramètres d'une fonction.

  • 02:35:00 Dans cette section, le concept de grad, un vecteur qui combine l'algèbre linéaire et le calcul, est expliqué. Grad est défini comme le vecteur où nous écrivons DF par DX et DF par DY dans les emplacements X&Y du vecteur. Le gradient directionnel est présenté comme le produit scalaire de grad F avec un vecteur unitaire, qui est parallèle à grad F, et la valeur maximale du gradient directionnel est la taille de grad F. La direction dans laquelle grad pointe est expliquée comme la direction de descente la plus raide perpendiculaire aux courbes de niveau. Enfin, l'utilisation du gradient pour minimiser la différence entre les valeurs des données et l'ajustement du modèle est discutée.

  • 02:40:00 donné est que X au carré plus Y au carré est égal à A au carré, ce qui signifie que les points que nous regardons sont tous sur un cercle de rayon A. Pour trouver les maxima ou les minima sur ce chemin, nous pouvons utiliser le méthode des multiplicateurs de Lagrange. Cela implique de trouver où le vecteur gradient perpendiculaire au contour de la fonction est dans la même direction, jusqu'à un signe moins, que le vecteur gradient perpendiculaire à la trajectoire du cercle. Cela nous donnera les points où le contour touche juste le chemin, où nous trouverons les minima et les maxima. Cette approche nous permet de résoudre des problèmes d'optimisation soumis à des contraintes, comme trouver la valeur maximale ou minimale d'une fonction le long d'un certain chemin.

  • 02:45:00 Dans cette section, le concept de multiplicateurs de Lagrange est présenté comme un outil pour résoudre des problèmes d'optimisation avec contraintes. Un exemple pratique impliquant une contrainte d'équation de cercle et une fonction multivariable est utilisé pour illustrer l'utilisation des multiplicateurs de Lagrange. Les équations sont établies et résolues pour trouver les valeurs maximales et minimales de la fonction dans la contrainte. Le tracé des résultats en trois dimensions montre les points maximum et minimum. Cette méthode peut être utile dans les problèmes d'optimisation en apprentissage automatique où des contraintes sont impliquées.

  • 02:50:00 Dans cette section, la vidéo explique comment optimiser les fonctions et résoudre des problèmes à l'aide du calcul multivarié. La méthode de Newton-Raphson est introduite qui utilise des gradients pour estimer la distance à parcourir entre une supposition actuelle et une solution pour un problème, tandis que le vecteur de gradient est défini comme perpendiculaire aux courbes de niveau et a des éléments égaux à la différence de la fonction le long de chaque axe. La vidéo montre ensuite comment résoudre un problème soumis à une contrainte en assimilant la fonction de gradient à la tangente de la contrainte, en utilisant la méthode du multiplicateur de Lagrange. L'application du calcul multivarié peut aider à ajuster les fonctions aux données à l'aide de la méthode des moindres carrés, permettant aux données d'être nettoyées, analysées et représentées graphiquement pour révéler les relations physiques et les hypothèses entre les variables.

  • 02:55:00 Dans cette section de la vidéo, le conférencier explique comment trouver la valeur optimale de m et c à l'aide d'un R résiduel et d'une mesure de la qualité de l'ajustement appelée chi carré. Il définit R comme la différence entre les éléments de données et leur emplacement prévu sur la ligne et le chi carré comme la somme des carrés des résidus. En traçant à quoi ressemblera le chi carré pour de nombreuses valeurs possibles différentes de M et C, il trouve le minimum à environ 215 et près d'une interception de 0. Le minimum est trouvé lorsque le gradient de chi carré est nul . Le conférencier explique ensuite comment résoudre explicitement le problème et montre ensuite comment le faire par descente linéaire. Il explique également comment se faire une idée des incertitudes sur les paramètres d'ajustement.

Partie 4

  • 03:00:00 Dans cette section, le concept d'ajustement d'une ligne à certaines données par régression est discuté, et la qualité de l'estimateur d'ajustement chi carré qui mesure l'écart de l'ajustement par rapport aux données est introduite. L'importance de comparer visuellement l'ajustement est mise en évidence ainsi que le fait que l'interception dépend du gradient. Le problème est refondu comme l'emplacement du centre de masse en y à la barre y pour éliminer l'incertitude dans le gradient lors de l'examen du terme constant dans l'ajustement. La vidéo continue ensuite en parlant de fonctions d'ajustement qui sont arbitrairement plus compliquées que la régression linéaire, et les paramètres sont ajustés aux données à l'aide des moindres carrés non linéaires, où le chi carré est calculé comme la somme de tous les points de données du différence entre le YI et le modèle de XI avec ses paramètres a K, le tout divisé par Sigma au carré.

  • 03:05:00 Dans cette section, l'orateur discute de la formule de descente la plus raide pour l'ajustement des moindres carrés non linéaires, qui est utilisée pour minimiser la somme des carrés des résidus pour un modèle non linéaire dans les fonctions et les paramètres d'ajustement. L'orateur explique que cette formule est utilisée pour mettre à jour le vecteur des paramètres d'ajustement à chaque itération jusqu'à ce que la valeur minimale du chi carré soit atteinte, ce qui pourrait être lorsque le gradient du chi carré est égal à zéro ou lorsque la valeur du chi carré cesse de changer. Bien qu'il existe différentes méthodes pour résoudre ces types de problèmes, la descente la plus raide est la plus simple et suffit pour trouver la valeur minimale d'un problème d'ajustement généralisé des moindres carrés non linéaires.

  • 03:10:00 cette section sur le calcul multivarié, la vidéo explique diverses méthodes pour résoudre les problèmes des moindres carrés non linéaires, y compris l'utilisation du hessien pour une convergence plus rapide, la méthode de Levenberg-Marquardt pour la stabilité et un ajustement robuste pour gérer les valeurs aberrantes. La vidéo montre ensuite comment utiliser MATLAB et Python pour effectuer un ajustement de courbe des moindres carrés non linéaire, en utilisant l'exemple d'ajustement d'une distribution gaussienne aux données de hauteur de population. Il souligne l'importance de commencer par une estimation raisonnable des paramètres initiaux pour garantir que l'algorithme peut converger vers un minimum significatif.

  • 03:15:00 Dans cette section, l'orateur souligne l'importance de générer une bonne estimation de départ et de comparer l'ajustement aux données lors de l'ajustement des données aux fonctions. Ils concluent la discussion sur l'utilisation du calcul multivarié pour optimiser les fonctions et ajuster les données aux fonctions, notant qu'il est facile d'adapter les fonctions par calcul dans quelques lignes de code en Python, MATLAB ou R. Cependant, l'orateur note l'importance de comprendre comment les algorithmes fonctionnent sous le capot et comment les corriger en cas de problème. Le cours a fourni une compréhension introductive du calcul multivarié pour l'apprentissage automatique, de la définition d'un dérivé à la façon dont il peut être appliqué dans les réseaux de neurones et la régression linéaire, permettant une intuition sur où le calcul peut être utile.
1...242526272829303132333435363738...75
Nouveau commentaire