Internet ainsi que tous les moyens numériques modernes disponibles pour communiquer, s'informer ou se divertir génèrent des données en quantités de plus en plus importantes. Dans des domaines aussi variés que la recherche d'information, la bio-informatique, la linguistique computationnelle ou la sécurité numérique, des méthodes automatiques capables d'organiser, classifier, ou transformer des téraoctets de données apportent une aide précieuse. L'apprentissage artificiel traite de la conception d'algorithmes qui permettent d'entraîner de tels outils à l'aide d'exemples d'apprentissage. Utiliser certaines de ces méthodes pour automatiser le traitement de problèmes complexes, en particulier quand les quantités de données en jeu sont insurmontables pour des opérateurs humains, paraît inévitable. Malheureusement, la plupart des algorithmes d'apprentissage actuels, bien qu'efficaces sur de petites bases de données, présentent une complexité importante qui les rend inutilisables sur de trop grandes masses de données. Ainsi, il existe un besoin certain dans la communauté de l'apprentissage artificiel pour des méthodes capables d'être entraînées sur des ensembles d'apprentissage de grande échelle, et pouvant ainsi gérer les quantités colossales d'informations générées quotidiennement. Nous développons ces enjeux et défis dans le Chapitre 1. Dans ce manuscrit, nous proposons des solutions pour réduire le temps d'entraînement et les besoins en mémoire d'algorithmes d'apprentissage sans pour autant dégrader leur précision. Nous nous intéressons en particulier aux Machines à Vecteurs Supports (SVMs), des méthodes populaires utilisées en général pour des tâches de classification automatique mais qui peuvent être adaptées à d'autres applications. Nous décrivons les SVMs en détail dans le Chapitre 2. Ensuite, dans le Chapitre 3, nous étudions le processus d'apprentissage par descente de gradient stochastique pour les SVMs linéaires. Cela nous amène à définir et étudier le nouvel algorithme, SGD-QN. Après cela, nous introduisons une nouvelle procédure d'apprentissage : le principe du “Process/Reprocess”. Nous déclinons alors trois algorithmes qui l'utilisent. Le Huller et LaSVM sont présentés dans le Chapitre 4. Ils servent à apprendre des SVMs destinés à traiter des problèmes de classification binaire (décision entre deux classes). Pour la tˆache plus complexe de prédiction de sorties structurées, nous modifions par la suite en profondeur l'algorithme LaSVM, ce qui conduit à l'algorithme LaRank présenté dans le Chapitre 5. Notre dernière contribution concerne le problème récent de l'apprentissage avec une supervision ambigüe pour lequel nous proposons un nouveau cadre théorique (et un algorithme associé) dans le Chapitre 6. Nous l'appliquons alors au problème de l'étiquetage sémantique du langage naturel. Tous les algorithmes introduits dans cette thèse atteignent les performances de l'état-de-l'art, en particulier en ce qui concerne les vitesses d'entraînement. La plupart d'entre eux ont été publiés dans des journaux ou actes de conférences internationaux. Des implantations efficaces de chaque méthode ont également été rendues disponibles. Dans la mesure du possible, nous décrivons nos nouveaux algorithmes de la manière la plus générale possible afin de faciliter leur application à des tâches nouvelles. Nous esquissons certaines d'entre elles dans le Chapitre 7.