Objective non-intrusive speech quality assessment aimed to emulate and correlate with human judgement has received more attention over the years. It is a difficult problem due to three reasons: data scarcity, noisy human judgement, and a potential uneven distribution of bias of mean opinion scores (MOS). In this paper, we introduce the Latent Mean-Opinion-Score Network (LaMOSNet) that leverage on individual judge’s scores to increase the data size, and new ideas to deal with both noisy and biased labels. We introduce a methodology called Optimistic Judge Estimation as a way to reduce bias in MOS in a clear way. We also implement stochastic gradient noise and mean teacher, ideas from noisy image classification, to further deal with noisy and uneven bias distribution of labels. We achieve competitive results on VCC2018 modeling MOS, and state-of-the-art modeling only listener dependent scores. / Objektiv referensfri ljudkvalitétsbedömning ämnad att härma och korrelera med mänsklig bedömning har fått mer uppmärksamhet med åren. Det är ett svårt problem på grund av tre anledningar: brist på data, varians i mänsklig bedömning, och en potentiell ojämn fördelning av bias av medel bedömningsvärde (mean opinion score, MOS). I detta papper introducerar vi Latent Mean-Opinion-Score Network (LaMOSNet) som tar nytta av individuella bedömmares poäng för att öka datastorleken, och nya idéer för att handskas med både varierande och partisk märkning. Jag introducerar en metodologi som kallas Optimistisk bedömmarestimering, ett sätt att minska partiskheten i MOS på ett klart sätt. Jag implementerar också stokastisk gradient variation och medellärare, idéer från opålitlig bild igenkänning, för att ännu mer hantera opålitliga märkningar. Jag får jämförelsebara resultat på VCC2018 när jag modellerar MOS, och state-of-the-art när jag modellerar enbart beömmarnas märkning.

<p dir="ltr">Advancements in machine learning, especially deep learning, have facilitated the creation of models capable of performing tasks previously thought impossible. This progress has opened new possibilities across diverse fields such as medical imaging and remote sensing. However, the performance of these models relies heavily on the availability of extensive labeled datasets.<br>Collecting large amounts of labeled data poses a significant financial burden, particularly in specialized fields like medical imaging and remote sensing, where annotation requires expert knowledge. To address this challenge, various methods have been developed to mitigate the necessity for labeled data or leverage information contained in unlabeled data. These encompass include self-supervised learning, few-shot learning, and semi-supervised learning. This dissertation centers on the application of semi-supervised learning in segmentation tasks.<br><br>We focus on panoptic segmentation, a task that combines semantic segmentation (assigning a class to each pixel) and instance segmentation (grouping pixels into different object instances). We choose two segmentation tasks in different domains: nerve segmentation in microscopic imaging and hyperspectral segmentation in satellite images from Mars.<br>Our study reveals that, while direct application of methods developed for natural images may yield low performance, targeted modifications or the development of robust models can provide satisfactory results, thereby unlocking new applications like machine-assisted annotation of new data.<br><br>This dissertation begins with a challenging panoptic segmentation problem in microscopic imaging, systematically exploring model architectures to improve generalization. Subsequently, it investigates how semi-supervised learning may mitigate the need for annotated data. It then moves to hyperspectral imaging, introducing a Hierarchical Bayesian model (HBM) to robustly classify single pixels. Key contributions of include developing a state-of-the-art U-Net model for nerve segmentation, improving the model's ability to segment different cellular structures, evaluating semi-supervised learning methods in the same setting, and proposing HBM for hyperspectral segmentation. <br>The dissertation also provides a dataset of labeled CRISM pixels and mineral detections, and a software toolbox implementing the full HBM pipeline, to facilitate the development of new models.</p>

