No description available.

Distributed iterative algorithms are of great importance, as they are known to provide low-complexity and approximate solutions to what are otherwise high-dimensional intractable optimization problems. The theory of message-passing based algorithms is fairly well developed in the coding, machine learning and statistical physics literatures. Even though several applications of message-passing algorithms have already been identified, this work aims at establishing that a plethora of other applications exist where it can be of great importance. In particular, the goal of this work is to develop and demonstrate applications of this class of algorithms in network communications and computational biology. In the domain of communications, message-passing based algorithms provide distributed ways of inferring the optimal solution without the aid of a central agent for various optimization problems that happen in the resource allocation of communication networks. Our main framework is Affinity Propagation (AP), originally developed for clustering problems. We reinterpret this framework to unify the development of distributed algorithms for discrete resource allocation problems. Also, we consider a network-coded communication network, where continuous rate allocation is studied. We formulate an optimization problem with a linear cost function, and then utilize a Belief Propagation (BP) approach to determine a decentralized rate allocation strategy. Next, we move to the domain of computational biology, where graphical representations and computational biology play a major role. First, we consider the motif finding problem with several DNA sequences. In effect, this is a sequence matching problem, which can be modeled using various graphical representations and also solved using low-complexity algorithms based on message-passing techniques. In addition, we address the application of message-passing algorithms for a DNA sequencing problem where the one dimensional structure of a single DNA sequence is identified. We reinterpret the problem as being equivalent to the decoding of a nonlinear code. Based on the iterative decoding framework, we develop an appropriate graphical model which enables us to derive a message-passing algorithm to improve the performance of the DNA sequencing problem. Although this work consists of disparate application domains of communications, networks and computational biology, graphical models and distributed message-passing algorithms form a common underlying theme. / text

Submitted by DANIELA CABRAL DE OLIVEIRA null (danielacaboliveira@gmail.com) on 2017-07-31T18:25:34Z No. of bitstreams: 1 Dissertacao.pdf: 4071736 bytes, checksum: 8334dda6779551cc88a5687ed7937bb3 (MD5) / Approved for entry into archive by Luiz Galeffi (luizgaleffi@gmail.com) on 2017-08-03T16:52:18Z (GMT) No. of bitstreams: 1 oliveira_dc_me_ilha.pdf: 4071736 bytes, checksum: 8334dda6779551cc88a5687ed7937bb3 (MD5) / Made available in DSpace on 2017-08-03T16:52:18Z (GMT). No. of bitstreams: 1 oliveira_dc_me_ilha.pdf: 4071736 bytes, checksum: 8334dda6779551cc88a5687ed7937bb3 (MD5) Previous issue date: 2017-06-28 / Este trabalho introduz uma nova metodologia de Monitoramento da Integridade de Estruturas (SHM, do inglês Structural Health Monitoring) utilizando algoritmos de aprendizado de máquina não-supervisionado para localização e detecção de dano. A abordagem foi testada em material isotrópico (placa de alumínio). Os dados experimentais foram cedidos por Rosa (2016). O banco de dados disponibilizado é abrangente e inclui medidas em diversas situações. Os transdutores piezelétricos foram colados na placa de alumínio com dimensões de 500 x 500 x 2mm, que atuam como sensores e atuadores ao mesmo tempo. Para manipulação dos dados foram analisados os sinais definindo o primeiro pacote do sinal (first packet), considerando apenas o intervalo de tempo igual ao tempo da força de excitação. Neste caso, na há interferência dos sinais refletidos nas bordas da estrutura. Os sinais são obtidos na situação sem dano (baseline) e, posteriormente nas diversas situações de dano. Como método de avaliação do quanto o dano interfere em cada caminho, foram implementadas as seguintes métricas: pico máximo, valor médio quadrático (RMSD), correlação entre os sinais, normas H2 e H∞ entre os sinais baseline e sinais com dano. Logo após o cálculo das métricas para as diversas situações de dano, foi implementado o algoritmo de aprendizado de máquina não-supervisionado K-Means no matlab e também testado no toolbox Weka. No algoritmo K-Means há a necessidade da pré-determinação do número de clusters e isto pode dificultar sua utilização nas situações reais. Então, fez se necessário a implementação de um algoritmo de aprendizado de máquina não-supervisionado que utiliza propagação de afinidades, onde a determinação do número de clusters é definida pela matriz de similaridades. O algoritmo de propagação de afinidades foi desenvolvido para todas as métricas separadamente para cada dano. / This paper introduces a new Structural Health Monitoring (SHM) methodology using unsupervised machine learning algorithms for locating and detecting damage. The approach was tested with isotropic material in an aluminum plate. Experimental data were provided by Rosa (2016). This provided database is open and includes measures in a variety of situations. The piezoelectric transducers were bonded to the aluminum plate with dimensions 500 x 500 x 2mm, and act as sensors and actuators simultaneously. In order to manipulate the data, signals defining the first packet were analyzed. It considers strictly the time interval equal to excitation force length. In this case, there is no interference of reflected signals in the structure boundaries. Signals are gathered at undamaged situation (baseline) and at several damage situations. As an evaluating method of how damage interferes in each path, it was implemented the following metrics: maximum peak, root-mean-square deviation (RMSD), correlation between signals, H2 and H∞ norms regarding baseline and damaged signals. The metrics were computed for numerous damage situations. The data were evaluated in an unsupervised K-Means machine learning algorithm implemented in matlab and also tested in Weka toolbox. However, the K-Means algorithm requires the specification of the number of clusters and it is a problem for practical applications. Therefore, an implementation of an unsupervised machine learning algorithm, which uses affinity propagation was made. In this case, the determination of the number of clusters is defined by the data similarity matrix. The affinity propagation algorithm was developed for all metrics separately for each damage.

