7 juillet 2020
L’édition de cette année de la Conférence internationale sur l’apprentissage automatique (ICML) sera virtuelle, se déroulant du dimanche 13 juillet au samedi 18 juillet.
L’ICML est l’une des principales conférences mondiales sur l’apprentissage automatique, comme en témoigne le volume massif d’articles sur l’apprentissage automatique soumis. Cette année, la conférence a accepté 1 088 articles sur 4 990 soumissions, soit un taux d’acceptation de 21,8% (en baisse par rapport à 22,6% en 2019). Les membres du corps professoral de Vector ont vu 19 articles acceptés, avec cinq autres provenant d’affiliés du corps professoral de Vector. Dans leur ensemble, les articles liés à Vector représentent 2,21% du nombre total d’articles acceptés à l’ICML 2020.
Voici des résumés en langage simple de certains des travaux que les chercheurs de Vector présenteront lors de l’édition de cette année de la conférence. Celles marquées d’un * indiquent le résumé original de l’article.
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 d’images offrent des performances impressionnantes, mais souffrent souvent d’une mauvaise calibration. Ils ont tendance à être trop confiants, la confiance du modèle ne reflétant pas toujours l’ambiguïté réelle et la dureté sous-jacentes des points de données. Nous proposons une nouvelle méthode pour mesurer la dureté des points de données, une méthode que nous appelons la dureté visuelle angulaire — étant donné une image particulière, à quel point est-il difficile pour un modèle d’apprentissage automatique de savoir s’il s’agit d’un petit pain à la cannelle ou d’un chiot recroquevillé?! Nous avons aussi constaté que l’AVH présente une corrélation statistiquement significative avec la dureté visuelle humaine, donc les gens trouvent ces problèmes 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 qui peuvent être plus équitables dans la prise de décision avec des ensembles de données déséquilibrés. L’alignement de l’entraînement avec cette mesure de dureté permet aussi une meilleure généralisation des changements dans 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 (ML) avec des préoccupations d’équité, les données disponibles sont souvent « manquantes et non au hasard » en raison de biais dans la politique historique utilisée pour la prise de décision. Dans le domaine du prêt, par exemple, la véritable solvabilité d’un demandeur est inconnue à moins qu’un prêt ne soit offert, donc si une population de demandeurs s’est vue offrir moins de prêts selon la politique historique, cette population sera « rare en données » dans l’ensemble de données résultant. Nous étudions l’équité à long terme de la prise de décision en apprentissage automatique et montrons que des articles récents issus de cette littérature peuvent être redéfinis comme des modèles causals. Ce paradigme de modélisation convient mieux aux problèmes où les données manquent et non au hasard, et permet l’utilisation d’outils issus de la littérature sur l’inférence causale pour améliorer l’estimation de la performance des politiques futures sur des populations rares en données, améliorant ainsi 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 posture 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) a été la clé pour apprendre les algorithmes afin de gérer l’énorme quantité de variations d’objets réels. Nous développons un cadre de régularisation basé sur des produits semi-internes pour induire un large ensemble d’invariances généralisées qui vont au-delà des espaces de Hilbert classiques à noyau reproducteur. Nous fournissons des implémentations efficaces basées sur des embeddings euclidiens et démontrons l’efficacité de notre algorithme en augmentation des données et en prédiction multilabel structurée.
Éliminer l’intermédiaire : entraîner et évaluer des modèles basés sur l’énergie sans échantillonnage
Will Grathwohl (Université de Toronto) · Kuan-Chieh Wang (Université de Toronto) · Joern-Henrik Jacobsen (Institut des Vecteurs et Université de Toronto) · David Duvenaud (Université de Toronto) · Richard Zemel (Institut Vector)
Si nous voulons faire des prédictions basées sur un ensemble de données, nous devons ajuster un modèle qui indique la probabilité de différentes prédictions. L’ajustement de ce modèle implique de comparer les prédictions aux données originales. Comme il existe une infinité de prédictions possibles, il peut être difficile de quantifier la différence entre toutes les prédictions possibles que le modèle pourrait faire et les données. Notre article propose d’utiliser un réseau de neurones pour apprendre la différence entre les prédictions du modèle et les données. Une fois que nous avons ajusté ce réseau, nous pouvons ajuster les prédictions du modèle pour réduire cette différence.
Détection des exemples hors distribution avec des matrices de Gram
Chandramouli Shama Sastry (Université Dalhousie/Institut Vector) · Sageev Oore (Université Dalhousie et Vector Institute)
Les réseaux neuronaux « ne savent pas ce qu’ils ne savent pas » : un classificateur de lésion cutanée précis pourrait non seulement classer une image de chien comme un type particulier de lésion, mais aussi le faire avec beaucoup d’assurance. Cela arrive parce que les chiens constituent un type (c’est-à-dire une distribution) d’image différente de tout ce que le réseau a vu pendant l’entraînement. L’un des aspects difficiles en pratique est que le réseau ne peut pas s’y préparer à l’avance (c’est-à-dire qu’il ne peut pas voir tous les types d’images possibles qu’il pourrait voir lors du déploiement!). Cette recherche permet d’obtenir des résultats de pointe pour détecter lorsqu’un type d’image inconnu est présenté. Notre algorithme le fait en remarquant des motifs 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 crédantes, mais nous ne savons toujours pas à quel point ils correspondent à la distribution globale des images. Nous avons introduit une méthode pour évaluer leur capacité de modélisation de distribution en termes de compression avec perte : la capacité d’encoder une image en utilisant un nombre beaucoup plus restreint de bits que ce qu’il faudrait pour l’encoder exactement. En mesurant la courbe de compromis entre le nombre de bits et l’erreur de reconstruction, on obtient une image beaucoup plus complète de la performance de la modélisation de distribution, comparativement aux métriques traditionnelles à valeurs scalaires.
Compromis fondamentaux entre invariance et sensibilité aux perturbations adversaires
Florian Tramer (Université Stanford) · Jens Behrmann (Université de Brême) · Nicholas Carlini (Google) · Nicolas Papernot (Université de Toronto et Vector Institute) · Joern-Henrik Jacobsen (Institut Vector et Université de Toronto)
Notre travail portait sur des exemples adversariaux : dans les tâches de perception, les exemples adversariaux sont des images perturbées pour induire un modèle d’apprentissage automatique en erreur afin qu’il fasse de mauvaises prédictions. La principale question que nous avons posée dans notre article de l’ICML était : les progrès que nous réalisons dans la défense contre la recherche par exemple adversaire mènent-ils à des progrès significatifs pour la robustesse de l’apprentissage automatique en pratique? Nous avons montré que ce n’est pas entièrement le cas à cause de la façon dont nous définissons les exemples adverses, qui fait des hypothèses trop simplifiantes, exposant ainsi les modèles à de nouvelles formes d’attaques.
Généralisation par dérandomisation
Jeffrey Negrea (étudiant à l’Université de Toronto, chez Vector), Gintare Karolina Dziugaite (Element AI), Daniel M. Roy
Il existe un grand écart entre la performance de l’apprentissage profond que nous observons en pratique et celle prédite par nos meilleures théories. Ce travail démontre comment contourner un obstacle théorique qui semblait rendre de nombreux outils standards inefficaces.
Vérification hiérarchique de la robustesse adversaire*
Cong Han Lim (Uber ATG) · Raquel Urtasun (Uber ATG) · Ersin Yumer (Uber ATG)
Nous introduisons un nouveau cadre pour le problème exact de vérification de robustesse point par point « p » qui exploite la structure géométrique couche par couche des réseaux en avance profonde avec activations linéaires rectifiées (réseaux ReLU). Les régions d’activation du réseau partitionnent l’espace d’entrée, et on peut vérifier la robustesse 'p autour d’un point en vérifiant toutes les régions d’activation dans le rayon désiré. L’algorithme GeoCert (Jordan et al., 2019) traite cette partition comme un complexe polyédrique générique afin de détecter la région à vérifier ensuite. En revanche, notre cadre LayerCert considère la structure d’arrangement des hyperplans imbriqués induite par les couches du réseau ReLU et explore les régions de manière hiérarchique. Nous montrons que, sous certaines conditions sur les paramètres de l’algorithme, LayerCert réduit de manière démontrable le nombre et la taille des programmes convexes à résoudre comparé à GeoCert. De plus, notre cadre LayerCert permet d’intégrer des routines de limite inférieure basées sur des relaxations convexes pour améliorer encore la performance. Les résultats expérimentaux démontrent que LayerCert peut réduire significativement à la fois le nombre de programmes convexes résolus et le temps d’exécution à la fine pointe.
Limites améliorées du regret Minimax sous perte logarithmique via l’auto-concordance
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 au fil du temps, comme la météo du lendemain ou la performance boursière. Dans ce travail, nous réalisons des avancées significatives dans notre compréhension des limites mathématiques de la performance en prévision.
Amélioration de l’optimisation des transformateurs grâce à une meilleure initialisation*
Xiao Shi Huang (IA de couche 6) · Felipe Perez (IA de couche6) · Jimmy Ba (Université de Toronto) · Maksims Volkovs (IA de couche 6)
L’architecture Transformer a connu un succès considérable récemment; le composant clé du Transformer 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 des couches d’attention peut être notoirement difficile, nécessitant des astuces comme apprendre le réchauffement du taux pour éviter la divergence. À mesure que les modèles Transformer deviennent plus gros et plus coûteux à entraîner, des recherches récentes se sont concentrées sur la compréhension et l’amélioration de l’optimisation dans ces architectures. Dans ce travail, nos contributions sont doubles : nous étudions d’abord et validons empiriquement la source des problèmes d’optimisation dans l’architecture encodeur-décodeur Transformer; Nous proposons ensuite un nouveau schéma d’initialisation des poids avec justification théorique, qui permet l’entraînement sans échauffement ni normalisation des couches. Des résultats empiriques sur des benchmarks publics de traduction automatique montrent que notre approche atteint une précision de pointe, permettant d’entraîner sans difficulté des modèles Transformer profonds avec 200 couches dans l’encodeur et le décodeur (plus de 1000 blocs attention/MLP).
Connectivité en mode 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 relions deux phénomènes apparemment distincts dans l’entraînement des réseaux neuronaux : la connectivité des modes linéaires et l’hypothèse du billet de loterie. Sur les réseaux à vision standard et les benchmarks, nous montrons que des sous-réseaux entraînables clairsemés apparaissent lorsque l’effet du bruit minibatch descend en dessous d’un niveau bien défini.
Silviu Pitis (Université de Toronto) · Harris Chan (Université de Toronto, Vector Institute) · Stephen Zhao (Université de Toronto) · Bradly Stadie (Institut Vector) · Jimmy Ba (Université de Toronto)
Nous concevons des robots à la recherche d’objectifs qui fixent et poursuivent des objectifs selon leur propre expérience et leurs capacités passées. En se fixant des objectifs qui les poussent à des situations peu explorées et nouvelles, nos robots simulés apprennent à naviguer dans les labyrinthes et à manipuler des blocs en un temps record, avec seulement une fraction des interactions environnementales utilisées par les approches de pointe précédentes.
Réseau d’itérations de valeurs de routage multi-agents*
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. C’est un problème complexe qui a de nombreuses applications en gestion de flotte pour atteindre un objectif commun, comme la cartographie à partir d’un essaim de robots et le covoiturage. Les méthodes traditionnelles ne sont généralement pas conçues pour des environnements réalistes qui contiennent des graphes peu connectés et un trafic inconnu, et sont souvent trop lentes en temps d’exécution pour être pratiques. En revanche, nous proposons un modèle basé sur un réseau de neurones de graphes capable d’effectuer un routage multi-agents basé sur l’itération de valeurs apprise dans un graphe peu connecté avec des conditions de circulation dynamiquement changeantes. De plus, notre module de communication appris permet aux agents de coordonner en ligne et de s’adapter plus efficacement aux changements. Nous avons créé un environnement simulé pour imiter une cartographie réaliste réalisée par des véhicules autonomes avec une couverture minimale des bords et des conditions de circulation inconnues; Notre approche surpasse nettement les solveurs traditionnels, tant en coût total qu’en temps d’exécution. Nous montrons aussi que notre modèle entraîné avec seulement deux agents sur des graphes d’un maximum de 25 nœuds peut facilement se généraliser à des situations avec plus d’agents et/ou de nœuds.
Heuristiques de solutions SAT basées sur le jumelage de moments bayésiens en ligne
Haonan Duan (Université de Waterloo) · Saeed Nejati (Université de Waterloo) · George Trimponias (Le labo 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ésienne visant à initialiser la recherche d’une solution aux problèmes de satisfaction de contraintes formulée comme la 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 dans les problèmes cryptographiques difficiles et autres problèmes combinatoires industriels
Martin Mladenov (Google) · Elliot Creager (Université de Toronto) · Omer Ben-Porat (Technion–Institut israélien de technologie) · Kevin Swersky (Google Brain) · Richard Zemel (Institut Vector) · Craig Boutilier (Google)
La plupart des recherches sur les systèmes de recommandation (RS) supposent que l’utilité d’un utilisateur peut être maximisée indépendamment de celle des autres agents (par exemple, autres utilisateurs, fournisseurs de contenu). Dans des contextes réalistes, cela n’est souvent pas vrai — la dynamique d’un écosystème RS couple l’utilité à long terme de tous les agents. Dans ce travail, nous explorons les contextes où les fournisseurs de contenu ne peuvent rester viables que s’ils bénéficient d’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 dans le système dynamique induit, et montrons qu’il peut être résolu comme un problème d’appariement contraint optimal. 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 RS dynamique simple et stylisé, l’approche standard myope de la recommandation — toujours faire correspondre un utilisateur au meilleur fournisseur — fonctionne mal. Nous développons plusieurs techniques évolutives pour résoudre le problème d’appariement, et établissons aussi des liens avec différentes notions de regret et d’équité de l’utilisateur, en soutenant que ces résultats sont plus équitables dans un sens utilitariste.
StyleGAN semi-supervisé pour l’apprentissage par démêlement
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, Collège de médecine Baylor) · Anima Anandkumar (Amazon IA & Caltech)
Les progrès récents dans les modèles génératifs pour les images ont donné des résultats impressionnants. Cependant, la génération n’est pas contrôlable. La génération contrefactuelle — où l’on veut changer une seule caractéristique de l’image d’entrée — nécessite de grandes notices au niveau des caractéristiques. Ce problème s’appelle le désentremêlement dans les modèles génératifs. Cela signifie que nous avons besoin de jeux de données avec des étiquettes détaillées telles que lunettes, barbe, eye_color, sourire — et cela concerne uniquement les visages. Dans d’autres domaines d’image naturels, cet espace d’étiquettes peut être encore plus grand. Ce travail vise à améliorer le démêlement sans recourir à des ensembles de données entièrement étiquetés. Nous pouvons obtenir une génération contrafactuelle contrôlable avec seulement 1% de données étiquetées, comparativement à d’autres approches contemporaines qui nécessitent une supervision complète. Les résultats nous permettent ainsi de distinguer les facteurs de variation dans les ensembles d’entrées comme la couleur, la forme, les traits du visage, etc. Et grâce à cette séparabilité, nous pouvons maintenant modifier l’entrée pour modifier ces caractéristiques de façon sélective, afin d’imaginer à quoi ressemblerait cette personne avec des lunettes, ou à quoi ressemblerait cette pièce avec un éclairage différent.
Attaques adversaires Wasserstein plus fortes 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 des perturbations imperceptibles qui modifient complètement la production du réseau, soulevant de sérieuses préoccupations de sécurité sur les systèmes d’IA. Nous développons deux nouveaux algorithmes pour effectuer des attaques adversaires plus rapides et plus puissantes dans le cadre du récent modèle de menace de Wasserstein. De plus, nous démontrons que nos algorithmes d’attaque, combinés à l’entraînement adversaire, améliorent grandement la robustesse des modèles profonds face aux attaques adverses. Nous nous attendons à ce que nos outils aident les praticiens à mieux évaluer la robustesse de leur modèle et, éventuellement, à construire des systèmes d’IA plus robustes.
Queues des coulées triangulaires de Lipschitz
Priyank Jaini (Université de Waterloo, Institut Vector) · Ivan Kobyzev (Borealis AI) · Yaoliang Yu (Université de Waterloo) · Marcus Brubaker (IA Borealis)
La distribution des objets réels (comme des visages humains ou des documents écrits en anglais) peut être apprise en « déformant » une distribution a priori fixe via des transformations triangulaires à plusieurs couches, après quoi de nouveaux objets peuvent être facilement synthétisés et intégrés dans divers algorithmes et applications d’apprentissage. Nous étudions comment la queue (c’est-à-dire les objets extrêmes) d’une distribution peut ou ne peut pas changer adéquatement à travers des architectures existantes dans des flux triangulaires. Par conséquent, nous proposons un modèle d’écoulement adaptatif à la queue qui peut mieux adapter les modèles existants aux distributions cibles à queues lourdes, comme celles couramment utilisées pour modéliser les risques financiers et les valeurs extrêmes.
Affiliés du corps professoral Vector
Certification boîte noire et apprentissage sous perturbations adversariales*
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 du point de vue d’un tiers qui cherche à certifier la robustesse d’un classificateur boîte noire donné. Nous analysons un cadre de type PAC d’apprentissage semi-supervisé et identifions des résultats de possibilités et d’impossibilités pour un apprentissage approprié des classes de VC dans ce contexte. Nous introduisons et étudions également un nouveau cadre de certification boîte noire avec un budget de requête limité. Nous analysons cela pour différentes classes de prédicteurs et types de perturbations. Nous considérons également le point de vue d’un adversaire boîte noire qui vise à trouver des exemples adverses, montrant que l’existence d’un adversaire à complexité de requête polynomiale implique l’existence d’un apprenant robuste avec une petite complexité d’échantillon.
Plongements de graphes plus rapides via grossissement*
Matthew Fahrbach (Institut de technologie de Géorgie) · Gramoz Goranci (Université de Toronto) · Sushant Sachdeva (Université de Toronto) · Richard Peng (Georgia Tech / MSR Redmond) · Chi Wang (Microsoft Research)
Les embeddings de graphes sont un outil omniprésent pour les tâches d’apprentissage automatique, telles que la classification des nœuds et la prédiction des liens, sur des données structurées en graphes. Cependant, calculer les plongements pour les graphes à grande échelle est prohibitivement inefficace, même si nous ne nous intéressons qu’à un petit sous-ensemble de sommets pertinents. Pour y remédier, nous présentons une approche efficace de grossissement des graphes, basée sur les compléments de Schur, pour calculer l’immersion des sommets pertinents. Nous démontrons que ces plongements sont préservés exactement par le graphe complémentaire de Schur obtenu par élimination gaussienne sur les sommets non pertinents. Comme le calcul des compléments de Schur est coûteux, nous donnons un algorithme en temps quasi linéaire qui génère un graphe grossier sur les sommets pertinents qui correspond de manière démontrable au complément de Schur en espérance à chaque itération. Nos expériences impliquant des tâches de prédiction sur les graphes démontrent que le calcul des embeddings sur le graphe grossier, plutôt que sur l’ensemble du graphe, entraîne des gains de temps significatifs sans sacrifier la 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 (duc) · Margo Seltzer (Université de la Colombie-Britannique)
L’optimisation par arbre de décision est notoirement difficile d’un point de vue computationnel, mais essentielle dans le domaine de l’apprentissage automatique interprétable. Malgré les efforts des 40 dernières années, ce n’est que récemment que des avancées en optimisation ont été réalisées permettant aux algorithmes pratiques de trouver des arbres de décision optimaux. Ces nouvelles techniques ont le potentiel de déclencher un changement de paradigme où il est possible de construire des arbres de décision clairsemés pour optimiser efficacement une variété de fonctions objectifs sans dépendre de découpes et d’heuristiques d’élagage avides qui mènent souvent à des solutions sous-optimales. La contribution à ce travail est de fournir un cadre général pour l’optimisation des arbres de décision qui aborde deux problèmes majeurs ouverts dans le 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 sur une variété d’objectifs, incluant le score F, l’AUC et une zone partielle sous l’enveloppe convexe ROC. Nous introduisons également un algorithme évolutif qui produit des résultats prouvement optimaux en présence de variables continues et accélère la construction de l’arbre de décision de plusieurs ordres de grandeur par rapport à l’état de la technologie.
Libération privée de requêtes assistée par des données publiques*
Raef Bassily (Université d’État de l’Ohio) · Albert Cheu (Université du Nord-Est) · 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 libération de requêtes différenciément privées, assistée par l’accès aux données publiques. Dans ce problème, l’objectif est de répondre à une grande catégorie de requêtes statistiques avec une erreur d’au plus α en utilisant une combinaison d’échantillons publics et privés. L’algorithme doit satisfaire à la confidentialité différentielle uniquement en ce qui concerne les échantillons privés. Nous étudions les limites de cette tâche en termes de complexité des échantillons privés et publics.
Premièrement, nous montrons que nous pouvons résoudre le problème pour toute classe de requête ��� de dimension VC finie en utilisant seulement d/α échantillons publics et p ̅√d3/2/α2 échantillons privés, où d et p sont respectivement la dimension VC et la dimension VC duale de ψ�. En comparaison, avec seulement des échantillons privés, ce problème ne peut être résolu même pour des classes de requête simples de dimension VC un, et sans échantillons privés, un échantillon public plus large de taille d/α2 est nécessaire. Ensuite, nous donnons des bornes inférieures à la complexité de l’échantillon qui présentent une dépendance étroite entre p et α. Pour la classe des souches décisionnelles, nous donnons une borne inférieure de p ̅√/α sur la complexité de l’échantillon privé chaque fois que la taille publique de l’échantillon est inférieure à 1/α2. Étant donné nos bornes supérieures, cela montre que la dépendance à p̅√ est nécessaire dans la complexité de l’échantillon privé. Nous donnons aussi une borne inférieure de 1/α sur la complexité publique de l’échantillon pour une large famille de classes de requêtes, qui, selon notre borne supérieure, est serrée en α.
Convolutions de 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 pour des tâches axées sur le langage. Certains de ces modèles utilisent tous les jetons de séquence disponibles pour générer une distribution d’attention qui aboutit à une complexité temporelle de O(n2). Alternativement, ils 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 donne une complexité temporelle de O(k⋅n). Dans cet article, nous introduisons les convolutions Time-conscious Large Kernel (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 donne une complexité temporelle de O(n), rendant effectivement 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 de traduction automatique standard à grande échelle, de synthèse abstraite et de modélisation du langage, et montrons que les convolutions TaLK constituent une amélioration efficace par rapport à d’autres approches basées sur l’attention/la convolution.