Recent increase in widespread use of facial recognition technologies have accelerated the utilization of demographic information, as extracted from facial features, yet it is accompanied by ethical concerns. It is therefore crucial, for ethical reasons, to ensure that algorithms like face recognition algorithms employed in legal proceedings are equitable and thoroughly documented across diverse populations. Accurate classification of demographic traits are therefore essential for enabling a comprehensive understanding of other algorithms. This thesis explores how classical machine learning algorithms compare to deep-learning models in predicting sex, age and skin color, concluding that the more compute-heavy deep-learning models, where the best performing models achieved an MCC of 0.99, 0.48 and 0.85 for sex, age and skin color respectively, significantly outperform their classical machine learning counterparts which achieved an MCC of 0.57, 0.22 and 0.54 at best. Once establishing that the deep-learning models are superior, further methods such as semi-supervised learning, a multi-characteristic classifier, sex-specific age classifiers and using tightly cropped facial images instead of upper-body images were employed to try and improve the deep-learning results. Throughout all deep-learning experiments the state of the art vision transformer and convolutional neural network were compared. Whilst the different architectures performed remarkably alike, a slight edge was seen for the convolutional neural network. The results further show that using cropped facial images generally improve the model performance and that more specialized models achieve modest improvements as compared to their less specialized counterparts. Semi-supervised learning showed potential in slightly improving the models further. The predictive performances achieved in this thesis indicate that the deep-learning models can reliably predict demographic features close to, or surpassing, a human.