The ability to learn is essential for robots to function and perform services within a dynamic human environment. Robot programming by demonstration facilitates learning through a human teacher without the need to develop new code for each task that the robot performs. In order for learning to be generalizable, the robot needs to be able to grasp the underlying structure of the task being learned. This requires appropriate knowledge abstraction and representation. The goal of this thesis is to develop a learning by imitation system that abstracts knowledge of human demonstrations of a task and represents the abstracted knowledge in a hierarchical framework. The learning by imitation system is capable of performing both action and object recognition based on video stream data at the lower level of the hierarchy, while the sequence of actions and object states observed is reconstructed at the higher level of the hierarchy in order to form a coherent representation of the task. Furthermore, error recovery capabilities are included in the learning by imitation system to improve robustness to unexpected situations during task execution. The first part of the thesis focuses on motion learning to allow the robot to both recognize the actions for task representation at the higher level of the hierarchy and to perform the actions to imitate the task. In order to efficiently learn actions, the actions are segmented into meaningful atomic units called motion primitives. These motion primitives are then modeled using dynamic movement primitives (DMPs), a dynamical system model that can robustly generate motion trajectories to arbitrary goal positions while maintaining the overall shape of the demonstrated motion trajectory. The DMPs also contain weight parameters that are reflective of the shape of the motion trajectory. These weight parameters are clustered using affinity propagation (AP), an efficient exemplar clustering algorithm, in order to determine groups of similar motion primitives and thus, performing motion recognition. The approach of DMPs combined with APs was experimentally verified on two separate motion data sets for its ability to recognize and generate motion primitives. The second part of the thesis outlines how the task representation is created and used for imitating observed tasks. This includes object and object state recognition using simple computer vision techniques as well as the automatic construction of a Petri net (PN) model to describe an observed task. Tasks are composed of a sequence of actions that have specific pre-conditions, i.e. object states required before the action can be performed, and post-conditions, i.e. object states that result from the action. The PNs inherently encode pre-conditions and post-conditions of a particular event, i.e. action, and can model tasks as a coherent sequence of actions and object states. In addition, PNs are very flexible in modeling a variety of tasks including tasks that involve both sequential and parallel components. The automatic PN creation process has been tested on both a sequential two block stacking task and a three block stacking task involving both sequential and parallel components. The PN provides a meaningful representation of the observed tasks that can be used by a robot to imitate the tasks. Lastly, error recovery capabilities are added to the learning by imitation system in order to allow the robot to readjust the sequence of actions needed during task execution. The error recovery component is able to deal with two types of errors: unexpected, but known situations and unexpected, unknown situations. In the case of unexpected, but known situations, the learning system is able to search through the PN to identify the known situation and the actions needed to complete the task. This ability is useful not only for error recovery from known situations, but also for human robot collaboration, where the human unexpectedly helps to complete part of the task. In the case of situations that are both unexpected and unknown, the robot will prompt the human demonstrator to teach how to recover from the error to a known state. By observing the error recovery procedure and automatically extending the PN with the error recovery information, the situation encountered becomes part of the known situations and the robot is able to autonomously recover from the error in the future. This error recovery approach was tested successfully on errors encountered during the three block stacking task.

