Bidirectional Helmholtz Machines

L'entraînement sans surveillance efficace et inférence dans les modèles génératifs profonds reste un problème difficile. Une approche assez simple, la machine de Helmholtz, consiste à entraîner du haut vers le bas un modèle génératif dirigé qui sera utilisé plus tard pour l'inférence approximative. Des résultats récents suggèrent que de meilleurs modèles génératifs peuvent être obtenus par de meilleures procédures d'inférence approximatives. Au lieu d'améliorer la procédure d'inférence, nous proposons ici un nouveau modèle, la machine de Helmholtz bidirectionnelle, qui garantit qu'on peut calculer efficacement les distributions de haut-vers-bas et de bas-vers-haut. Nous y parvenons en interprétant à les modèles haut-vers-bas et bas-vers-haut en tant que distributions d'inférence approximative, puis ensuite en définissant la distribution du modèle comme étant la moyenne géométrique de ces deux distributions. Nous dérivons une borne inférieure pour la vraisemblance de ce modèle, et nous démontrons que l'optimisation de cette borne se comporte en régulisateur. Ce régularisateur sera tel que la distance de Bhattacharyya sera minisée entre les distributions approximatives haut-vers-bas et bas-vers-haut. Cette approche produit des résultats de pointe en terme de modèles génératifs qui favorisent les réseaux significativement plus profonds. Elle permet aussi une inférence approximative amérliorée par plusieurs ordres de grandeur. De plus, nous introduisons un modèle génératif profond basé sur les modèles BiHM pour l'entraînement semi-supervisé.

Interrelated product design activities sequencing with efficient tabu search algorithms

This paper proposes and investigates a metaheuristic tabu search algorithm (TSA) that generates optimal or near optimal solutions sequences for the feedback length minimization problem (FLMP) associated to a design structure matrix (DSM). The FLMP is a non-linear combinatorial optimization problem, belonging to the NP-hard class, and therefore finding an exact optimal solution is very hard and time consuming, especially on medium and large problem instances. First, we introduce the subject and provide a review of the related literature and problem definitions. Using the tabu search method (TSM) paradigm, this paper presents a new tabu search algorithm that generates optimal or sub-optimal solutions for the feedback length minimization problem, using two different neighborhoods based on swaps of two activities and shifting an activity to a different position. Furthermore, this paper includes numerical results for analyzing the performance of the proposed TSA and for fixing the proper values of its parameters. Then we compare our results on benchmarked problems with those already published in the literature. We conclude that the proposed tabu search algorithm is very promising because it outperforms the existing methods, and because no other tabu search method for the FLMP is reported in the literature. The proposed tabu search algorithm applied to the process layer of the multidimensional design structure matrices proves to be a key optimization method for an optimal product development.

Détection de mouvements dans des séquences d’images basée sur la dynamique de supraconductivité

Le but de ce travail est d’étudier la faisabilité de la détection de mouvements dans des séquences d’images en utilisant l’équation de continuité et la dynamique de supraconductivité. Notre approche peut être motivée par le fait que l’équation de continuité apparait dans plusieurs techniques qui estiment le flot optique. Un grand nombre de techniques qui utilisent les flots optiques utilisent une contrainte appelée contrainte de l’invariance lumineuse. La dynamique de supraconductivité nous permet de nous affranchir de la contrainte de l’invariance lumineuse. Les expériences se feront avec la base de données de séquences d’images CDNET 2014. Pour obtenir les résultats numériques en terme de score F1, une combinaison sera faite par la suite entre la dynamique de supraconductivité et un méchanisme d’attention qui est un résumé des vérites de terrain.

An adaptive neighborhood search algorithm for optimizing stochastic mining complexes