[ES] Las imágenes de fondo de ojo son muy utilizadas por los oftalmólogos para la evaluación de la retina y la detección de glaucoma. Esta patología es la segunda causa de ceguera en el mundo, según estudios de la Organización Mundial de la Salud (OMS). En esta tesis doctoral, se estudian algoritmos de aprendizaje automático (machine learning) para la evaluación automática del glaucoma usando imágenes de fondo de ojo. En primer lugar, se proponen dos métodos para la segmentación automática. El primer método utiliza la transformación Watershed Estocástica para segmentar la copa óptica y posteriormente medir características clínicas como la relación Copa/Disco y la regla ISNT. El segundo método es una arquitectura U-Net que se usa específicamente para la segmentación del disco óptico y la copa óptica. A continuación, se presentan sistemas automáticos de evaluación del glaucoma basados en redes neuronales convolucionales (CNN por sus siglas en inglés). En este enfoque se utilizan diferentes modelos entrenados en ImageNet como clasificadores automáticos de glaucoma, usando fine-tuning. Esta nueva técnica permite detectar el glaucoma sin segmentación previa o extracción de características. Además, este enfoque presenta una mejora considerable del rendimiento comparado con otros trabajos del estado del arte. En tercer lugar, dada la dificultad de obtener grandes cantidades de imágenes etiquetadas (glaucoma/no glaucoma), esta tesis también aborda el problema de la síntesis de imágenes de la retina. En concreto se analizaron dos arquitecturas diferentes para la síntesis de imágenes, las arquitecturas Variational Autoencoder (VAE) y la Generative Adversarial Networks (GAN). Con estas arquitecturas se generaron imágenes sintéticas que se analizaron cualitativa y cuantitativamente, obteniendo un rendimiento similar a otros trabajos en la literatura. Finalmente, en esta tesis se plantea la utilización de un tipo de GAN (DCGAN) como alternativa a los sistemas automáticos de evaluación del glaucoma presentados anteriormente. Para alcanzar este objetivo se implementó un algoritmo de aprendizaje semi-supervisado. / [CA] Les imatges de fons d'ull són molt utilitzades pels oftalmòlegs per a l'avaluació de la retina i la detecció de glaucoma. Aquesta patologia és la segona causa de ceguesa al món, segons estudis de l'Organització Mundial de la Salut (OMS). En aquesta tesi doctoral, s'estudien algoritmes d'aprenentatge automàtic (machine learning) per a l'avaluació automàtica del glaucoma usant imatges de fons d'ull. En primer lloc, es proposen dos mètodes per a la segmentació automàtica. El primer mètode utilitza la transformació Watershed Estocàstica per segmentar la copa òptica i després mesurar característiques clíniques com la relació Copa / Disc i la regla ISNT. El segon mètode és una arquitectura U-Net que s'usa específicament per a la segmentació del disc òptic i la copa òptica. A continuació, es presenten sistemes automàtics d'avaluació del glaucoma basats en xarxes neuronals convolucionals (CNN per les sigles en anglès). En aquest enfocament s'utilitzen diferents models entrenats en ImageNet com classificadors automàtics de glaucoma, usant fine-tuning. Aquesta nova tècnica permet detectar el glaucoma sense segmentació prèvia o extracció de característiques. A més, aquest enfocament presenta una millora considerable del rendiment comparat amb altres treballs de l'estat de l'art. En tercer lloc, donada la dificultat d'obtenir grans quantitats d'imatges etiquetades (glaucoma / no glaucoma), aquesta tesi també aborda el problema de la síntesi d'imatges de la retina. En concret es van analitzar dues arquitectures diferents per a la síntesi d'imatges, les arquitectures Variational Autoencoder (VAE) i la Generative adversarial Networks (GAN). Amb aquestes arquitectures es van generar imatges sintètiques que es van analitzar qualitativament i quantitativament, obtenint un rendiment similar a altres treballs a la literatura. Finalment, en aquesta tesi es planteja la utilització d'un tipus de GAN (DCGAN) com a alternativa als sistemes automàtics d'avaluació del glaucoma presentats anteriorment. Per assolir aquest objectiu es va implementar un algoritme d'aprenentatge semi-supervisat. / [EN] Fundus images are widely used by ophthalmologists to assess the retina and detect glaucoma, which is, according to studies from the World Health Organization (WHO), the second cause of blindness worldwide. In this thesis, machine learning algorithms for automatic glaucoma assessment using fundus images are studied. First, two methods for automatic segmentation are proposed. The first method uses the Stochastic Watershed transformation to segment the optic cup and measures clinical features such as the Cup/Disc ratio and ISNT rule. The second method is a U-Net architecture focused on the optic disc and optic cup segmentation task. Secondly, automated glaucoma assessment systems using convolutional neural networks (CNNs) are presented. In this approach, different ImageNet-trained models are fine-tuned and used as automatic glaucoma classifiers. These new techniques allow detecting glaucoma without previous segmentation or feature extraction. Moreover, it improves the performance of other state-of-art works. Thirdly, given the difficulty of getting large amounts of glaucoma-labelled images, this thesis addresses the problem of retinal image synthesis. Two different architectures for image synthesis, the Variational Autoencoder (VAE) and Generative Adversarial Networks (GAN) architectures, were analysed. Using these models, synthetic images that were qualitative and quantitative analysed, reporting state-of-the-art performance, were generated. Finally, an adversarial model is used to create an alternative automatic glaucoma assessment system. In this part, a semi-supervised learning algorithm was implemented to reach this goal. / The research derived from this doctoral thesis has been supported by the Generalitat Valenciana under the scholarship Santiago Grisolía [GRISOLIA/2015/027]. / Díaz Pinto, AY. (2019). Machine Learning for Glaucoma Assessment using Fundus Images [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/124351