The ability to learn is essential for robots to function and perform services within a dynamic human environment. Robot programming by demonstration facilitates learning through a human teacher without the need to develop new code for each task that the robot performs. In order for learning to be generalizable, the robot needs to be able to grasp the underlying structure of the task being learned. This requires appropriate knowledge abstraction and representation. The goal of this thesis is to develop a learning by imitation system that abstracts knowledge of human demonstrations of a task and represents the abstracted knowledge in a hierarchical framework. The learning by imitation system is capable of performing both action and object recognition based on video stream data at the lower level of the hierarchy, while the sequence of actions and object states observed is reconstructed at the higher level of the hierarchy in order to form a coherent representation of the task. Furthermore, error recovery capabilities are included in the learning by imitation system to improve robustness to unexpected situations during task execution. The first part of the thesis focuses on motion learning to allow the robot to both recognize the actions for task representation at the higher level of the hierarchy and to perform the actions to imitate the task. In order to efficiently learn actions, the actions are segmented into meaningful atomic units called motion primitives. These motion primitives are then modeled using dynamic movement primitives (DMPs), a dynamical system model that can robustly generate motion trajectories to arbitrary goal positions while maintaining the overall shape of the demonstrated motion trajectory. The DMPs also contain weight parameters that are reflective of the shape of the motion trajectory. These weight parameters are clustered using affinity propagation (AP), an efficient exemplar clustering algorithm, in order to determine groups of similar motion primitives and thus, performing motion recognition. The approach of DMPs combined with APs was experimentally verified on two separate motion data sets for its ability to recognize and generate motion primitives. The second part of the thesis outlines how the task representation is created and used for imitating observed tasks. This includes object and object state recognition using simple computer vision techniques as well as the automatic construction of a Petri net (PN) model to describe an observed task. Tasks are composed of a sequence of actions that have specific pre-conditions, i.e. object states required before the action can be performed, and post-conditions, i.e. object states that result from the action. The PNs inherently encode pre-conditions and post-conditions of a particular event, i.e. action, and can model tasks as a coherent sequence of actions and object states. In addition, PNs are very flexible in modeling a variety of tasks including tasks that involve both sequential and parallel components. The automatic PN creation process has been tested on both a sequential two block stacking task and a three block stacking task involving both sequential and parallel components. The PN provides a meaningful representation of the observed tasks that can be used by a robot to imitate the tasks. Lastly, error recovery capabilities are added to the learning by imitation system in order to allow the robot to readjust the sequence of actions needed during task execution. The error recovery component is able to deal with two types of errors: unexpected, but known situations and unexpected, unknown situations. In the case of unexpected, but known situations, the learning system is able to search through the PN to identify the known situation and the actions needed to complete the task. This ability is useful not only for error recovery from known situations, but also for human robot collaboration, where the human unexpectedly helps to complete part of the task. In the case of situations that are both unexpected and unknown, the robot will prompt the human demonstrator to teach how to recover from the error to a known state. By observing the error recovery procedure and automatically extending the PN with the error recovery information, the situation encountered becomes part of the known situations and the robot is able to autonomously recover from the error in the future. This error recovery approach was tested successfully on errors encountered during the three block stacking task.