Les métaheuristiques sont très utilisées dans le domaine de l'optimisation discrète. Elles permettent d’obtenir une solution de bonne qualité en un temps raisonnable, pour des problèmes qui sont de grande taille, complexes, et difficiles à résoudre. Souvent, les métaheuristiques ont beaucoup de paramètres que l’utilisateur doit ajuster manuellement pour un problème donné. L'objectif d'une métaheuristique adaptative est de permettre l'ajustement automatique de certains paramètres par la méthode, en se basant sur l’instance à résoudre. La métaheuristique adaptative, en utilisant les connaissances préalables dans la compréhension du problème, des notions de l'apprentissage machine et des domaines associés, crée une méthode plus générale et automatique pour résoudre des problèmes. L’optimisation globale des complexes miniers vise à établir les mouvements des matériaux dans les mines et les flux de traitement afin de maximiser la valeur économique du système. Souvent, en raison du grand nombre de variables entières dans le modèle, de la présence de contraintes complexes et de contraintes non-linéaires, il devient prohibitif de résoudre ces modèles en utilisant les optimiseurs disponibles dans l’industrie. Par conséquent, les métaheuristiques sont souvent utilisées pour l’optimisation de complexes miniers. Ce mémoire améliore un procédé de recuit simulé développé par Goodfellow & Dimitrakopoulos (2016) pour l’optimisation stochastique des complexes miniers stochastiques. La méthode développée par les auteurs nécessite beaucoup de paramètres pour fonctionner. Un de ceux-ci est de savoir comment la méthode de recuit simulé cherche dans le voisinage local de solutions. Ce mémoire implémente une méthode adaptative de recherche dans le voisinage pour améliorer la qualité d'une solution. Les résultats numériques montrent une augmentation jusqu'à 10% de la valeur de la fonction économique.

Estimation de cartes d'énergie de hautes fréquences ou d'irrégularité de périodicité de la marche humaine par caméra de profondeur pour la détection de pathologies

Ce travail présente deux nouveaux systèmes simples d'analyse de la marche humaine grâce à une caméra de profondeur (Microsoft Kinect) placée devant un sujet marchant sur un tapis roulant conventionnel, capables de détecter une marche saine et celle déficiente. Le premier système repose sur le fait qu'une marche normale présente typiquement un signal de profondeur lisse au niveau de chaque pixel avec moins de hautes fréquences, ce qui permet d'estimer une carte indiquant l'emplacement et l'amplitude de l'énergie de haute fréquence (HFSE). Le second système analyse les parties du corps qui ont un motif de mouvement irrégulier, en termes de périodicité, lors de la marche. Nous supposons que la marche d'un sujet sain présente partout dans le corps, pendant les cycles de marche, un signal de profondeur avec un motif périodique sans bruit. Nous estimons, à partir de la séquence vidéo de chaque sujet, une carte montrant les zones d'irrégularités de la marche (également appelées énergie de bruit apériodique). La carte avec HFSE ou celle visualisant l'énergie de bruit apériodique peut être utilisée comme un bon indicateur d'une éventuelle pathologie, dans un outil de diagnostic précoce, rapide et fiable, ou permettre de fournir des informations sur la présence et l'étendue de la maladie ou des problèmes (orthopédiques, musculaires ou neurologiques) du patient. Même si les cartes obtenues sont informatives et très discriminantes pour une classification visuelle directe, même pour un non-spécialiste, les systèmes proposés permettent de détecter automatiquement les individus en bonne santé et ceux avec des problèmes locomoteurs.

Étude de la médiane de permutations sous la distance de Kendall-Tau

La distance de Kendall-τ compte le nombre de paires en désaccord entre deux permuta- tions. La distance d’une permutation à un ensemble est simplement la somme des dis- tances entre cette permutation et les permutations de l’ensemble. À partir d’un ensemble donné de permutations, notre but est de trouver la permutation, appelée médiane, qui minimise cette distance à l’ensemble. Le problème de la médiane de permutations sous la distance de Kendall-τ, trouve son application en bio-informatique, en science politique, en télécommunication et en optimisation. Ce problème d’apparence simple est prouvé difficile à résoudre. Dans ce mémoire, nous présentons plusieurs approches pour résoudre le problème, pour trouver une bonne solution approximative, pour le séparer en classes caractéristiques, pour mieux com- prendre sa compléxité, pour réduire l’espace de recheche et pour accélérer les calculs. Nous présentons aussi, vers la fin du mémoire, une généralisation de ce problème et nous l’étudions avec ces mêmes approches. La majorité du travail de ce mémoire se situe dans les trois articles qui le composent et est complémenté par deux chapitres servant à les lier.