[pt] O aprendizado supervisionado é, hoje, o ramo do aprendizado de máquina central para a maioria das inovações nos negócios. A abordagem depende de ter grandes quantidades de dados rotulados, suficiente para ajustar funções com a precisão necessária. No entanto, pode ser caro obter dados rotulados ou criar os rótulos através de um processo de anotação. O aprendizado semisupervisionado (SSL) é usado para rotular com precisão os dados a partir de pequenas quantidades de dados rotulados utilizando técnicas de aprendizado não supervisionado. Uma técnica de rotulagem é a propagação de rótulos. Neste trabalho, usamos especificamente o algoritmo Consensus rate-based label propagation (CRLP). Este algoritmo depende do uma função de consenso para a propagação. Uma possível função de consenso é a matriz de co-associação que estima a probabilidade dos pontos i e j pertencem ao mesmo grupo. Neste trabalho, observamos que a matriz de co-associação contém informações valiosas para tratar esse tipo de problema. Quando nenhum dado está rotulado, é comum escolher aleatoriamente, com probabilidade uniforme, os dados a serem rotulados manualmente, a partir dos quais a propagação procede. Este trabalho aborda o problema de seleção de um conjunto de tamanho fixo de dados para serem rotulados manualmente que propiciem uma melhor precisão no algoritmo de propagação de rótulos. Três técnicas de seleção, baseadas em princípios de amostragem estocástica, são propostas: Stratified Sampling (SS), Probability (P), and Stratified Sampling - Probability (SSP). Eles são todos baseados nas informações embutidas na matriz de co-associação. Os experimentos foram realizados em 15 conjuntos de benchmarks e mostraram resultados muito interessantes. Não só, porque eles fornecem uma seleção mais equilibrada quando comparados a uma seleção aleatória, mas também melhoram os resultados de precisão na propagação de rótulos. Em outro contexto, essas estratégias também foram testadas dentro de um processo de aprendizagem ativa, obtendo também bons resultados. / [en] Supervised learning is, today, the branch of Machine Learning central to most business disruption. The approach relies on having amounts of labeled data large enough to learn functions with the required approximation. However, labeled data may be expensive, to obtain or to construct through a labeling process. Semi-supervised learning (SSL) strives to label accurately data from small amounts of labeled data and the use of unsupervised learning techniques. One labeling technique is label propagation. We use specifically the Consensus rate-based label propagation (CRLP) in this work. A consensus function is central to the propagation. A possible consensus function is a coassociation matrix that estimates the probability of data points i and j belong to the same group. In this work, we observe that the co-association matrix has valuable information embedded in it. When no data is labeled, it is common to choose with a uniform probability randomly, the data to manually label, from which the propagation proceeds. This work addresses the problem of selecting a fixed-size set of data points to label (manually), to improve the label propagation algorithm s accuracy. Three selection techniques, based on stochastic sampling principles, are proposed: Stratified Sampling (SP), Probability (P), and Stratified Sampling - Probability (SSP). They are all based on the information embedded in the co-association matrix. Experiments were carried out on 15 benchmark sets and showed exciting results. Not only because they provide a more balanced selection when compared to a uniform random selection, but also improved the accuracy results of a label propagation method. These strategies were also tested inside an active learning process in a different context, also achieving good results.

On étudie l’application des algorithmes de décomposition matricielles tel que la Factorisation Matricielle Non-négative (FMN), aux représentations fréquentielles de signaux audio musicaux. Ces algorithmes, dirigés par une fonction d’erreur de reconstruction, apprennent un ensemble de fonctions de base et un ensemble de coef- ficients correspondants qui approximent le signal d’entrée. On compare l’utilisation de trois fonctions d’erreur de reconstruction quand la FMN est appliquée à des gammes monophoniques et harmonisées: moindre carré, divergence Kullback-Leibler, et une mesure de divergence dépendente de la phase, introduite récemment. Des nouvelles méthodes pour interpréter les décompositions résultantes sont présentées et sont comparées aux méthodes utilisées précédemment qui nécessitent des connaissances du domaine acoustique. Finalement, on analyse la capacité de généralisation des fonctions de bases apprises par rapport à trois paramètres musicaux: l’amplitude, la durée et le type d’instrument. Pour ce faire, on introduit deux algorithmes d’étiquetage des fonctions de bases qui performent mieux que l’approche précédente dans la majorité de nos tests, la tâche d’instrument avec audio monophonique étant la seule exception importante. / We study the application of unsupervised matrix decomposition algorithms such as Non-negative Matrix Factorization (NMF) to frequency domain representations of music audio signals. These algorithms, driven by a given reconstruction error function, learn a set of basis functions and a set of corresponding coefficients that approximate the input signal. We compare the use of three reconstruction error functions when NMF is applied to monophonic and harmonized musical scales: least squares, Kullback-Leibler divergence, and a recently introduced “phase-aware” divergence measure. Novel supervised methods for interpreting the resulting decompositions are presented and compared to previously used methods that rely on domain knowledge. Finally, the ability of the learned basis functions to generalize across musical parameter values including note amplitude, note duration and instrument type, are analyzed. To do so, we introduce two basis function labeling algorithms that outperform the previous labeling approach in the majority of our tests, instrument type with monophonic audio being the only notable exception.

