L'édition de cette année de la Conférence internationale sur l'apprentissage machine (ICML) sera virtuelle et se déroulera du dimanche 13 juillet au samedi 18 juillet.
L'ICML est l'une des principales conférences mondiales sur l'apprentissage machine, comme en témoigne le nombre important d'articles soumis. Cette année, la conférence a accepté 1 088 articles sur 4 990 soumissions, soit un taux d'acceptation de 21,8 % (contre 22,6 % en 2019). Dix-neuf articles de professeurs du département Vector ont été acceptés, ainsi que cinq articles de professeurs affiliés à ce département. Au total, les articles relatifs à Vector représentent 2,21 % du nombre total d'articles acceptés à l'ICML 2020.
Vous trouverez ci-dessous des résumés en langage clair de certains travaux que les chercheurs de Vector présenteront lors de l'édition de cette année de la conférence. Les résumés marqués d'un astérisque (*) correspondent au résumé original de l'article.
Faculté des vecteurs
Beidi Chen (Université Rice) · Weiyang Liu (Georgia Tech) · Zhiding Yu (NVIDIA) · Jan Kautz (NVIDIA) · Anshumali Shrivastava (Université Rice) · Animesh Garg (Université de Toronto, Vector Institute, Nvidia) · Anima Anandkumar (Caltech)
Les modèles d'apprentissage profond pour le raisonnement sur les images offrent des performances impressionnantes, mais souffrent souvent d'un mauvais étalonnage. Ils ont tendance à être trop confiants, leur niveau de confiance ne reflétant pas toujours l'ambiguïté et la complexité réelles des points de données. Nous proposons une nouvelle méthode pour mesurer cette complexité, que nous appelons « Difficulté Visuelle Angulaire » (DVA). Étant donné une image particulière, est-il difficile pour un modèle d'apprentissage automatique de déterminer s'il s'agit d'un petit pain à la cannelle ou d'un chiot en boule ? Nous avons aussi trouvé une corrélation statistiquement significative entre la DVA et la difficulté visuelle humaine, ce qui signifie que les humains perçoivent ces problèmes comme tout aussi difficiles. La mesure de cette confusion est importante pour entraîner de meilleurs modèles avec moins de données, ainsi que des modèles capables de prendre des décisions plus équitables avec des ensembles de données déséquilibrés. L'alignement de l'entraînement sur cette mesure de complexité permet également une meilleure généralisation aux variations de la distribution des données de test.
Modélisation causale pour l'équité dans les systèmes dynamiques
Elliot Creager (Université de Toronto) · David Madras (Université de Toronto) · Toniann Pitassi (Université de Toronto) · Richard Zemel (Institut Vector)
Dans les applications d'apprentissage automatique (AA) où l'équité est un enjeu crucial, les données disponibles sont souvent « manquantes de manière non aléatoire » en raison de biais inhérents à la politique historique de prise de décision. Dans le secteur du crédit, par exemple, la solvabilité réelle d'un demandeur est inconnue tant qu'un prêt ne lui est pas accordé. Ainsi, si une population de demandeurs s'est vu offrir moins de prêts selon la politique historique, cette population sera sous-représentée dans l'ensemble de données résultant. Nous étudions l'équité à long terme des décisions prises par l'AA et montrons que des articles récents sur ce sujet peuvent être reformulés sous forme de modèles causaux. Ce paradigme de modélisation est mieux adapté aux problèmes de données manquantes de manière non aléatoire et permet d'utiliser des outils issus de l'inférence causale pour améliorer l'estimation de la performance des politiques futures sur des populations sous-représentées, contribuant ainsi à la recherche de politiques plus équitables dans ces contextes.
Yingyi Ma (UIC) · Vignesh Ganapathiraman (Université de l'Illinois à Chicago) · Yaoliang Yu (Université de Waterloo) · Xinhua Zhang (Université de l'Illinois à Chicago (UIC))
La découverte automatique de représentations invariantes à certaines transformations (comme les changements de pose et d'expressions faciales, la translation ou la rotation d'objets rigides, les relations sémantiques ou logiques entre classes, et les relations structurées entre entités) est essentielle pour permettre aux algorithmes d'apprentissage de gérer l'immense variété des objets réels. Nous développons un cadre de régularisation basé sur les semi-produits scalaires afin d'induire un large ensemble d'invariances généralisées qui dépassent le cadre des espaces de Hilbert à noyau reproduisant classiques. Nous proposons des implémentations efficaces basées sur les plongements euclidiens et démontrons l'efficacité de notre algorithme pour l'augmentation de données et la prédiction multiétiquettes structurée.
Supprimer l'intermédiaire : Entraînement et évaluation de modèles énergétiques sans échantillonnage
Will Grathwohl (Université de Toronto) · Kuan-Chieh Wang (Université de Toronto) · Joern-Henrik Jacobsen (Institut Vector et Université de Toronto) · David Duvenaud (Université de Toronto) · Richard Zemel (Institut Vector)
Pour faire des prédictions à partir d'un ensemble de données, il faut ajuster un modèle qui évalue la probabilité des différentes prédictions. L'ajustement de ce modèle implique de comparer les prédictions aux données originales. Étant donné le nombre infini de prédictions possibles, il peut être difficile de quantifier l'écart entre toutes les prédictions possibles du modèle et les données. Notre article propose d'utiliser un réseau de neurones pour apprendre cet écart. Une fois ce réseau ajusté, il est possible de modifier les prédictions du modèle afin de réduire cet écart.
Détection d'exemples hors distribution à l'aide de matrices de Gram
Chandramouli Shama Sastry (Université Dalhousie/Institut Vector) · Sageev Oore (Université Dalhousie et Institut Vector)
Les réseaux neuronaux ignorent souvent leurs propres lacunes : un classificateur précis de lésions cutanées pourrait non seulement identifier l’image d’un chien comme appartenant à un type de lésion particulier, mais aussi le faire avec une grande certitude. Cela s’explique par le fait que les chiens constituent un type (ou une distribution) d’images différent de tout ce que le réseau a vu lors de son apprentissage. L’une des difficultés pratiques réside dans l’impossibilité pour le réseau de s’y préparer à l’avance (c’est-à-dire qu’il ne peut pas entrevoir tous les types d’images qu’il pourrait rencontrer lors de son déploiement !). Cette recherche obtient des résultats de pointe en matière de détection de la présentation d’un type d’image inhabituel. Notre algorithme y parvient en repérant des schémas inhabituels dans les activations internes du réseau.
Évaluation des taux de compression avec perte des modèles génératifs profonds
Sicong Huang (Université de Toronto) · Alireza Makhzani (Université de Toronto) · Yanshuai Cao (Borealis AI) · Roger Grosse (Université de Toronto et Vector Institute)
Les réseaux antagonistes génératifs (GAN) ont démontré une capacité impressionnante à générer des images d'apparence convaincante, mais leur capacité à reproduire fidèlement la distribution globale des images reste encore mal connue. Nous avons introduit une méthode pour évaluer leur capacité de modélisation de la distribution en termes de compression avec perte : l'aptitude à encoder une image avec un nombre de bits bien inférieur à celui nécessaire pour l'encoder exactement. En mesurant la courbe de compromis entre le nombre de bits et l'erreur de reconstruction, on obtient une vision beaucoup plus complète des performances de modélisation de la distribution, comparée aux métriques scalaires traditionnelles.
Compromis fondamentaux entre invariance et sensibilité aux perturbations adverses
Florian Tramer (Université Stanford) · Jens Behrmann (Université de Brême) · Nicholas Carlini (Google) · Nicolas Papernot (Université de Toronto et Vector Institute) · Joern-Henrik Jacobsen (Vector Institute et Université de Toronto)
Nos travaux portaient sur les exemples adverses : dans les tâches de perception, les exemples adverses sont des images perturbées pour induire en erreur un modèle d’apprentissage automatique et l’amener à faire des prédictions incorrectes. La question principale que nous avons posée dans notre article à l'ICML était la suivante : les progrès réalisés dans la lutte contre les recherches sur les exemples adverses se traduisent-ils par des avancées significatives pour la robustesse de l'apprentissage automatique en pratique ? Nous avons montré que ce n’est pas entièrement le cas, car notre définition des exemples adverses repose sur des hypothèses simplificatrices excessives qui exposent les modèles à de nouvelles formes d’attaques.
Généralisation par dérandomisation
Jeffrey Negrea (étudiant de l'U de T, à Vector), Gintare Karolina Dziugaite (Élément AI), Daniel M. Roy
Il existe un écart important entre les performances de l'apprentissage profond observées en pratique et celles prédites par nos meilleures théories. Ce travail démontre comment contourner un obstacle théorique qui semblait rendre inefficaces de nombreux outils standards.
Vérification hiérarchique pour la robustesse face aux attaques adverses *
Cong Han Lim (Uber ATG) · Raquel Urtasun (Uber ATG) · Ersin Yumer (Uber ATG)
Nous introduisons un nouveau cadre pour le problème de vérification exacte de la robustesse ponctuelle `p`, exploitant la structure géométrique par couches des réseaux de neurones profonds à propagation avant avec activations linéaires rectifiées (réseaux ReLU). Les régions d'activation du réseau partitionnent l'espace d'entrée, et la robustesse `p` autour d'un point peut être vérifiée en examinant toutes les régions d'activation dans le rayon souhaité. L'algorithme GeoCert (Jordan et al., 2019) traite cette partition comme un complexe polyédrique générique afin de déterminer la région à examiner ensuite. À l'inverse, notre cadre LayerCert considère la structure d'hyperplans imbriqués induite par les couches du réseau ReLU et explore les régions de manière hiérarchique. Nous démontrons que, sous certaines conditions sur les paramètres de l'algorithme, LayerCert réduit significativement le nombre et la taille des programmes convexes à résoudre par rapport à GeoCert. De plus, notre cadre LayerCert permet l'intégration de routines de borne inférieure basées sur des relaxations convexes afin d'améliorer davantage les performances. Les résultats expérimentaux démontrent que LayerCert peut réduire considérablement à la fois le nombre de programmes convexes résolus et le temps d'exécution par rapport aux méthodes de pointe.
Amélioration des bornes du regret minimax sous perte logarithmique par l'autoconcordance
Blair Bilodeau (Université de Toronto), Dylan Foster (MIT), Daniel Roy (Université de Toronto)
Nous nous intéressons souvent à la prévision d'événements futurs, comme la météo du lendemain ou la performance des marchés boursiers. Dans ce travail, nous progressons de manière significative dans notre compréhension des limites mathématiques de la performance des prévisions.
Amélioration de l'optimisation des transformateurs grâce à une meilleure initialisation *
Xiao Shi Huang (IA de couche 6) · Felipe Perez (IA de couche 6) · Jimmy Ba (Université de Toronto) · Maksims Volkovs (IA de couche 6)
L'architecture Transformer a connu un succès considérable ces dernières années ; son composant clé est la couche d'attention, qui permet au modèle de se concentrer sur les régions importantes d'une séquence d'entrée. L'optimisation du gradient avec les couches d'attention peut s'avérer particulièrement complexe, nécessitant des techniques telles que l'échauffement du taux d'apprentissage pour éviter la divergence. Face à l'augmentation de la taille et du coût d'entraînement des modèles Transformer, les recherches récentes se sont concentrées sur la compréhension et l'amélioration de l'optimisation au sein de ces architectures. Dans ce travail, nos contributions sont doubles : nous étudions et validons empiriquement l'origine des problèmes d'optimisation dans l'architecture Transformer encodeur-décodeur ; nous proposons ensuite un nouveau schéma d'initialisation des poids, justifié théoriquement, qui permet un entraînement sans échauffement ni normalisation des couches. Les résultats empiriques obtenus sur des bases de données publiques de traduction automatique montrent que notre approche atteint une précision remarquable, permettant d'entraîner sans difficulté des modèles Transformer profonds comportant 200 couches dans l'encodeur et le décodeur (plus de 1 000 blocs d'attention/MLP).
Connectivité linéaire et hypothèse du billet de loterie
Jonathan Frankle (MIT), Gintare Karolina Dziugaite (Element AI), Daniel M. Roy (Vector Institute), Michael Carbin (MIT)
Dans ce travail, nous établissons un lien entre deux phénomènes apparemment distincts dans l'entraînement des réseaux de neurones : la connectivité linéaire et l'hypothèse du billet de loterie. Sur des réseaux de vision et des jeux de données de référence standards, nous montrons que des sous-réseaux entraînables clairsemés apparaissent lorsque l'effet du bruit des mini-lots descend en dessous d'un seuil bien défini.
Silviu Pitis (Université de Toronto) · Harris Chan (Université de Toronto, Institut Vector) · Stephen Zhao (Université de Toronto) · Bradly Stadie (Institut Vector) · Jimmy Ba (Université de Toronto)
Nous concevons des robots qui peuvent poursuivre des objectifs en fonction de leur expérience et de leurs compétences. En les orientant vers des situations inédites et peu explorées, nos robots simulés apprennent à naviguer dans des labyrinthes et à manipuler des blocs en un temps record, avec un nombre d'interactions avec l'environnement considérablement réduit par rapport aux approches de pointe précédentes.
Réseau d'itération de valeur de routage multiagents *
Quinlan Sykora (Uber ATG) · Mengye Ren (Uber ATG / Université de Toronto) · Raquel Urtasun (Uber ATG)
Dans cet article, nous abordons le problème du routage coordonné de plusieurs agents. Ce problème complexe trouve de nombreuses applications dans la gestion de flottes pour atteindre un objectif commun, comme la cartographie par essaim de robots et le covoiturage. Les méthodes traditionnelles ne sont généralement pas conçues pour les environnements réalistes, caractérisés par des graphiques peu connectés et un trafic inconnu, et sont souvent trop lentes pour être pratiques. Nous proposons, en revanche, un modèle basé sur un réseau de neurones graphiques capable d'effectuer un routage multi-agents grâce à l'itération de valeurs apprises dans un graphe peu connecté avec des conditions de trafic dynamiques. De plus, notre module de communication appris permet aux agents de se coordonner en temps réel et de s'adapter plus efficacement aux changements. Nous avons créé un environnement simulé pour reproduire la cartographie réelle effectuée par des véhicules autonomes avec une couverture minimale d'arêtes et des conditions de trafic inconnues ; notre approche surpasse de manière significative les solveurs traditionnels, tant en termes de coût total que de temps d'exécution. Nous montrons également que notre modèle, entraîné avec seulement deux agents sur des graphiques comportant au maximum 25 nœuds, peut facilement être généralisé à des situations avec plus d'agents et/ou de nœuds.
Heuristiques de résolution SAT basées sur la correspondance de moments bayésiens en ligne
Haonan Duan (Université de Waterloo) · Saeed Nejati (Université de Waterloo) · George Trimponias (Laboratoire de l'Arche de Noé) · Pascal Poupart (Université de Waterloo et Borealis AI) · Vijay Ganesh (Université de Waterloo, Génie électrique et informatique)
Ce travail décrit une technique d'apprentissage bayésien pour initialiser la recherche d'une solution aux problèmes de satisfaction de contraintes formulés comme des problèmes de satisfaisabilité booléenne. L'approche apprend à satisfaire la plupart des contraintes en une fraction de seconde, ce qui accélère la recherche d'une solution aux problèmes cryptographiques complexes et à d'autres problèmes combinatoires industriels.
Martin Mladenov (Google) · Elliot Creager (Université de Toronto) · Omer Ben-Porat (Technion – Institut de technologie d’Israël) · Kevin Swersky (Google Brain) · Richard Zemel (Vector Institute) · Craig Boutilier (Google)
La plupart des recherches sur les systèmes de recommandation (SR) supposent que l'utilité d'un utilisateur peut être maximisée indépendamment de celle des autres acteurs (autres utilisateurs, fournisseurs de contenu, etc.). En réalité, cette hypothèse est souvent erronée : la dynamique d'un écosystème de SR lie l'utilité à long terme de tous les acteurs. Dans ce travail, nous explorons des contextes où les fournisseurs de contenu ne peuvent rester viables sans un certain niveau d'engagement des utilisateurs. Nous formulons le problème de recommandation dans ce contexte comme un problème de sélection d'équilibre au sein du système dynamique induit, et montrons qu'il peut être résolu comme un problème d'appariement optimal sous contraintes. Notre modèle garantit que le système atteint un équilibre avec un bien-être social maximal, soutenu par un ensemble suffisamment diversifié de fournisseurs viables. Nous démontrons que même dans un modèle de SR dynamique simple et stylisé, l'approche myope standard de la recommandation – qui consiste à toujours associer un utilisateur au meilleur fournisseur – est peu performante. Nous développons plusieurs techniques évolutives pour résoudre le problème d'appariement, et établissons des liens avec diverses notions de regret de l'utilisateur et d'équité, en arguant que ces résultats sont plus justes d'un point de vue utilitariste.
StyleGAN semi-supervisé pour l'apprentissage du démêlage
Weili Nie (Université Rice) · Tero Karras (NVIDIA) · Animesh Garg (Université de Toronto, Vector Institute, Nvidia) · Shoubhik Debnath (Nvidia) · Anjul Patney (Nvidia) · Ankit Patel (Université Rice, Baylor College of Medicine) · Anima Anandkumar (Amazon AI et Caltech)
Les progrès récents en matière de modèles génératifs d'images ont permis d'obtenir des résultats impressionnants. Cependant, la génération reste difficilement contrôlable. La génération contrefactuelle – où l'on souhaite modifier une seule caractéristique de l'image d'entrée – exige un grand nombre d'étiquettes détaillées. Ce problème est appelé désenchevêtrement dans les modèles génératifs. Cela signifie que nous avons besoin d'ensembles de données avec des étiquettes précises telles que « lunettes », « barbe », « couleur des yeux », « sourire » – et ce, uniquement pour les visages. Dans d'autres domaines d'images naturelles, cet espace d'étiquettes peut être encore plus vaste. Ce travail vise à améliorer le désenchevêtrement sans utiliser d'ensembles de données entièrement étiquetés. Nous pouvons obtenir une génération contrefactuelle contrôlable avec seulement 1 % de données étiquetées, contrairement aux autres approches contemporaines qui nécessitent une supervision complète. Les résultats nous permettent ainsi de séparer les facteurs de variation dans l'ensemble de données d'entrée, comme la couleur, la forme, les traits du visage, etc. Grâce à cette séparabilité, nous pouvons maintenant modifier l'entrée pour changer sélectivement n'importe laquelle de ces caractéristiques et imaginer à quoi ressemblerait cette personne avec des lunettes, ou à quoi ressemblerait cette pièce avec un éclairage différent.
Attaques adverses de Wasserstein plus puissantes et plus rapides
Kaiwen Wu (Université de Waterloo) · Allen Wang (Université de Waterloo) · Yaoliang Yu (Université de Waterloo)
Les modèles profonds sont étonnamment vulnérables aux attaques adverses, c'est-à-dire aux perturbations imperceptibles qui modifient radicalement la sortie du réseau, ce qui soulève de sérieuses questions de sécurité concernant les systèmes d'IA. Nous développons deux nouveaux algorithmes permettant de réaliser des attaques adverses plus rapides et plus puissantes, conformément au modèle de menace de Wasserstein. De plus, nous démontrons que nos algorithmes d'attaque, combinés à un entraînement adverse, améliorent considérablement la robustesse des modèles profonds face à ces attaques. Nous espérons que nos outils aideront les praticiens à mieux évaluer la robustesse de leurs modèles et, ultimement, à concevoir des systèmes d'IA plus robustes.
Queues des écoulements triangulaires lipschitziens
Priyank Jaini (Université de Waterloo, Institut Vector) · Ivan Kobyzev (Borealis AI) · Yaoliang Yu (Université de Waterloo) · Marcus Brubaker (Borealis AI)
La distribution d'objets réels (comme des visages humains ou des documents rédigés en anglais) peut être apprise en « déformant » une distribution a priori fixe par des transformations triangulaires multicouches. De nouveaux objets peuvent ensuite être facilement synthétisés et intégrés à divers algorithmes et applications d'apprentissage. Nous étudions comment la queue de distribution (c'est-à-dire les valeurs extrêmes) peut évoluer ou non de manière adéquate à travers les architectures existantes de flux triangulaires. En conséquence, nous proposons un modèle de flux adaptatif à la queue de distribution, capable d'adapter plus efficacement les modèles de flux existants aux distributions cibles à queue épaisse, telles que celles couramment utilisées pour modéliser les risques financiers et les valeurs extrêmes.
Affiliés de la faculté Vector
Certification et apprentissage en boîte noire sous perturbations adverses *
Hassan Ashtiani (Université McMaster) · Vinayak Pathak (Scotiabank) · Ruth Urner (Université York)
Nous étudions formellement le problème de la classification sous perturbations adverses, tant du point de vue de l'apprenant que de celui d'un tiers visant à certifier la robustesse d'un classificateur de boîte noire donné. Nous analysons un cadre d'apprentissage semi-supervisé de type PAC et identifions des résultats de possibilité et d'impossibilité pour un apprentissage correct des classes CV dans ce contexte. Nous présentons et étudions également un nouveau cadre de certification boîte noire avec un budget de requêtes limité. Nous l'analysons pour différentes classes de prédicteurs et différents types de perturbations. Nous considérons également le point de vue d'un adversaire boîte noire cherchant à trouver des exemples adverses, et montrons que l'existence d'un tel adversaire, dont la complexité de requêtes est polynomiale, implique l'existence d'un apprenant robuste, dont la complexité d'échantillonnage est faible.
Intégrations de graphiques plus rapides grâce au grossissement *
Matthew Fahrbach (Georgia Institute of Technology) · Gramoz Goranci (Université de Toronto) · Sushant Sachdeva (Université de Toronto) · Richard Peng (Georgia Tech / MSR Redmond) · Chi Wang (Microsoft Research)
Les plongements de graphes sont un outil omniprésent pour les tâches d'apprentissage machine, telles que la classification de nœuds et la prédiction de liens, sur des données structurées en graphes. Cependant, le calcul des plongements pour les graphes de grande taille est extrêmement inefficace, même si l'on ne s'intéresse qu'à un petit sous-ensemble de sommets pertinents. Pour remédier à ce problème, nous présentons une approche efficace de réduction de graphe, basée sur les compléments de Schur, pour calculer le plongement des sommets pertinents. Nous démontrons que ces plongements sont exactement préservés par le graphe du complément de Schur obtenu par élimination de Gauss sur les sommets non pertinents. Comme le calcul des compléments de Schur est coûteux, nous proposons un algorithme quasi linéaire qui génère un graphe réduit sur les sommets pertinents, dont l'espérance est garantie à chaque itération par rapport au complément de Schur. Nos expériences, portant sur des tâches de prédiction sur des graphes, montrent que le calcul des plongements sur le graphe réduit, plutôt que sur le graphe entier, permet un gain de temps significatif sans perte de précision.
Arbres de décision clairsemés optimaux généralisés et évolutifs *
Jimmy Lin (Université de la Colombie-Britannique) · Chudi Zhong (Université Duke) · Diane Hu (Université Duke) · Cynthia Rudin (Université Duke) · Margo Seltzer (Université de la Colombie-Britannique)
L'optimisation des arbres de décision est réputée pour sa complexité computationnelle, mais essentielle dans le domaine de l'apprentissage automatique interprétable. Malgré les efforts déployés ces 40 dernières années, ce n'est que récemment que des percées majeures ont permis à des algorithmes pratiques de trouver des arbres de décision optimaux. Ces nouvelles techniques ont le potentiel d'induire un changement de paradigme, permettant de construire des arbres de décision clairsemés pour optimiser efficacement diverses fonctions objectives sans recourir à des heuristiques gloutonnes de division et d'élagage, souvent sources de solutions sous-optimales. La contribution de ce travail est de fournir un cadre général pour l'optimisation des arbres de décision, qui aborde les deux principaux problèmes ouverts dans ce domaine : le traitement des données déséquilibrées et l'optimisation complète sur des variables continues. Nous présentons des techniques qui produisent des arbres de décision optimaux pour diverses fonctions objectives, notamment le score F, l'AUC et l'aire partielle sous l'enveloppe convexe ROC. Nous introduisons également un algorithme évolutif qui produit des résultats optimaux prouvés en présence de variables continues et accélère la construction des arbres de décision de plusieurs ordres de grandeur par rapport à l'état de l'art.
Publication de requêtes privées assistée par des données publiques *
Raef Bassily (Université d'État de l'Ohio) · Albert Cheu (Université Northeastern) · Shay Moran (IAS, Princeton) · Aleksandar Nikolov (Université de Toronto) · Jonathan Ullman (Université Northeastern) · Steven Wu (Université du Minnesota)
Nous étudions le problème de la publication de requêtes différentiellement privées, facilitée par l'accès à des données publiques. L'objectif est de répondre à une large classe de requêtes statistiques avec une erreur inférieure ou égale à α, en utilisant une combinaison d'échantillons publics et privés. L'algorithme doit garantir la confidentialité différentielle uniquement par rapport aux échantillons privés. Nous étudions les limites de cette tâche en fonction de la complexité des échantillons privés et publics.
Nous montrons d'abord que le problème peut être résolu pour toute classe de requêtes de dimension VC finie en utilisant seulement d/α échantillons publics et p‾√d³/²/α² échantillons privés, où d et p représentent respectivement la dimension VC et sa duale. En comparaison, avec seulement des échantillons privés, ce problème ne peut être résolu, même pour des classes de requêtes simples de dimension VC égale à un, et sans aucun échantillon privé, un échantillon public plus important, de taille d/α², est nécessaire. Ensuite, nous établissons des bornes inférieures de la complexité d'échantillonnage qui présentent une forte dépendance à p et α. Pour la classe des souches de décision, nous donnons une borne inférieure de p‾√/α sur la complexité d'échantillonnage privée lorsque la taille de l'échantillon public est inférieure à 1/α². Compte tenu de nos bornes supérieures, cela démontre que la dépendance à p‾√ est nécessaire pour la complexité d'échantillonnage privée. Nous donnons également une borne inférieure de 1/α sur la complexité de l'échantillon public pour une large famille de classes de requêtes, qui, selon notre borne supérieure, est serrée en α.
Convolutions à gros noyau sensibles au temps *
Vasileios Lioutas (Université Carleton) · Yuhong Guo (Université Carleton)
À ce jour, la plupart des architectures de modélisation de séquences de pointe utilisent l'attention pour construire des modèles génératifs destinés aux tâches linguistiques. Certains de ces modèles exploitent tous les jetons de la séquence disponibles pour générer une distribution d'attention, ce qui induit une complexité temporelle de O(n²). D'autres utilisent des convolutions en profondeur avec des noyaux normalisés softmax de taille k, agissant comme une auto-attention à fenêtre limitée, ce qui mène à une complexité temporelle de O(k⋅n). Dans cet article, nous introduisons les convolutions à gros noyau sensibles au temps (TaLK), une nouvelle opération de convolution adaptative qui apprend à prédire la taille d'un noyau de sommation au lieu d'utiliser une matrice de noyau de taille fixe. Cette méthode permet d'obtenir une complexité temporelle de O(n), rendant ainsi le processus d'encodage de séquences linéaire par rapport au nombre de jetons. Nous évaluons la méthode proposée sur des ensembles de données à grande échelle de traduction automatique standard, de résumé abstrait et de modélisation du langage, et montrons que les convolutions TaLK constituent une amélioration significative par rapport aux autres approches basées sur l'attention/convolution.