La tâche de segmentation et de regroupement en locuteurs (speaker diarization) consiste à identifier "qui parle quand" dans un flux audio sans connaissance a priori du nombre de locuteurs ou de leur temps de parole respectifs. Les systèmes de segmentation et de regroupement en locuteurs sont généralement construits en combinant quatre étapes principales. Premièrement, les régions ne contenant pas de parole telles que les silences, la musique et le bruit sont supprimées par la détection d'activité vocale (VAD). Ensuite, les régions de parole sont divisées en segments homogènes en locuteur par détection des changements de locuteurs, puis regroupées en fonction de l'identité du locuteur. Enfin, les frontières des tours de parole et leurs étiquettes sont affinées avec une étape de re-segmentation. Dans cette thèse, nous proposons d'aborder ces quatre étapes avec des approches fondées sur les réseaux de neurones. Nous formulons d’abord le problème de la segmentation initiale (détection de l’activité vocale et des changements entre locuteurs) et de la re-segmentation finale sous la forme d’un ensemble de problèmes d’étiquetage de séquence, puis nous les résolvons avec des réseaux neuronaux récurrents de type Bi-LSTM (Bidirectional Long Short-Term Memory). Au stade du regroupement des régions de parole, nous proposons d’utiliser l'algorithme de propagation d'affinité à partir de plongements neuronaux de ces tours de parole dans l'espace vectoriel des locuteurs. Des expériences sur un jeu de données télévisées montrent que le regroupement par propagation d'affinité est plus approprié que le regroupement hiérarchique agglomératif lorsqu'il est appliqué à des plongements neuronaux de locuteurs. La segmentation basée sur les réseaux récurrents et la propagation d'affinité sont également combinées et optimisées conjointement pour former une chaîne de regroupement en locuteurs. Comparé à un système dont les modules sont optimisés indépendamment, la nouvelle chaîne de traitements apporte une amélioration significative. De plus, nous proposons d’améliorer l'estimation de la matrice de similarité par des réseaux neuronaux récurrents, puis d’appliquer un partitionnement spectral à partir de cette matrice de similarité améliorée. Le système proposé atteint des performances à l'état de l'art sur la base de données de conversation téléphonique CALLHOME. Enfin, nous formulons le regroupement des tours de parole en mode séquentiel sous la forme d'une tâche supervisée d’étiquetage de séquence et abordons ce problème avec des réseaux récurrents empilés. Pour mieux comprendre le comportement du système, une analyse basée sur une architecture de codeur-décodeur est proposée. Sur des exemples synthétiques, nos systèmes apportent une amélioration significative par rapport aux méthodes de regroupement traditionnelles. / Speaker diarization is the task of determining "who speaks when" in an audio stream that usually contains an unknown amount of speech from an unknown number of speakers. Speaker diarization systems are usually built as the combination of four main stages. First, non-speech regions such as silence, music, and noise are removed by Voice Activity Detection (VAD). Next, speech regions are split into speaker-homogeneous segments by Speaker Change Detection (SCD), later grouped according to the identity of the speaker thanks to unsupervised clustering approaches. Finally, speech turn boundaries and labels are (optionally) refined with a re-segmentation stage. In this thesis, we propose to address these four stages with neural network approaches. We first formulate both the initial segmentation (voice activity detection and speaker change detection) and the final re-segmentation as a set of sequence labeling problems and then address them with Bidirectional Long Short-Term Memory (Bi-LSTM) networks. In the speech turn clustering stage, we propose to use affinity propagation on top of neural speaker embeddings. Experiments on a broadcast TV dataset show that affinity propagation clustering is more suitable than hierarchical agglomerative clustering when applied to neural speaker embeddings. The LSTM-based segmentation and affinity propagation clustering are also combined and jointly optimized to form a speaker diarization pipeline. Compared to the pipeline with independently optimized modules, the new pipeline brings a significant improvement. In addition, we propose to improve the similarity matrix by bidirectional LSTM and then apply spectral clustering on top of the improved similarity matrix. The proposed system achieves state-of-the-art performance in the CALLHOME telephone conversation dataset. Finally, we formulate sequential clustering as a supervised sequence labeling task and address it with stacked RNNs. To better understand its behavior, the analysis is based on a proposed encoder-decoder architecture. Our proposed systems bring a significant improvement compared with traditional clustering methods on toy examples.