Malgré des progrès constants en termes de capacité de calcul, mémoire et quantité de données disponibles, les algorithmes d'apprentissage machine doivent se montrer efficaces dans l'utilisation de ces ressources. La minimisation des coûts est évidemment un facteur important, mais une autre motivation est la recherche de mécanismes d'apprentissage capables de reproduire le comportement d'êtres intelligents. Cette thèse aborde le problème de l'efficacité à travers plusieurs articles traitant d'algorithmes d'apprentissage variés : ce problème est vu non seulement du point de vue de l'efficacité computationnelle (temps de calcul et mémoire utilisés), mais aussi de celui de l'efficacité statistique (nombre d'exemples requis pour accomplir une tâche donnée). Une première contribution apportée par cette thèse est la mise en lumière d'inefficacités statistiques dans des algorithmes existants. Nous montrons ainsi que les arbres de décision généralisent mal pour certains types de tâches (chapitre 3), de même que les algorithmes classiques d'apprentissage semi-supervisé à base de graphe (chapitre 5), chacun étant affecté par une forme particulière de la malédiction de la dimensionalité. Pour une certaine classe de réseaux de neurones, appelés réseaux sommes-produits, nous montrons qu'il peut être exponentiellement moins efficace de représenter certaines fonctions par des réseaux à une seule couche cachée, comparé à des réseaux profonds (chapitre 4). Nos analyses permettent de mieux comprendre certains problèmes intrinsèques liés à ces algorithmes, et d'orienter la recherche dans des directions qui pourraient permettre de les résoudre. Nous identifions également des inefficacités computationnelles dans les algorithmes d'apprentissage semi-supervisé à base de graphe (chapitre 5), et dans l'apprentissage de mélanges de Gaussiennes en présence de valeurs manquantes (chapitre 6). Dans les deux cas, nous proposons de nouveaux algorithmes capables de traiter des ensembles de données significativement plus grands. Les deux derniers chapitres traitent de l'efficacité computationnelle sous un angle différent. Dans le chapitre 7, nous analysons de manière théorique un algorithme existant pour l'apprentissage efficace dans les machines de Boltzmann restreintes (la divergence contrastive), afin de mieux comprendre les raisons qui expliquent le succès de cet algorithme. Finalement, dans le chapitre 8 nous présentons une application de l'apprentissage machine dans le domaine des jeux vidéo, pour laquelle le problème de l'efficacité computationnelle est relié à des considérations d'ingénierie logicielle et matérielle, souvent ignorées en recherche mais ô combien importantes en pratique. / Despite constant progress in terms of available computational power, memory and amount of data, machine learning algorithms need to be efficient in how they use them. Although minimizing cost is an obvious major concern, another motivation is to attempt to design algorithms that can learn as efficiently as intelligent species. This thesis tackles the problem of efficient learning through various papers dealing with a wide range of machine learning algorithms: this topic is seen both from the point of view of computational efficiency (processing power and memory required by the algorithms) and of statistical efficiency (n umber of samples necessary to solve a given learning task).The first contribution of this thesis is in shedding light on various statistical inefficiencies in existing algorithms. Indeed, we show that decision trees do not generalize well on tasks with some particular properties (chapter 3), and that a similar flaw affects typical graph-based semi-supervised learning algorithms (chapter 5). This flaw is a form of curse of dimensionality that is specific to each of these algorithms. For a subclass of neural networks, called sum-product networks, we prove that using networks with a single hidden layer can be exponentially less efficient than when using deep networks (chapter 4). Our analyses help better understand some inherent flaws found in these algorithms, and steer research towards approaches that may potentially overcome them. We also exhibit computational inefficiencies in popular graph-based semi-supervised learning algorithms (chapter 5) as well as in the learning of mixtures of Gaussians with missing data (chapter 6). In both cases we propose new algorithms that make it possible to scale to much larger datasets. The last two chapters also deal with computational efficiency, but in different ways. Chapter 7 presents a new view on the contrastive divergence algorithm (which has been used for efficient training of restricted Boltzmann machines). It provides additional insight on the reasons why this algorithm has been so successful. Finally, in chapter 8 we describe an application of machine learning to video games, where computational efficiency is tied to software and hardware engineering constraints which, although often ignored in research papers, are ubiquitous in practice.