Développement d’un système d’appariement pour l’e-recrutement

Ce mémoire tente de répondre à une problématique très importante dans le domaine de recrutement : l’appariement entre offre d’emploi et candidats. Dans notre cas nous disposons de milliers d’offres d’emploi et de millions de profils ramassés sur les sites dédiés et fournis par un industriel spécialisé dans le recrutement. Les offres d’emploi et les profils de candidats sur les réseaux sociaux professionnels sont généralement destinés à des lecteurs humains qui sont les recruteurs et les chercheurs d’emploi. Chercher à effectuer une sélection automatique de profils pour une offre d’emploi se heurte donc à certaines difficultés que nous avons cherché à résoudre dans le présent mémoire. Nous avons utilisé des techniques de traitement automatique de la langue naturelle pour extraire automatiquement les informations pertinentes dans une offre d’emploi afin de construite une requête qui nous permettrait d’interroger notre base de données de profils. Pour valider notre modèle d’extraction de métier, de compétences et de d’expérience, nous avons évalué ces trois différentes tâches séparément en nous basant sur une référence cent offres d’emploi canadiennes que nous avons manuellement annotée. Et pour valider notre outil d’appariement nous avons fait évaluer le résultat de l’appariement de dix offres d’emploi canadiennes par un expert en recrutement.

Environnement d’adaptation pour un jeu sérieux

Nous avons développé un jeu sérieux afin d’enseigner aux utilisateurs à dessiner des diagrammes de Lewis. Nous l’avons augmenté d’un environnement pouvant enregistrer des signaux électroencéphalographiques, les expressions faciales, et la pupille d’un utilisateur. Le but de ce travail est de vérifier si l’environnement peut permettre au jeu de s’adapter en temps réel à l’utilisateur grâce à une détection automatique du besoin d’aide de l’utilisateur ainsi que si l’utilisateur est davantage satisfait de son expérience avec l’adaptation. Les résultats démontrent que le système d’adaptation peut détecter le besoin d’aide grâce à deux modèles d’apprentissage machine entraînés différemment, l’un généralisé et l’autre personalisé, avec des performances respectives de 53.4% et 67.5% par rapport à un niveau de chance de 33.3%.

Un modèle rétroactif de réconciliation utilité-confidentialité sur les données d’assurance

Le partage des données de façon confidentielle préoccupe un bon nombre d’acteurs, peu importe le domaine. La recherche évolue rapidement, mais le manque de solutions adaptées à la réalité d’une entreprise freine l’adoption de bonnes pratiques d’affaires quant à la protection des renseignements sensibles. Nous proposons dans ce mémoire une solution modulaire, évolutive et complète nommée PEPS, paramétrée pour une utilisation dans le domaine de l’assurance. Nous évaluons le cycle entier d’un partage confidentiel, de la gestion des données à la divulgation, en passant par la gestion des forces externes et l’anonymisation. PEPS se démarque du fait qu’il utilise la contextualisation du problème rencontré et l’information propre au domaine afin de s’ajuster et de maximiser l’utilisation de l’ensemble anonymisé. À cette fin, nous présentons un algorithme d’anonymat fortement contextualisé ainsi que des mesures de performances ajustées aux analyses d’expérience.

Une heuristique de recherche à voisinage variable pour le problème du voyageur de commerce avec fenêtres de temps