In the wake of the Big Data phenomenon, the computing world has seen a number of computational paradigms developed in response to the sudden need to process ever-increasing volumes of data. Most notably, MapReduce has proven quite successful in scaling out an extensible class of simple algorithms to even hundreds of thousands of nodes. However, there are some tasks---even embarrassingly parallelizable ones---that neither MapReduce nor any existing automated parallelization framework is well-equipped to perform. For instance, any computation that (naively) requires consideration of all pairs of inputs becomes prohibitively expensive even when parallelized over a large number of worker nodes. Many of the most desirable methods in machine learning and statistics exhibit these kinds of all-pairs or, more generally, all-tuples computations; accordingly, their application in the Big Data setting may seem beyond hope. However, a new algorithmic strategy inspired by breakthroughs in computational physics has shown great promise for a wide class of computations dubbed generalized N-body problems (GNBPs). This strategy, which involves the simultaneous traversal of multiple space-partitioning trees, has been applied to a succession of well-known learning methods, accelerating each asymptotically and by orders of magnitude. Examples of these include all-k-nearest-neighbors search, k-nearest-neighbors classification, k-means clustering, EM for mixtures of Gaussians, kernel density estimation, kernel discriminant analysis, kernel machines, particle filters, the n-point correlation, and many others. For each of these problems, no overall faster algorithms are known. Further, these dual- and multi-tree algorithms compute either exact results or approximations to within specified error bounds, a rarity amongst fast methods. This dissertation aims to unify a family of GNBPs under a common framework in order to ease implementation and future study. We start by formalizing the problem class and then describe a general algorithm, the generalized fast multipole method (GFMM), capable of solving all problems that fit the class, though with varying degrees of speedup. We then show O(N) and O(log N) theoretical run-time bounds that may be obtained under certain conditions. As a corollary, we derive the tightest known general-dimensional run-time bounds for exact all-nearest-neighbors and several approximated kernel summations. Next, we implement a number of these algorithms in a commercial database, empirically demonstrating dramatic asymptotic speedup over their conventional SQL implementations. Lastly, we implement a fast, parallelized algorithm for kernel discriminant analysis and apply it to a large dataset (40 million points in 4D) from the Sloan Digital Sky Survey, identifying approximately one million quasars with high accuracy. This exceeds the previous largest catalog of quasars in size by a factor of ten and has since been used in a follow-up study to confirm the existence of dark energy.