Extracting useful knowledge from data sets is a key concept in modern information systems. Consequently, the need of efficient techniques to extract the desired knowledge has been growing over time. Machine learning is a research field dedicated to the development of techniques capable of enabling a machine to \"learn\" from data. Many techniques have been proposed so far, but there are still issues to be unveiled specially in interdisciplinary research. In this thesis, we explore the advantages of network data representation to develop machine learning techniques based on dynamical processes on networks. The network representation unifies the structure, dynamics and functions of the system it represents, and thus is capable of capturing the spatial, topological and functional relations of the data sets under analysis. We develop network-based techniques for the three machine learning paradigms: supervised, semi-supervised and unsupervised. The random walk dynamical process is used to characterize the access of unlabeled data to data classes, configuring a new heuristic we call ease of access in the supervised paradigm. We also propose a classification technique which combines the high-level view of the data, via network topological characterization, and the low-level relations, via similarity measures, in a general framework. Still in the supervised setting, the modularity and Katz centrality network measures are applied to classify multiple observation sets, and an evolving network construction method is applied to the dimensionality reduction problem. The semi-supervised paradigm is covered by extending the ease of access heuristic to the cases in which just a few labeled data samples and many unlabeled samples are available. A semi-supervised technique based on interacting forces is also proposed, for which we provide parameter heuristics and stability analysis via a Lyapunov function. Finally, an unsupervised network-based technique uses the concepts of pinning control and consensus time from dynamical processes to derive a similarity measure used to cluster data. The data is represented by a connected and sparse network in which nodes are dynamical elements. Simulations on benchmark data sets and comparisons to well-known machine learning techniques are provided for all proposed techniques. Advantages of network data representation and dynamical processes for machine learning are highlighted in all cases / A extração de conhecimento útil a partir de conjuntos de dados é um conceito chave em sistemas de informação modernos. Por conseguinte, a necessidade de técnicas eficientes para extrair o conhecimento desejado vem crescendo ao longo do tempo. Aprendizado de máquina é uma área de pesquisa dedicada ao desenvolvimento de técnicas capazes de permitir que uma máquina \"aprenda\" a partir de conjuntos de dados. Muitas técnicas já foram propostas, mas ainda há questões a serem reveladas especialmente em pesquisas interdisciplinares. Nesta tese, exploramos as vantagens da representação de dados em rede para desenvolver técnicas de aprendizado de máquina baseadas em processos dinâmicos em redes. A representação em rede unifica a estrutura, a dinâmica e as funções do sistema representado e, portanto, é capaz de capturar as relações espaciais, topológicas e funcionais dos conjuntos de dados sob análise. Desenvolvemos técnicas baseadas em rede para os três paradigmas de aprendizado de máquina: supervisionado, semissupervisionado e não supervisionado. O processo dinâmico de passeio aleatório é utilizado para caracterizar o acesso de dados não rotulados às classes de dados configurando uma nova heurística no paradigma supervisionado, a qual chamamos de facilidade de acesso. Também propomos uma técnica de classificação de dados que combina a visão de alto nível dos dados, por meio da caracterização topológica de rede, com relações de baixo nível, por meio de medidas de similaridade, em uma estrutura geral. Ainda no aprendizado supervisionado, as medidas de rede modularidade e centralidade Katz são aplicadas para classificar conjuntos de múltiplas observações, e um método de construção evolutiva de rede é aplicado ao problema de redução de dimensionalidade. O paradigma semissupervisionado é abordado por meio da extensão da heurística de facilidade de acesso para os casos em que apenas algumas amostras de dados rotuladas e muitas amostras não rotuladas estão disponíveis. É também proposta uma técnica semissupervisionada baseada em forças de interação, para a qual fornecemos heurísticas para selecionar parâmetros e uma análise de estabilidade mediante uma função de Lyapunov. Finalmente, uma técnica não supervisionada baseada em rede utiliza os conceitos de controle pontual e tempo de consenso de processos dinâmicos para derivar uma medida de similaridade usada para agrupar dados. Os dados são representados por uma rede conectada e esparsa na qual os vértices são elementos dinâmicos. Simulações com dados de referência e comparações com técnicas de aprendizado de máquina conhecidas são fornecidos para todas as técnicas propostas. As vantagens da representação de dados em rede e de processos dinâmicos para o aprendizado de máquina são evidenciadas em todos os casos