Nous adaptons une heuristique de recherche à voisinage variable pour traiter le problème du voyageur de commerce avec fenêtres de temps (TSPTW) lorsque l'objectif est la minimisation du temps d'arrivée au dépôt de destination. Nous utilisons des méthodes efficientes pour la vérification de la réalisabilité et de la rentabilité d'un mouvement. Nous explorons les voisinages dans des ordres permettant de réduire l'espace de recherche. La méthode résultante est compétitive avec l'état de l'art. Nous améliorons les meilleures solutions connues pour deux classes d'instances et nous fournissons les résultats de plusieurs instances du TSPTW pour la première fois.

Development of new scenario decomposition techniques for linear and nonlinear stochastic programming

Une approche classique pour traiter les problèmes d’optimisation avec incertitude à deux- et multi-étapes est d’utiliser l’analyse par scénario. Pour ce faire, l’incertitude de certaines données du problème est modélisée par vecteurs aléatoires avec des supports finis spécifiques aux étapes. Chacune de ces réalisations représente un scénario. En utilisant des scénarios, il est possible d’étudier des versions plus simples (sous-problèmes) du problème original. Comme technique de décomposition par scénario, l’algorithme de recouvrement progressif est une des méthodes les plus populaires pour résoudre les problèmes de programmation stochastique multi-étapes. Malgré la décomposition complète par scénario, l’efficacité de la méthode du recouvrement progressif est très sensible à certains aspects pratiques, tels que le choix du paramètre de pénalisation et la manipulation du terme quadratique dans la fonction objectif du lagrangien augmenté. Pour le choix du paramètre de pénalisation, nous examinons quelques-unes des méthodes populaires, et nous proposons une nouvelle stratégie adaptive qui vise à mieux suivre le processus de l’algorithme. Des expériences numériques sur des exemples de problèmes stochastiques linéaires multi-étapes suggèrent que la plupart des techniques existantes peuvent présenter une convergence prématurée à une solution sous-optimale ou converger vers la solution optimale, mais avec un taux très lent. En revanche, la nouvelle stratégie paraît robuste et efficace. Elle a convergé vers l’optimalité dans toutes nos expériences et a été la plus rapide dans la plupart des cas. Pour la question de la manipulation du terme quadratique, nous faisons une revue des techniques existantes et nous proposons l’idée de remplacer le terme quadratique par un terme linéaire. Bien que qu’il nous reste encore à tester notre méthode, nous avons l’intuition qu’elle réduira certaines difficultés numériques et théoriques de la méthode de recouvrement progressif.

Bidirectional Helmholtz Machines

L'entraînement sans surveillance efficace et inférence dans les modèles génératifs profonds reste un problème difficile. Une approche assez simple, la machine de Helmholtz, consiste à entraîner du haut vers le bas un modèle génératif dirigé qui sera utilisé plus tard pour l'inférence approximative. Des résultats récents suggèrent que de meilleurs modèles génératifs peuvent être obtenus par de meilleures procédures d'inférence approximatives. Au lieu d'améliorer la procédure d'inférence, nous proposons ici un nouveau modèle, la machine de Helmholtz bidirectionnelle, qui garantit qu'on peut calculer efficacement les distributions de haut-vers-bas et de bas-vers-haut. Nous y parvenons en interprétant à les modèles haut-vers-bas et bas-vers-haut en tant que distributions d'inférence approximative, puis ensuite en définissant la distribution du modèle comme étant la moyenne géométrique de ces deux distributions. Nous dérivons une borne inférieure pour la vraisemblance de ce modèle, et nous démontrons que l'optimisation de cette borne se comporte en régulisateur. Ce régularisateur sera tel que la distance de Bhattacharyya sera minisée entre les distributions approximatives haut-vers-bas et bas-vers-haut. Cette approche produit des résultats de pointe en terme de modèles génératifs qui favorisent les réseaux significativement plus profonds. Elle permet aussi une inférence approximative amérliorée par plusieurs ordres de grandeur. De plus, nous introduisons un modèle génératif profond basé sur les modèles BiHM pour l'entraînement semi-supervisé.