Les images hyperspectrales suscitent un intérêt croissant depuis une quinzaine d'années. Elles fournissent une information plus détaillée d'une scène et permettent une discrimination plus précise des objets que les images couleur RVB ou multi-spectrales. Bien que les potentialités de la technologie hyperspectrale apparaissent relativement grandes, l'analyse et l'exploitation de ces données restent une tâche difficile et présentent aujourd'hui un défi. Les travaux de cette thèse s'inscrivent dans le cadre de la réduction et de partitionnement des images hyperspectrales de grande dimension spatiale. L'approche proposée se compose de deux étapes : calcul d'attributs et classification des pixels. Une nouvelle approche d'extraction d'attributs à partir des matrices de tri-occurrences définies sur des voisinages cubiques est proposée en tenant compte de l'information spatiale et spectrale. Une étude comparative a été menée afin de tester le pouvoir discriminant de ces nouveaux attributs par rapport aux attributs classiques. Les attributs proposés montrent un large écart discriminant par rapport à ces derniers et par rapport aux signatures spectrales. Concernant la classification, nous nous intéressons ici au partitionnement des images par une approche de classification non supervisée et non paramétrique car elle présente plusieurs avantages: aucune connaissance a priori, partitionnement des images quel que soit le domaine applicatif, adaptabilité au contenu informationnel des images. Une étude comparative des principaux classifieurs semi-supervisés (connaissance du nombre de classes) et non supervisés (C-moyennes, FCM, ISODATA, AP) a montré la supériorité de la méthode de propagation d'affinité (AP). Mais malgré un meilleur taux de classification, cette méthode présente deux inconvénients majeurs: une surestimation du nombre de classes dans sa version non supervisée, et l'impossibilité de l'appliquer sur des images de grande taille (complexité de calcul quadratique). Nous avons proposé une approche qui apporte des solutions à ces deux problèmes. Elle consiste tout d'abord à réduire le nombre d'individus à classer avant l'application de l'AP en agrégeant les pixels à très forte similarité. Pour estimer le nombre de classes, la méthode AP utilise de manière implicite un paramètre de préférence p dont la valeur initiale correspond à la médiane des valeurs de la matrice de similarité. Cette valeur conduisant souvent à une sur-segmentation des images, nous avons introduit une étape permettant d'optimiser ce paramètre en maximisant un critère lié à la variance interclasse. L'approche proposée a été testée avec succès sur des images synthétiques, mono et multi-composantes. Elle a été également appliquée et comparée sur des images hyperspectrales de grande taille spatiale (1000 × 1000 pixels × 62 bandes) avec succès dans le cadre d'une application réelle pour la détection des plantes invasives. / The interest in hyperspectral image data has been constantly increasing during the last years. Indeed, hyperspectral images provide more detailed information about the spectral properties of a scene and allow a more precise discrimination of objects than traditional color images or even multispectral images. High spatial and spectral resolutions of hyperspectral images enable to precisely characterize the information pixel content. Though the potentialities of hyperspectral technology appear to be relatively wide, the analysis and the treatment of these data remain complex. In fact, exploiting such large data sets presents a great challenge. In this thesis, we are mainly interested in the reduction and partitioning of hyperspectral images of high spatial dimension. The proposed approach consists essentially of two steps: features extraction and classification of pixels of an image. A new approach for features extraction based on spatial and spectral tri-occurrences matrices defined on cubic neighborhoods is proposed. A comparative study shows the discrimination power of these new features over conventional ones as well as spectral signatures. Concerning the classification step, we are mainly interested in this thesis to the unsupervised and non-parametric classification approach because it has several advantages: no a priori knowledge, image partitioning for any application domain, and adaptability to the image information content. A comparative study of the most well-known semi-supervised (knowledge of number of classes) and unsupervised non-parametric methods (K-means, FCM, ISODATA, AP) showed the superiority of affinity propagation (AP). Despite its high correct classification rate, affinity propagation has two major drawbacks. Firstly, the number of classes is over-estimated when the preference parameter p value is initialized as the median value of the similarity matrix. Secondly, the partitioning of large size hyperspectral images is hampered by its quadratic computational complexity. Therefore, its application to this data type remains impossible. To overcome these two drawbacks, we propose an approach which consists of reducing the number of pixels to be classified before the application of AP by automatically grouping data points with high similarity. We also introduce a step to optimize the preference parameter value by maximizing a criterion related to the interclass variance, in order to correctly estimate the number of classes. The proposed approach was successfully applied on synthetic images, mono-component and multi-component and showed a consistent discrimination of obtained classes. It was also successfully applied and compared on hyperspectral images of high spatial dimension (1000 × 1000 pixels × 62 bands) in the context of a real application for the detection of invasive and non-invasive vegetation species.