Malgré des progrès constants en termes de capacité de calcul, mémoire et quantité de données disponibles, les algorithmes d'apprentissage machine doivent se montrer efficaces dans l'utilisation de ces ressources. La minimisation des coûts est évidemment un facteur important, mais une autre motivation est la recherche de mécanismes d'apprentissage capables de reproduire le comportement d'êtres intelligents. Cette thèse aborde le problème de l'efficacité à travers plusieurs articles traitant d'algorithmes d'apprentissage variés : ce problème est vu non seulement du point de vue de l'efficacité computationnelle (temps de calcul et mémoire utilisés), mais aussi de celui de l'efficacité statistique (nombre d'exemples requis pour accomplir une tâche donnée). Une première contribution apportée par cette thèse est la mise en lumière d'inefficacités statistiques dans des algorithmes existants. Nous montrons ainsi que les arbres de décision généralisent mal pour certains types de tâches (chapitre 3), de même que les algorithmes classiques d'apprentissage semi-supervisé à base de graphe (chapitre 5), chacun étant affecté par une forme particulière de la malédiction de la dimensionalité. Pour une certaine classe de réseaux de neurones, appelés réseaux sommes-produits, nous montrons qu'il peut être exponentiellement moins efficace de représenter certaines fonctions par des réseaux à une seule couche cachée, comparé à des réseaux profonds (chapitre 4). Nos analyses permettent de mieux comprendre certains problèmes intrinsèques liés à ces algorithmes, et d'orienter la recherche dans des directions qui pourraient permettre de les résoudre. Nous identifions également des inefficacités computationnelles dans les algorithmes d'apprentissage semi-supervisé à base de graphe (chapitre 5), et dans l'apprentissage de mélanges de Gaussiennes en présence de valeurs manquantes (chapitre 6). Dans les deux cas, nous proposons de nouveaux algorithmes capables de traiter des ensembles de données significativement plus grands. Les deux derniers chapitres traitent de l'efficacité computationnelle sous un angle différent. Dans le chapitre 7, nous analysons de manière théorique un algorithme existant pour l'apprentissage efficace dans les machines de Boltzmann restreintes (la divergence contrastive), afin de mieux comprendre les raisons qui expliquent le succès de cet algorithme. Finalement, dans le chapitre 8 nous présentons une application de l'apprentissage machine dans le domaine des jeux vidéo, pour laquelle le problème de l'efficacité computationnelle est relié à des considérations d'ingénierie logicielle et matérielle, souvent ignorées en recherche mais ô combien importantes en pratique. / Despite constant progress in terms of available computational power, memory and amount of data, machine learning algorithms need to be efficient in how they use them. Although minimizing cost is an obvious major concern, another motivation is to attempt to design algorithms that can learn as efficiently as intelligent species. This thesis tackles the problem of efficient learning through various papers dealing with a wide range of machine learning algorithms: this topic is seen both from the point of view of computational efficiency (processing power and memory required by the algorithms) and of statistical efficiency (n umber of samples necessary to solve a given learning task).The first contribution of this thesis is in shedding light on various statistical inefficiencies in existing algorithms. Indeed, we show that decision trees do not generalize well on tasks with some particular properties (chapter 3), and that a similar flaw affects typical graph-based semi-supervised learning algorithms (chapter 5). This flaw is a form of curse of dimensionality that is specific to each of these algorithms. For a subclass of neural networks, called sum-product networks, we prove that using networks with a single hidden layer can be exponentially less efficient than when using deep networks (chapter 4). Our analyses help better understand some inherent flaws found in these algorithms, and steer research towards approaches that may potentially overcome them. We also exhibit computational inefficiencies in popular graph-based semi-supervised learning algorithms (chapter 5) as well as in the learning of mixtures of Gaussians with missing data (chapter 6). In both cases we propose new algorithms that make it possible to scale to much larger datasets. The last two chapters also deal with computational efficiency, but in different ways. Chapter 7 presents a new view on the contrastive divergence algorithm (which has been used for efficient training of restricted Boltzmann machines). It provides additional insight on the reasons why this algorithm has been so successful. Finally, in chapter 8 we describe an application of machine learning to video games, where computational efficiency is tied to software and hardware engineering constraints which, although often ignored in research papers, are ubiquitous in practice.