Interrelated product design activities sequencing with efficient tabu search algorithms

This paper proposes and investigates a metaheuristic tabu search algorithm (TSA) that generates optimal or near optimal solutions sequences for the feedback length minimization problem (FLMP) associated to a design structure matrix (DSM). The FLMP is a non-linear combinatorial optimization problem, belonging to the NP-hard class, and therefore finding an exact optimal solution is very hard and time consuming, especially on medium and large problem instances. First, we introduce the subject and provide a review of the related literature and problem definitions. Using the tabu search method (TSM) paradigm, this paper presents a new tabu search algorithm that generates optimal or sub-optimal solutions for the feedback length minimization problem, using two different neighborhoods based on swaps of two activities and shifting an activity to a different position. Furthermore, this paper includes numerical results for analyzing the performance of the proposed TSA and for fixing the proper values of its parameters. Then we compare our results on benchmarked problems with those already published in the literature. We conclude that the proposed tabu search algorithm is very promising because it outperforms the existing methods, and because no other tabu search method for the FLMP is reported in the literature. The proposed tabu search algorithm applied to the process layer of the multidimensional design structure matrices proves to be a key optimization method for an optimal product development.

Détection de mouvements dans des séquences d’images basée sur la dynamique de supraconductivité

Le but de ce travail est d’étudier la faisabilité de la détection de mouvements dans des séquences d’images en utilisant l’équation de continuité et la dynamique de supraconductivité. Notre approche peut être motivée par le fait que l’équation de continuité apparait dans plusieurs techniques qui estiment le flot optique. Un grand nombre de techniques qui utilisent les flots optiques utilisent une contrainte appelée contrainte de l’invariance lumineuse. La dynamique de supraconductivité nous permet de nous affranchir de la contrainte de l’invariance lumineuse. Les expériences se feront avec la base de données de séquences d’images CDNET 2014. Pour obtenir les résultats numériques en terme de score F1, une combinaison sera faite par la suite entre la dynamique de supraconductivité et un méchanisme d’attention qui est un résumé des vérites de terrain.

An adaptive neighborhood search algorithm for optimizing stochastic mining complexes

Les métaheuristiques sont très utilisées dans le domaine de l'optimisation discrète. Elles permettent d’obtenir une solution de bonne qualité en un temps raisonnable, pour des problèmes qui sont de grande taille, complexes, et difficiles à résoudre. Souvent, les métaheuristiques ont beaucoup de paramètres que l’utilisateur doit ajuster manuellement pour un problème donné. L'objectif d'une métaheuristique adaptative est de permettre l'ajustement automatique de certains paramètres par la méthode, en se basant sur l’instance à résoudre. La métaheuristique adaptative, en utilisant les connaissances préalables dans la compréhension du problème, des notions de l'apprentissage machine et des domaines associés, crée une méthode plus générale et automatique pour résoudre des problèmes. L’optimisation globale des complexes miniers vise à établir les mouvements des matériaux dans les mines et les flux de traitement afin de maximiser la valeur économique du système. Souvent, en raison du grand nombre de variables entières dans le modèle, de la présence de contraintes complexes et de contraintes non-linéaires, il devient prohibitif de résoudre ces modèles en utilisant les optimiseurs disponibles dans l’industrie. Par conséquent, les métaheuristiques sont souvent utilisées pour l’optimisation de complexes miniers. Ce mémoire améliore un procédé de recuit simulé développé par Goodfellow & Dimitrakopoulos (2016) pour l’optimisation stochastique des complexes miniers stochastiques. La méthode développée par les auteurs nécessite beaucoup de paramètres pour fonctionner. Un de ceux-ci est de savoir comment la méthode de recuit simulé cherche dans le voisinage local de solutions. Ce mémoire implémente une méthode adaptative de recherche dans le voisinage pour améliorer la qualité d'une solution. Les résultats numériques montrent une augmentation jusqu'à 10% de la valeur de la fonction économique.