On étudie l’application des algorithmes de décomposition matricielles tel que la Factorisation Matricielle Non-négative (FMN), aux représentations fréquentielles de signaux audio musicaux. Ces algorithmes, dirigés par une fonction d’erreur de reconstruction, apprennent un ensemble de fonctions de base et un ensemble de coef- ficients correspondants qui approximent le signal d’entrée. On compare l’utilisation de trois fonctions d’erreur de reconstruction quand la FMN est appliquée à des gammes monophoniques et harmonisées: moindre carré, divergence Kullback-Leibler, et une mesure de divergence dépendente de la phase, introduite récemment. Des nouvelles méthodes pour interpréter les décompositions résultantes sont présentées et sont comparées aux méthodes utilisées précédemment qui nécessitent des connaissances du domaine acoustique. Finalement, on analyse la capacité de généralisation des fonctions de bases apprises par rapport à trois paramètres musicaux: l’amplitude, la durée et le type d’instrument. Pour ce faire, on introduit deux algorithmes d’étiquetage des fonctions de bases qui performent mieux que l’approche précédente dans la majorité de nos tests, la tâche d’instrument avec audio monophonique étant la seule exception importante. / We study the application of unsupervised matrix decomposition algorithms such as Non-negative Matrix Factorization (NMF) to frequency domain representations of music audio signals. These algorithms, driven by a given reconstruction error function, learn a set of basis functions and a set of corresponding coefficients that approximate the input signal. We compare the use of three reconstruction error functions when NMF is applied to monophonic and harmonized musical scales: least squares, Kullback-Leibler divergence, and a recently introduced “phase-aware” divergence measure. Novel supervised methods for interpreting the resulting decompositions are presented and compared to previously used methods that rely on domain knowledge. Finally, the ability of the learned basis functions to generalize across musical parameter values including note amplitude, note duration and instrument type, are analyzed. To do so, we introduce two basis function labeling algorithms that outperform the previous labeling approach in the majority of our tests, instrument type with monophonic audio being the only notable exception.