Dissertationen zum Thema „Network data representation“

Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2013.
Cataloged from PDF version of thesis.
Includes bibliographical references (p. 101-105).
Game players express values related to self-expression through various means such as avatar customization, gameplay style, and interactions with other players. Multiplayer online games are now often integrated with social networks that provide social contexts in which player-to-player interactions take place, such as conversation and trading of virtual items. Building upon a theoretical framework based in machine learning and cognitive science, I present results from a novel approach to modeling and analyzing player values in terms of both preferences in avatar customization and patterns in social network use. To facilitate this work, I developed the Steam-Player- Preference Analyzer (Steam-PPA) system, which performs advanced data collection on publicly available social networking profile information. The primary contribution of this thesis is the AIR Toolkit Status Performance Classifier (AIR-SPC), which uses machine learning techniques including k-means clustering, natural language processing (NLP), and support vector machines (SVM) to perform inference on the data. As an initial case study, I use Steam-PPA to collect gameplay and avatar customization information from players in the popular, and commercially successful, multi-player first-person-shooter game Team Fortress 2 (TF2). Next, I use AIR-SPC to analyze the information from profiles on the social network Steam. The upshot is that I use social networking information to predict the likelihood of players customizing their profile in several ways associated with the monetary values of their avatars. In this manner I have developed a computational model of aspects of players' digital social identity capable of predicting specific values in terms of preferences exhibited within a virtual game-world.
by Chong-U Lim.
S.M.

In recent years, deep learning has made a significant impact in various fields – helping to push the state-of-the-art forward in many application domains. Convolutional Neural Networks (CNN) have been applied successfully to tasks such as visual object detection, image super-resolution, and video action recognition while Long Short-term Memory (LSTM) and Transformer networks have been used to solve a variety of challenging tasks in natural language processing. However, these popular deep learning architectures (i.e., CNNs, LSTMs, and Transformers) can only handle data that can be represented as grids or sequences. Due to this limitation, many existing deep learning approaches do not generalize to problem domains where the data is represented as graphs – social networks in social network analysis or molecular graphs in chemoinformatics, for instance. The goal of this thesis is to help bridge the gap by studying deep learning solutions that can handle graph data naturally. In particular, we explore deep learning-based approaches in the following areas. 1. Graph Attention. In the real-world, graphs can be both large – with many complex patterns – and noisy which can pose a problem for effective graph mining. An effective way to deal with this issue is to use an attention-based deep learning model. An attention mechanism allows the model to focus on task-relevant parts of the graph which helps the model make better decisions. We introduce a model for graph classification which uses an attention-guided walk to bias exploration towards more task-relevant parts of the graph. For the task of node classification, we study a different model – one with an attention mechanism which allows each node to select the most task-relevant neighborhood to integrate information from. 2. Graph Representation Learning. Graph representation learning seeks to learn a mapping that embeds nodes, and even entire graphs, as points in a low-dimensional continuous space. The function is optimized such that the geometric distance between objects in the embedding space reflect some sort of similarity based on the structure of the original graph(s). We study the problem of learning time-respecting embeddings for nodes in a dynamic network. 3. Brain Network Discovery. One of the fundamental tasks in functional brain analysis is the task of brain network discovery. The brain is a complex structure which is made up of various brain regions, many of which interact with each other. The objective of brain network discovery is two-fold. First, we wish to partition voxels – from a functional Magnetic Resonance Imaging scan – into functionally and spatially cohesive regions (i.e., nodes). Second, we want to identify the relationships (i.e., edges) between the discovered regions. We introduce a deep learning model which learns to construct a group-cohesive partition of voxels from the scans of multiple individuals in the same group. We then introduce a second model which can recover a hierarchical set of brain regions, allowing us to examine the functional organization of the brain at different levels of granularity. Finally, we propose a model for the problem of unified and group-contrasting edge discovery which aims to discover discriminative brain networks that can help us to better distinguish between samples from different classes.

Mesurer l'activité d'un réseau de télécommunications est essentiel à son opération et sa gestion. Ces mesures sont primordiales pour analyser la performance du réseau et établir son diagnostic. En particulier, effectuer des mesures détaillées sur les flux consiste à calculer des métriques caractérisant les flots de données individuels qui traversent le réseau. Afin de développer des représentations pertinentes de leur trafic, les opérateurs réseau doivent en sélectionner les caractéristiques appropriées et doivent attentivement relier leur coût d'extraction à leur expressivité pour les tâches considérées. Dans cette thèse, nous proposons de nouvelles méthodologies pour extraire des représentations pertinentes du trafic. Particulièrement, nous postulons que l'apprentissage automatique (Machine Learning) peut améliorer les systèmes de mesures, grâce à sa capacité à apprendre des motifs adéquats issus des données, ce afin de fournir des prédictions sur des caractéristiques du trafic.La première contribution de cette thèse est un cadre de développement permettant aux systèmes de mesures basés sur des sketches d'exploiter la nature biaisée du trafic réseau. Spécifiquement, nous proposons une nouvelle représentation de ces structures de données, qui tire profit de de la sous-utilisation des sketches, réduisant ainsi l'empreinte mémoire des mesures par flux en n'enregistrant que les compteurs utiles. La deuxième contribution est un système de surveillance réseau assisté par un modèle d'apprentissage automatique, en intégrant un classificateur de trafic. En particulier, nous isolons les flux les plus larges dans le plan de données (data plane), avant de les traiter séparément avec des structures de données dédiées pour différents cas d'usage. Les dernières contributions de cette thèse abordent la conception d'un pipeline d'apprentissage profond (Deep Learning) pour les mesures de réseau, afin d'extraire de riches représentations des données de trafic permettant l'analyse du réseau. Nous puisons dans les récentes avancées en modélisation de séquences afin d'apprendre ces représentations depuis des données de trafic catégorielles et numériques. Ces représentations alimentent la résolution de tâches complexes telles que la réconciliation de données issues d'un flux de clics enregistré par un fournisseur d'accès à internet, ou la prédiction du mouvement d'un terminal dans un réseau Wi-Fi. Enfin, nous présentons une étude empirique des affinités entre tâches candidates à l'apprentissage multitâches, afin d'évaluer lorsque deux tâches bénéficieraient d'un apprentissage conjoint
Measurements are essential to operate and manage computer networks, as they are critical to analyze performance and establish diagnosis. In particular, per-flow monitoring consists in computing metrics that characterize the individual data streams traversing the network. To develop relevant traffic representations, operators need to select suitable flow characteristics and carefully relate their cost of extraction with their expressiveness for the downstream tasks considered. In this thesis, we propose novel methodologies to extract appropriate traffic representations. In particular, we posit that Machine Learning can enhance measurement systems, thanks to its ability to learn patterns from data, in order to provide predictions of pertinent traffic characteristics.The first contribution of this thesis is a framework for sketch-based measurements systems to exploit the skewed nature of network traffic. Specifically, we propose a novel data structure representation that leverages sketches' under-utilization, reducing per-flow measurements memory footprint by storing only relevant counters. The second contribution is a Machine Learning-assisted monitoring system that integrates a lightweight traffic classifier. In particular, we segregate large and small flows in the data plane, before processing them separately with dedicated data structures for various use cases. The last contributions address the design of a unified Deep Learning measurement pipeline that extracts rich representations from traffic data for network analysis. We first draw from recent advances in sequence modeling to learn representations from both numerical and categorical traffic data. These representations serve as input to solve complex networking tasks such as clickstream identification and mobile terminal movement prediction in WLAN. Finally, we present an empirical study of task affinity to assess when two tasks would benefit from being learned together

Network reconstruction is the process of recovering a unique structured representation of some dynamic system using input-output data and some additional knowledge about the structure of the system. Many network reconstruction algorithms have been proposed in recent years, most dealing with the reconstruction of strictly proper networks (i.e., networks that require delays in all dynamics between measured variables). However, no reconstruction technique presently exists capable of recovering both the structure and dynamics of networks where links are proper (delays in dynamics are not required) and not necessarily strictly proper.The ultimate objective of this dissertation is to develop algorithms capable of reconstructing proper networks, and this objective will be addressed in three parts. The first part lays the foundation for the theory of mathematical representations of proper networks, including an exposition on when such networks are well-posed (i.e., physically realizable). The second part studies the notions of abstractions of a network, which are other networks that preserve certain properties of the original network but contain less structural information. As such, abstractions require less a priori information to reconstruct from data than the original network, which allows previously-unsolvable problems to become solvable. The third part addresses our original objective and presents reconstruction algorithms to recover proper networks in both the time domain and in the frequency domain.

This work presents an investigation of tailoring Network Representation Learning (NRL) for an application in the Financial Industry. NRL approaches are data-driven models that learn how to encode graph structures into low-dimensional vector spaces, which can be further exploited by downstream Machine Learning applications. They can potentially bring a lot of benefits in the Financial Industry since they extract in an automatic way features that can provide useful input regarding graph structures, called embeddings. Financial transactions can be represented as a network, and through NRL, it is possible to extract embeddings that reflect the intrinsic inter-connected nature of economic relationships. Such embeddings can be used for several purposes, among which Anomaly Detection to fight financial crime.This work provides a qualitative analysis over state-of-the-art NRL models, which identifies Graph Convolutional Network (ConvGNN) as the most suitable category of approaches for Financial Industry but with a certain need for further improvement. Financial Industry poses additional challenges when modelling a NRL solution. Despite the need of having a scalable solution to handle real-world graph with considerable dimensions, it is necessary to take into consideration several characteristics: transactions graphs are inherently dynamic since every day new transactions are executed and nodes can be heterogeneous. Besides, everything is further complicated by the need to have updated information in (near) real-time due to the sensitivity of the application domain. For these reasons, GraphSAGE has been considered as a base for the experiments, which is an inductive ConvGNN model. Two variants of GraphSAGE are presented: a dynamic variant whose weights evolve accordingly with the input sequence of graph snapshots, and a variant specifically meant to handle bipartite graphs. These variants have been evaluated by applying them to real-world data and leveraging the generated embeddings to perform Anomaly Detection. The experiments demonstrate that leveraging these variants leads toimagecomparable results with other state-of-the-art approaches, but having the advantage of being suitable to handle real-world financial data sets.
Detta arbete presenterar en undersökning av tillämpningar av Network Representation Learning (NRL) inom den finansiella industrin. Metoder inom NRL möjliggör datadriven kondensering av grafstrukturer till lågdimensionella och lätthanterliga vektorer.Dessa vektorer kan sedan användas i andra maskininlärningsuppgifter. Närmare bestämt, kan metoder inom NRL underlätta hantering av och informantionsutvinning ur beräkningsintensiva och storskaliga grafer inom den finansiella sektorn, till exempel avvikelsehantering bland finansiella transaktioner. Arbetet med data av denna typ försvåras av det faktum att transaktionsgrafer är dynamiska och i konstant förändring. Utöver detta kan noderna, dvs transaktionspunkterna, vara vitt skilda eller med andra ord härstamma från olika fördelningar.I detta arbete har Graph Convolutional Network (ConvGNN) ansetts till den mest lämpliga lösningen för nämnda tillämpningar riktade mot upptäckt av avvikelser i transaktioner. GraphSAGE har använts som utgångspunkt för experimenten i två olika varianter: en dynamisk version där vikterna uppdateras allteftersom nya transaktionssekvenser matas in, och en variant avsedd särskilt för bipartita (tvådelade) grafer. Dessa varianter har utvärderats genom användning av faktiska datamängder med avvikelsehantering som slutmål.

In the artificial intelligence community there is a growing consensus that real world data is naturally represented as graphs because they can easily incorporate complexity at several levels, e.g. hierarchies or time dependencies. In this context, this thesis studies two main branches for structured data. In the first part we explore how state-of-the-art machine learning methods can be extended to graph modeled data provided that one is able to represent graphs in vector spaces. Such extensions can be applied to analyze several kinds of real-world data and tackle different problems. Here we study the following problems: a) understand the relational nature and evolution of websites which belong to different categories (e-commerce, academic (p.a.) and encyclopedic (forum)); b) model tennis players scores based on different game surfaces and tournaments in order to predict matches results; c) analyze preter- m-infants motion patterns able to characterize possible neuro degenerative disorders and d) build an academic collaboration recommender system able to model academic groups and individual research interest while suggesting possible researchers to connect with, topics of interest and representative publications to external users. In the second part we focus on graphs inference methods from data which present two main challenges: missing data and non-stationary time dependency. In particular, we study the problem of inferring Gaussian Graphical Models in the following settings: a) inference of Gaussian Graphical Models when data are missing or latent in the context of multiclass or temporal network inference and b) inference of time-varying Gaussian Graphical Models when data is multivariate and non-stationary. Such methods have a natural application in the composition of an optimized stock markets portfolio. Overall this work sheds light on how to acknowledge the intrinsic structure of data with the aim of building statistical models that are able to capture the actual complexity of the real world.

Ces modèles combinent à des réseaux sémantiques des bases de connaissances formées de règles. Les données sont représentées par des graphes sans circuit, ordonnés ou semi-ordonnés, ainsi que par des grammaires de graphes. La recherche de la réponse à une question se ramène à la recherche de morphismes entre structures. Les réprésentations sont construites automatiquement par l'appel à des règles de réécriture de graphes

This thesis proposes a collaboration framework for the Web of Things based on the concepts of Service-oriented Architecture and integrated with semantic web technologies to offer new possibilities in terms of efficient asset management during operations requiring multi-actor collaboration. The motivation for the project comes from the rise in disasters where effective cross-organisation collaboration can increase the efficiency of critical information dissemination. Organisational boundaries of participants as well as their IT capability and trust issues hinders the deployment of a multi-party collaboration framework, thereby preventing timely dissemination of critical data. In order to tackle some of these issues, this thesis proposes a new collaboration framework consisting of a resource-based data model, resource-oriented access control mechanism and semantic technologies utilising the Semantic Sensor Network Ontology that can be used simultaneously by multiple actors without impacting each other’s networks and thus increase the efficiency of disaster management and relief operations. The generic design of the framework enables future extensions, thus enabling its exploitation across many application domains. The performance of the framework is evaluated in two areas: the capability of the access control mechanism to scale with increasing number of devices, and the capability of the semantic annotation process to increase in efficiency as more information is provided. The results demonstrate that the proposed framework is fit for purpose.

The neural net computer simulations which will be presented here are based on the acceptance of a set of assumptions that for the last twenty years have been expressed in the fields of information processing, neurophysiology and cognitive sciences. First of all, neural networks and their dynamical behaviors in terms of attractors is the natural way adopted by the brain to encode information. Any information item to be stored in the neural net should be coded in some way or another in one of the dynamical attractors of the brain and retrieved by stimulating the net so as to trap its dynamics in the desired item's basin of attraction. The second view shared by neural net researchers is to base the learning of the synaptic matrix on a local Hebbian mechanism. The last assumption is the presence of chaos and the benefit gained by its presence. Chaos, although very simply produced, inherently possesses an infinite amount of cyclic regimes that can be exploited for coding information. Moreover, the network randomly wanders around these unstable regimes in a spontaneous way, thus rapidly proposing alternative responses to external stimuli and being able to easily switch from one of these potential attractors to another in response to any coming stimulus.

In this thesis, it is shown experimentally that the more information is to be stored in robust cyclic attractors, the more chaos appears as a regime in the back, erratically itinerating among brief appearances of these attractors. Chaos does not appear to be the cause but the consequence of the learning. However, it appears as an helpful consequence that widens the net's encoding capacity. To learn the information to be stored, an unsupervised Hebbian learning algorithm is introduced. By leaving the semantics of the attractors to be associated with the feeding data unprescribed, promising results have been obtained in term of storing capacity.
Doctorat en sciences appliquées
info:eu-repo/semantics/nonPublished

Today, an increasing amount of the functionality traditionally associated with stationary computers is moving into mobile devices. Furthermore, the number of applications that retrieve data via networks is increasing in view of the recent growth of video streaming to the browsers, further emphasizing the Quality of Experience (QoE) requirements of mobile users today. Obviously, QoE demands are not necessarily connected to the fact that the link is mobile, which puts significant QoS demands onto the mobile systems involved. Consequently, this requires mobile systems to be flexible and adaptable to meet the QoS demands and cope with dynamic operating environments. Additionally, the rapid migration towards wireless connectivity and the abundance of mobile devices has put even greater strain on current wireless access technology designs. The frequency spectrum is a limited resource and must be efficiently utilized to conserve capacity and avoid overcrowding, particularly in densely populated areas. Hence, new wireless technologies and innovative architectural designs are needed to manage and to govern the wireless domain. The thesis is about combining the potential of Dynamic Spectrum Access (DSA) provided by Cognitive Radio (CR) with the scalability and fault tolerance capabilities demonstrated by Peer-to-Peer (P2P) systems. By combining these two technologies, we show that we can improve the resource utilization in crowded metropolitan areas to ensure service continuation between local mobile devices with minimal infrastructure requirements. The aim is to optimize the communication between Cognitive Radio Devices (CRD) in a Cognitive Radio Network (CRN) according to end-to-end (e2e) goals and user preferences.

La thèse porte sur le développement d'architectures neuronales profondes permettant d'analyser des contenus textuels ou visuels, ou la combinaison des deux. De manière générale, le travail tire parti de la capacité des réseaux de neurones à apprendre des représentations abstraites. Les principales contributions de la thèse sont les suivantes: 1) Réseaux récurrents pour la compréhension de la parole: différentes architectures de réseaux sont comparées pour cette tâche sur leurs facultés à modéliser les observations ainsi que les dépendances sur les étiquettes à prédire. 2) Prédiction d’image et de mouvement : nous proposons une architecture permettant d'apprendre une représentation d'une image représentant une action humaine afin de prédire l'évolution du mouvement dans une vidéo ; l'originalité du modèle proposé réside dans sa capacité à prédire des images à une distance arbitraire dans une vidéo. 3) Encodeurs bidirectionnels multimodaux : le résultat majeur de la thèse concerne la proposition d'un réseau bidirectionnel permettant de traduire une modalité en une autre, offrant ainsi la possibilité de représenter conjointement plusieurs modalités. L'approche été étudiée principalement en structuration de collections de vidéos, dons le cadre d'évaluations internationales où l'approche proposée s'est imposée comme l'état de l'art. 4) Réseaux adverses pour la fusion multimodale: la thèse propose d'utiliser les architectures génératives adverses pour apprendre des représentations multimodales en offrant la possibilité de visualiser les représentations dans l'espace des images
In this dissertation, the thesis that deep neural networks are suited for analysis of visual, textual and fused visual and textual content is discussed. This work evaluates the ability of deep neural networks to learn automatic multimodal representations in either unsupervised or supervised manners and brings the following main contributions:1) Recurrent neural networks for spoken language understanding (slot filling): different architectures are compared for this task with the aim of modeling both the input context and output label dependencies.2) Action prediction from single images: we propose an architecture that allow us to predict human actions from a single image. The architecture is evaluated on videos, by utilizing solely one frame as input.3) Bidirectional multimodal encoders: the main contribution of this thesis consists of neural architecture that translates from one modality to the other and conversely and offers and improved multimodal representation space where the initially disjoint representations can translated and fused. This enables for improved multimodal fusion of multiple modalities. The architecture was extensively studied an evaluated in international benchmarks within the task of video hyperlinking where it defined the state of the art today.4) Generative adversarial networks for multimodal fusion: continuing on the topic of multimodal fusion, we evaluate the possibility of using conditional generative adversarial networks to lean multimodal representations in addition to providing multimodal representations, generative adversarial networks permit to visualize the learned model directly in the image domain

Biological neuronal networks are a key object of study in the field of computational neuroscience, and recent studies have also shown their potential applicability within artificial intelligence and robotics [1]. They come in many shapes and forms, and a well known and widely studied example is the liquid state machine from 2004 [2]. In 2019, a novel and simple connectivity rule was presented with the introduction of the SpreizerNet [3]. The connectivity of the SpreizerNet is governed by a type of gradient noise known as Perlin noise, and as such the connectivity is anisotropic but correlated. The spiking activity produced in the SpreizerNet is possibly functionally relevant, e.g. for motor control or classification of input stimuli. In 2020, it was shown to be useful for motor control [4]. In this Master’s thesis, we inquire if the spiking activity of the SpreizerNet is functionally relevant in the context of stimulus representation. We investigate how input stimulus from the MNIST handwritten digits dataset is represented in the spatio-temporal activity sequences produced by the SpreizerNet, and whether this representation is sufficient for separation. Furthermore, we consider how the parameters governing the local structure of connectivity impacts representation and separation. We find that (1) the SpreizerNet separates input stimulus at the initial stage after stimulus and (2) that separation decreases with time when the activity from dissimilar inputs becomes unified.
Biologiska neurala nätverk är ett centralt studieobjekt inom beräkningsneurovetenskapen, och nyliga studier har även visat deras potentiella applicerbarhet inom artificiell intelligens och robotik [1]. De kan formuleras på många olika sätt, och ett välkänt och vida studerat exempel är liquid state machine från 2004 [2]. 2019 presenterades en ny och enkel kopplingsregel i SpreizerNätverket [3]. Kopplingarna i SpreizerNätverket styrs av en typ av gradientbrus vid namn Perlinbrus, och som sådana är de anisotropiska men korrelerade. Spikdatan som genereras av SpreizerNätverket är möjligtvis betydelsefull för funktion, till exempel för motorisk kontroll eller separation av stimuli. 2020 visade Michaelis m. fl. att spikdatan var relevant för motorisk kontroll [4]. I denna masteruppsats frågar vi oss om spikdatan är funktionellt relevant för stimulusrepresentation. Vi undersöker hur stimulus från MNIST handwritten digits -datasetet representeras i de spatiotemporella aktivitetssekvenserna som genereras i SpreizerNätverket, och huruvida denna representation är tillräcklig för separation.Vidare betraktar vi hur parametrarna som styr den lokala kopplingsstrukturen påverkar representation och separation. Vi visar att (1) SpreizerNätverket separerar stimuli i ett initialt skede efter stimuli och (2) att separationen minskar med tid när aktiviteten från olika stimuli blir enhetlig.

This thesis addresses the problem of using distributed sensing for automatically inferring a representation of the environment, i.e. a map, that can be useful for the self-calibration of intelligence systems, such as sensor networks. The information recovered by such a process allows typical applications such as data collection and navigation to proceed without labour intensive input from a human technician. Simplifying the deployment of large scale sensor networks and other intelligent systems will effectively reduce their cost and improve their widespread availability and hence aid their practical application to tasks such as the monitoring of carbon emissions and greenhouse gases. In our research we focus on algorithms and techniques for recovering two types of information from the immediate environment: topology information that indicates physical connectivity between regions of interest from the point of view of a navigating agent; and a probability distribution function (PDF) describing the position of components of the intelligent system. We consider situations where data is collected from systems that comprise of: a number of stationary network components; stationary network components augmented with a mobile robot; or a mobile robot only. Our approaches are, for the most part, based on statistical methods that employ stochastic sampling techniques to provide approximate solutions to problems for which computing the optimal or exact solution is intractable. Numerical simulations and experiments conducted on hardware suggest that this research has promising real world applications in the area of sensor network self-configuration.
Ce thèse s'adresse au problème de l'emploi de la détection dispersée pour déduire automatiquement une représentation de l'environnement, c'est-à-dire une carte, qui peut servir dans l'autocalibrage des systèmes intelligents tels que les réseaux des capteurs. L'information récupérée par un tel processus permet aux applications typiques telle que la collecte des données et la navigation de continuer sans une contribution de main d'œuvre de la part d'un technicien humain. Simplifier la répartition en grand des réseaux de capteurs et d'autres systèmes intelligents réduira effectivement leur coût et améliora leur disponibilité répandue, donc il facilitera leur application pratique aux tâches comme le contrôle des émissions de carbone et les gaz à effet de serre.Dans nos recherches nous nous concentrons sur les algorithmes et les techniques pour récupérer deux types d'information de l'environnement immédiat : l'information topologique qui indique la connectivité physique entre les régions d'intérêt du point de vue d'un agent navigateur; et une fonction de dispersion de probabilité (PDF) qui décrit la position des élément du système intelligent. Nous considérons les situation où les données se recueillent des systèmes composés de: plusieurs éléments fixes du réseau; des éléments fixes du réseau augmentés d'un robot mobile; un robot mobile seulement. Nos approches sont, pour la plupart, fondées sur des méthodes statistiques qui emploient des techniques stochastiques d'échantillonnage pour fournir des solutions approximatives aux problèmes dont le calcul d'une solution exacte ou optimale reste réfractaire. Les simulations numériques et les expériences exécutées au matériel suggèrent que ces recherches promettent des applications actuelles et pratiques dans le domaine d'autocalibrage des réseaux de capteurs.

Les progrès des technologies de séquençage génomique ont conduit à une croissance exponentielle du nombre de séquences protéiques dans les bases de données publiques. Il est important d’exploiter cette énorme quantité de données pour décrire les êtres vivants au niveau moléculaire, et ainsi mieux comprendre les processus pathologiques humains et accélérer la découverte de médicaments. Une condition préalable, cependant, est que toutes ces protéines soient annotées avec des propriétés fonctionnelles telles que les numéros de commission enzymatique (EC) ou les termes de l’ontologie « Gene Ontology » (GO). Aujourd’hui, seule une petite fraction des protéines est annotée fonctionnellement et examinée manuellement par des experts car c’est une tâche coûteuse, lente et chronophage. Le développement d’outils d’annotation automatique des protéines est la voie à suivre pour réduire l’écart entre séquences protéiques annotées et non annotées et produire des annotations fiables. Aucun outil déjà développés n’est pleinement satisfaisant. Seuls quelques-uns utilisent les approches à base de graphes et tiennent compte de la composition en domaines des protéines qui sont des régions conservées à travers les séquences protéiques de la même famille. Dans cette thèse, nous concevons et évaluons des approches à base de graphes pour effectuer l’annotation automatique des fonctions protéiques et nous explorons l’impact de l’architecture en domaines sur les fonctions protéiques. La première partie est consacrée à l’annotation de la fonction des protéines à l’aide d’un graphe de similarité de domaines et de techniques de propagation d’étiquettes (ou de labels) améliorées. Tout d’abord, nous présentons GrAPFI (« Graph-based Automatic Protein Function Inference ») pour l’annotation automatique des protéines par les numéros EC et par des termes GO. Nous validons les performances de GrAPFI en utilisant six protéomes de référence dans UniprotKB/SwissProt, et nous comparons les résultats de GrAPFI avec des outils de référence. Nous avons constaté que GrAPFI atteint une meilleure précision et une couverture comparable ou meilleure par rapport aux outils existants. La deuxième partie traite de l’apprentissage de représentations pour les entités biologiques. Au début, nous nous concentrons sur les techniques de plongement lexical (« word embedding »), utilisant les réseaux neuronaux. Nous formulons la tâche d’annotation comme une tâche de classification de textes. Nous construisons un corpus de protéines sous forme de phrases composées de leurs domaines respectifs et nous apprenons une représentation vectorielle à dimension fixe. Ensuite, nous portons notre attention sur l’apprentissage de représentations à partir de graphes de connaissances intégrant différentes sources de données liées aux protéines et à leurs fonctions. Nous formulons le problème d’annotation fonctionnelle des protéines comme une tâche de prédiction de liens entre une protéine et un terme GO. Nous proposons Prot-A-GAN, un modèle d’apprentissage automatique inspiré des réseaux antagonistes génératifs (GAN pour « Generative Adversarial Network »). Nous observons que Prot-A-GAN fonctionne avec des résultats prometteurs pour associer des fonctions appropriées aux protéines requêtes. En conclusion, cette thèse revisite le problème crucial de l’annotation automatique des fonctions protéiques à grande échelle en utilisant des techniques innovantes d’intelligence artificielle. Elle ouvre de larges perspectives, notamment pour l’utilisation des graphes de connaissances, disponibles aujourd’hui dans de nombreux domaines autres que l’annotation de protéines grâce aux progrès de la science des données
Due to the recent advancement in genomic sequencing technologies, the number of protein entries in public databases is growing exponentially. It is important to harness this huge amount of data to describe living things at the molecular level, which is essential for understanding human disease processes and accelerating drug discovery. A prerequisite, however, is that all of these proteins be annotated with functional properties such as Enzyme Commission (EC) numbers and Gene Ontology (GO) terms. Today, only a small fraction of the proteins is functionally annotated and reviewed by expert curators because it is expensive, slow and time-consuming. Developing automatic protein function annotation tools is the way forward to reduce the gap between the annotated and unannotated proteins and to predict reliable annotations for unknown proteins. Many tools of this type already exist, but none of them are fully satisfactory. We observed that only few consider graph-based approaches and the domain composition of proteins. Indeed, domains are conserved regions across protein sequences of the same family. In this thesis, we design and evaluate graph-based approaches to perform automatic protein function annotation and we explore the impact of domain architecture on protein functions. The first part is dedicated to protein function annotation using domain similarity graph and neighborhood-based label propagation technique. We present GrAPFI (Graph-based Automatic Protein Function Inference) for automatically annotating proteins with enzymatic functions (EC numbers) and GO terms from a protein-domain similarity graph. We validate the performance of GrAPFI using six reference proteomes from UniprotKB/SwissProt and compare GrAPFI results with state-of-the-art EC prediction approaches. We find that GrAPFI achieves better accuracy and comparable or better coverage. The second part of the dissertation deals with learning representation for biological entities. At the beginning, we focus on neural network-based word embedding technique. We formulate the annotation task as a text classification task. We build a corpus of proteins as sentences composed of respective domains and learn fixed dimensional vector representation for proteins. Then, we focus on learning representation from heterogeneous biological network. We build knowledge graph integrating different sources of information related to proteins and their functions. We formulate the problem of function annotation as a link prediction task between proteins and GO terms. We propose Prot-A-GAN, a machine-learning model inspired by Generative Adversarial Network (GAN) to learn vector representation of biological entities from protein knowledge graph. We observe that Prot-A-GAN works with promising results to associate ap- propriate functions with query proteins. In conclusion, this thesis revisits the crucial problem of large-scale automatic protein function annotation in the light of innovative techniques of artificial intelligence. It opens up wide perspectives, in particular for the use of knowledge graphs, which are today available in many fields other than protein annotation thanks to the progress of data science

This thesis presents a study of alignment-free methods for genetic sequence comparison. By using representations based on k-mers – short subsequences of length k - sequence similarity can be measured rapidly and accurately by calculating the distance between these paired representations. This research utilises and adapts conventional methods from information retrieval to generate novel representations for k-mers and sequence fragments. Precision was further improved through the use of machine learning approaches - especially neural networks - to learn relationships between k-mers and to generate enhanced sequence representations. These approaches have applications in large scale sequence comparison, especially in the analysis of metagenomic samples.

Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Civil and Environmental Engineering, 2000.
Includes bibliographical references (leaves 139-141).
In this thesis, we develop methods for the following problems: the representation of discrete-time dynamic data, and the computation of fastest paths in continuous-time dynamic networks. We apply these methods for the following application problems: storage and communication of discrete-time dynamic transportation network data, and computation of fastest paths in traffic networks with signalized intersections. These problems are at the heart of realtime management of transportation networks equipped with information technologies. We propose a representation (called the bit-stream representation) method for nondecreasing discrete-time dynamic functions as a stream of 0 and 1 bits. We show that this representation is 12 times less memory consuming than the classical representation for such data, where the function value at each time-instant is stored as an L-bit integer. We exploit this representation to efficiently store and represent travel-time data in discrete-time dynamic transportation networks. Since the bit-stream representation requires lesser memory space, it also leads to lesser communication-time requirements for applications involving communication of such data. We adapt a classical dynamic one-to-all fastest path to work on bit-streams and show that this leads to savings of up to 16-times in over-all communication and computation times. This holds the potential to impact the development of efficient high performance computer implementations of dynamic shortest path algorithms in time-dependent networks. We model travel-times in dynamic networks using piece-wise linear functions. We consider the one-to-all fastest path problem in a class of continuous-time dynamic networks. We present two algorithms: Algorithm OR, that is based on a conceptual algorithm known in the literature; and Algorithm IOT-C, that is developed in this thesis. We implement the two algorithms, and show that Algorithm IOT-C outperforms Algorithm OR by a factor of two. We study the application problem of computing fastest paths in traffic networks with signalized intersections. We use a piece-wise linear link travel-time dynamic network model to address this problem, and demonstrate that this model is more accurate than discrete-time models proposed in the literature. Some of the implemented algorithms are applied to solve variants of the one-to-all fastest path problem in traffic networks with signalized intersections, and study the computational performance of these implementations.
by Vinay M. Yadappanavar.
S.M.

Le contenu visuel se concentre souvent sur les humains. L’analyse automatique des humains à partir de données visuelles revêt donc une grande importance pour de nombreuses applications. Le but de cette thèse est d’apprendre des représentations visuelles pour l’analyse des humains. Un accent particulier est mis sur deux domaines étroitement liés de la vision artificielle : l’analyse du corps humain et la reconnaissance des actions. En résumé, nos contributions sont les suivantes : (i) nous générons des données synthétiques photoréalistes de personnes permettant l’entraînement de CNNs pour l’analyse du corps humain, (ii) nous proposons une architecture multitâche permettant d’obtenir une représentation volumétrique du corps à partir d’une seule image, (iii) nous étudions les avantages des convolutions temporelles à long terme pour la reconnaissance de l’action humaine à l’aide de CNNs 3D, (iv) nous incorporons une fonction de coût de similarité des vidéos multi-vues pour concevoir des représentations invariantes au changement de vue
The focus of visual content is often people. Automatic analysis of people from visual data is therefore of great importance for numerous applications in content search, autonomous driving, surveillance, health care, and entertainment. The goal of this thesis is to learn visual representations for human understanding. Particular emphasis is given to two closely related areas of computer vision: human body analysis and human action recognition. In summary, our contributions are the following: (i) we generate photo-realistic synthetic data for people that allows training CNNs for human body analysis, (ii) we propose a multi-task architecture to recover a volumetric body shape from a single image, (iii) we study the benefits of long-term temporal convolutions for human action recognition using 3D CNNs, (iv) we incorporate similarity training in multi-view videos to design view-independent representations for action recognition

In this work, a Representative Volume Element (RVE) generator based on the distance fields of arbitrary shaped inclusion packing is used to obtain morphologies of open-foam materials. When the inclusions are spherical, the tessellations of the resultant packing creates morphologies that are similar to physical foam samples in terms of their face-to-pore ratio, edge-to-face ratio and strut length distribution among others. Functions that combine the distance fields can be used to obtain the tessellations along with the necessary variations in the strut geometry and extract these open-foam morphologies. It is also possible to replace the inclusion packing with a predefined set of inclusions that are directly extracted from CT-scan based images.The use of discrete level-set functions results in steep discontinuities in the distance function derivatives. A multiple level-set based approach is presented that can appropriately capture the sharp edges of the open-foam struts from the resultant distance fields. Such an approach can circumvent the discontinuities presented by the distance fields which might lead to spurious stress concentrations in a material behavior analysis.The individual cells are then extracted as inclusion surfaces based on said combinations of the distance functions and their modifications. These surfaces can be joined together to obtain the final geometry of the open-foam morphologies. The physical attributes of the extracted geometries are compared to the experimental data. A statistical comparison is presented outlining the various features. The study is extended to morphologies that have been extracted using CT-scan images. With the help of mesh optimization tools, surface triangulations can be obtained, merged and developed as finite element (FE) models. The models are ready to use in a multi-scale study to obtain the homogenized material behavior. The upscaling can help assess the practical applications of these models by comparing with experimental data of physical samples. The material behavior of the RVEs are also compared with the experimental observations. To increase the computational efficiency of the study, a neural network based surrogate is presented that can replace the micro-scale boundary value problem (BVP) in the multi-scale analysis. The neural networks are built with the help of modules that are specifically designed to predict history dependent behavior and are called Recurrent Neural Networks (RNN). The surrogates are trained to take into account the randomness of the loading that complex material undergo during any given material behavior analysis.
Dans ce travail, un générateur de volumes élémentaires représentatifs (VER) basé sur les champs de distance d'un agrégat d'inclusions de forme arbitraire est développé dans le cadre de matériaux moussés à structure ouverte. Lorsque les inclusions sont sphériques, la tessellation de l'agrégat résulte en des morphologies similaires aux échantillons de mousse physique en termes de rapports des nombres de face par pores et de bords par faces, ainsi que de la distribution de la longueur des entretoises, entre autres. Les fonctions qui combinent les champs de distance peuvent être utilisées pour obtenir des tesselations avec les variations nécessaires aux géométries des entretoises et extraire ces morphologies de mousse ouverte. Il est également possible de remplacer l'agrégat d'inclusions par un ensemble prédéfini d'inclusions qui sont directement extraites d'images tomographiques.L'utilisation de fonctions de niveaux discrètes entraîne de fortes discontinuités dans les dérivées des champs de distance. Une approche basée sur des ensembles de niveaux multiples est présentée qui peut capturer de manière appropriée les arêtes vives des entretoises des mousses ouvertes à partir des champs de distance résultants. Une telle approche peut contourner les discontinuités présentées par les champs de distance qui pourraient conduire à des concentrations de contraintes parasites dans une analyse ducomportement des matériaux.Les pores individuels sont ensuite extraits en tant que surfaces d'inclusions sur la base desdites combinaisons des fonctions de distance et de leurs modifications. Ces surfaces peuvent être réunies pour obtenir la géométrie finale des morphologies de mousse ouverte. Les attributs physiques des géométries extraites sont comparés aux données expérimentales. Une comparaison statistique est présentée décrivant les différentes caractéristiques. L'étude est étendue aux morphologies qui ont été extraites à l'aide d'images tomographiques.À l'aide d'outils d'optimisation de maillage, les triangulations des surfaces peuvent être obtenues, fusionnées et développées sous forme de modèles d'éléments finis (FE). Les modèles sont prêts à être utilisés dans une étude multi-échelle pour obtenir le comportement homogénéisé du matériau. La mise à l'échelle peut aider à évaluer les applications pratiques de ces modèles en les comparant aux données expérimentales d'échantillons physiques. Le comportement des matériaux des VERs est également comparé aux observations expérimentales.Pour augmenter l'efficacité de calcul de l'étude, un modèle de substitution basé sur un réseau neuronal est présenté. Ce modèle peut remplacer le problème aux valeurs limites à l'échelle micro dans une analyse multi-échelle. Les réseaux de neurones sont construits à l'aide de modules spécialement conçus pour prédire le comportement dépendant de l'histoire et sont appelés réseaux de neurones récurrents (RNN). Les modèles de substitution sont entrainés pour prendre en compte le caractère aléatoire du chargement que subit un matériau complexe lors d'une analyse de comportement d'un matériau.
Doctorat en Sciences de l'ingénieur et technologie
info:eu-repo/semantics/nonPublished

Aprendizado semissupervisionado (ASS) é o nome dado ao paradigma de aprendizado de máquina que considera tanto dados rotulados como dados não rotulados. Embora seja considerado frequentemente como um meio termo entre os paradigmas supervisionado e não supervisionado, esse paradigma é geralmente aplicado a tarefas preditivas ou descritivas. Na tarefa preditiva de classificação, p. ex., o objetivo é rotular dados não rotulados de acordo com os rótulos dos dados rotulados. Nesse caso, enquanto que os dados não rotulados descrevem as distribuições dos dados e mediam a propagação dos rótulos, os itens de dados rotulados semeiam a propagação de rótulos e guiam-na à estabilidade. No entanto, dados são gerados tipicamente não rotulados e sua rotulação requer o envolvimento de especialistas no domínio, rotulando-os manualmente. Dificuldades na visualização de grandes volumes de dados, bem como o custo associado ao envolvimento do especialista, são desafios que podem restringir o desempenho dessa tarefa. Por- tanto, o destacamento automático de bons candidatos a dados rotulados, doravante denominados indivíduos representativos, é uma tarefa de grande importância, e pode proporcionar uma boa relação entre o custo com especialista e o desempenho do aprendizado. Dentre as abordagens de ASS discriminadas na literatura, nosso interesse de estudo se concentra na abordagem baseada em redes, onde conjuntos de dados são representados relacionalmente, através da abstração gráfica. Logo, o presente trabalho tem como objetivo explorar a influência dos nós rotulados no desempenho do ASS baseado em redes, i.e., estudar a caracterização de nós representativos, como a estrutura da rede pode realçá-los, o ganho de desempenho de ASS proporcionado pela rotulação manual dos mesmos, e aspectos filosóficos relacionados. Em relação à caracterização, critérios de caracterização de nós centrais em redes são estudados considerando-se redes com estruturas modulares bem definidas. Contraintuitivamente, nós bastantes conectados (hubs) não são muito representativos. Nós razoavelmente conectados em vizinhanças pouco conectadas, por outro lado, são; estritamente local, esse critério de caracterização é escalável a grandes volumes de dados. Em redes com distribuição de grau homogênea - modelo Girvan-Newman (GN), nós com alto coeficiente de agrupamento também mostram-se representativos. Por outro lado, em redes com distribuição de grau heterogênea - modelo Lancichinetti-Fortunato-Radicchi (LFR), nós com alta intermedialidade se destacam. Nós com alto coeficiente de agrupamento em redes GN estão tipicamente situados em motifs do tipo quase-clique; nós com alta intermedialidade em redes LFR são hubs situados na borda das comunidades. Em ambos os casos, os nós destacados são excelentes regularizadores. Além disso, como critérios diversos se destacam em redes com características diversas, abordagens unificadas para a caracterização de nós representativos também foram estudadas. Crítica para o realce de indivíduos representativos e o bom desempenho da classificação semissupervisionada, a construção de redes a partir de bases de dados vetoriais também foi estudada. O método denominado AdaRadius foi proposto, e apresenta vantagens tais como adaptabilidade em bases de dados com densidade variada, baixa dependência da configuração de seus parâmetros, e custo computacional razoável, tanto sobre dados pool-based como incrementais. As redes resultantes, por sua vez, são esparsas, porém conectadas, e permitem que a classificação semissupervisionada se favoreça da rotulação prévia de indivíduos representativos. Por fim, também foi estudada a validação de métodos de construção de redes para o ASS, sendo proposta a medida denominada coerência grafo-rótulos de Katz. Em suma, os resultados discutidos apontam para a validade da seleção de indivíduos representativos para semear a classificação semissupervisionada, corroborando a hipótese central da presente tese. Analogias são encontrados em diversos problemas modelados em redes, tais como epidemiologia, propagação de rumores e informações, resiliência, letalidade, grandmother cells, e crescimento e auto-organização.
Semi-supervised learning (SSL) is the name given to the machine learning paradigm that considers both labeled and unlabeled data. Although often defined as a mid-term between unsupervised and supervised machine learning, this paradigm is usually applied to predictive or descriptive tasks. In the classification task, for example, the goal is to label the unlabeled data according to the labels of the labeled data. In this case, while the unlabeled data describes the data distributions and mediate the label propagation, the labeled data seeds the label propagation and guide it to the stability. However, as a whole, data is generated unlabeled, and to label data requires the involvement of domain specialists, labeling it by hand. Difficulties on visualizing huge amounts of data, as well as the cost of the specialists involvement, are challenges which may constraint the labeling task performance. Therefore, the automatic highlighting of good candidates to label by hand, henceforth called representative individuals, is a high value task, which may result in a good tradeoff between the cost with the specialist and the machine learning performance. Among the SSL approaches in the literature, our study is focused on the network--based approache, where datasets are represented relationally, through the graphic abstraction. Thus, the current study aims to explore and exploit the influence of the labeled data on the SSL performance, that is, the proper characterization of representative nodes, how the network structure may enhance them, the SSL performance gain due to labeling them by hand, and related philosophical aspects. Concerning the characterization, central nodes characterization criteria were studied on networks with well-defined modular structures. Counterintuitively, highly connected nodes (hubs) are not much representatives. Not so connected nodes placed in low connectivity neighborhoods are, though. Strictly local, this characterization is scalable to huge volumes of data. In networks with homogeneous degree distribution - Girvan-Newman networks (GN), nodes with high clustering coefficient also figure out as representatives. On the other hand, in networks with inhomogeneous degree distribution - Lancichinetti-Fortunato-Radicchi networks (LFR), nodes with high betweenness stand out. Nodes with high clustering coefficient in GN networks typically lie in almost-cliques motifs; nodes with high betweenness in LFR networks are highly connected nodes, which lie in communities borders. In both cases, the highlighted nodes are outstanding regularizers. Besides that, unified approaches to characterize representative nodes were studied because diverse criteria stand out for diverse networks. Crucial for highlighting representative nodes and ensure good SSL performance, the graph construction from vector-based datasets was also studied. The method called AdaRadius was introduced and presents advantages such as adaptability to data with variable density, low dependency on parameters settings, and reasonable computational cost on both pool based and incremental data. Yielding networks are sparse but connected and allow the semi-supervised classification to take great advantage of the manual labeling of representative nodes. Lastly, the validation of graph construction methods for SSL was studied, being proposed the validation measure called graph-labels Katz coherence. Summing up, the discussed results give rise to the validity of representative individuals selection to seed the semi-supervised classification, supporting the central assumption of current thesis. Analogies may be found in several real-world network problems, such as epidemiology, rumors and information spreading, resilience, lethality, grandmother cells, and network evolving and self-organization.

Les systèmes biologiques sont composés de biomolécules en interaction à différents niveaux moléculaires. D’un côté, les avancées technologiques ont facilité l’obtention des données omiques à ces divers niveaux. De l’autre, de nombreuses questions se posent, pour donner du sens et élucider les interactions importantes dans le flux d’informations complexes porté par cette énorme variété et quantité des données multi-omiques. Les réponses les plus satisfaisantes seront celles qui permettront de dévoiler les mécanismes sous-jacents à la condition biologique d’intérêt. On s’attend souvent à ce que l’intégration de différents types de données omiques permette de mettre en lumière les changements causaux potentiels qui conduisent à un phénotype spécifique ou à des traitements ciblés. Avec les avancées récentes de la science des réseaux, nous avons choisi de traiter ce problème d’intégration en représentant les données omiques à travers les graphes. Dans cette thèse, nous avons développé trois modèles à savoir BraneExp, BraneNet et BraneMF pour l’apprentissage d’intégrations de noeuds à partir de réseaux biologiques multicouches générés à partir de données omiques. Notre objectif est de résoudre divers problèmes complexes liés à l’intégration de données multiomiques, en développant des méthodes expressives et évolutives capables de tirer parti de la riche sémantique structurelle latente des réseaux du monde réel
Biological systems are composed of interacting bio-molecules at different molecular levels. With the advent of high-throughput technologies, omics data at their respective molecular level can be easily obtained. These huge, complex multi-omics data can be useful to provide insights into the flow of information at multiple levels, unraveling the mechanisms underlying the biological condition of interest. Integration of different omics data types is often expected to elucidate potential causative changes that lead to specific phenotypes, or targeted treatments. With the recent advances in network science, we choose to handle this integration issue by representing omics data through networks. In this thesis, we have developed three models, namely BraneExp, BraneNet, and BraneMF, for learning node embeddings from multilayer biological networks generated with omics data. We aim to tackle various challenging problems arising in multi-omics data integration, developing expressive and scalable methods capable of leveraging rich structural semantics of realworld networks

When human’s visual system is looking at two pictures taken in some indoor location, it is fairly easy to tell whether they were taken in exactly the same place, even when the location has never been visited in reality. It is possible due to being able to pay attention to the multiple factors such as spatial properties (windows shape, room shape), common patterns (floor, walls) or presence of specific objects (furniture, lighting). Changes in camera pose, illumination, furniture location or digital alteration of the image (e.g. watermarks) has little influence on this ability. Traditional approaches to measuring the perceptual similarity of images struggled to reproduce this skill. This thesis defines the Indoor scene verification (ISV) problem as distinguishing whether two indoor scene images were taken in the same indoor space or not. It explores the capabilities of state-of-the-art perceptual similarity metrics by introducing two new datasets designed specifically for this problem. Perceptual hashing, ORB, FaceNet and NetVLAD are evaluated as the baseline candidates. The results show that NetVLAD provides the best results on both datasets and therefore is chosen as the baseline for the experiments aiming to improve it. Three of them are carried out testing the impact of using the different training dataset, changing deep neural network architecture and introducing new loss function. Quantitative analysis of AUC score shows that switching from VGG16 to MobileNetV2 allows for improvement over the baseline.
Med mänskliga synförmågan är det ganska lätt att bedöma om två bilder som tas i samma inomhusutrymme verkligen har tagits i exakt samma plats även om man aldrig har varit där. Det är möjligt tack vare många faktorer, sådana som rumsliga egenskaper (fönsterformer, rumsformer), gemensamma mönster (golv, väggar) eller närvaro av särskilda föremål (möbler, ljus). Ändring av kamerans placering, belysning, möblernas placering eller digitalbildens förändring (t. ex. vattenstämpel) påverkar denna förmåga minimalt. Traditionella metoder att mäta bildernas perceptuella likheter hade svårigheter att reproducera denna färdighet . Denna uppsats definierar verifiering av inomhusbilder, Indoor SceneVerification (ISV), som en ansats att ta reda på om två inomhusbilder har tagits i samma utrymme eller inte. Studien undersöker de främsta perceptuella identitetsfunktionerna genom att introducera två nya datauppsättningar designade särskilt för detta. Perceptual hash, ORB, FaceNet och NetVLAD identifierades som potentiella referenspunkter. Resultaten visar att NetVLAD levererar de bästa resultaten i båda datauppsättningarna, varpå de valdes som referenspunkter till undersökningen i syfte att förbättra det. Tre experiment undersöker påverkan av användning av olika datauppsättningar, ändring av struktur i neuronnätet och införande av en ny minskande funktion. Kvantitativ AUC-värdet analys visar att ett byte frånVGG16 till MobileNetV2 tillåter förbättringar i jämförelse med de primära lösningarna.

De nos jours, les médias sociaux ont largement affecté tous les aspects de la vie humaine. Le changement le plus significatif dans le comportement des gens après l'émergence des réseaux sociaux en ligne (OSNs) est leur méthode de communication et sa portée. Avoir plus de connexions sur les OSNs apporte plus d'attention et de visibilité aux gens, où cela s'appelle la popularité sur les médias sociaux. Selon le type de réseau social, la popularité se mesure par le nombre d'adeptes, d'amis, de retweets, de goûts et toutes les autres mesures qui servaient à calculer l'engagement. L'étude du comportement de popularité des utilisateurs et des contenus publiés sur les médias sociaux et la prédiction de leur statut futur sont des axes de recherche importants qui bénéficient à différentes applications telles que les systèmes de recommandation, les réseaux de diffusion de contenu, les campagnes publicitaires, la prévision des résultats des élections, etc. Cette thèse porte sur l'analyse du comportement de popularité des utilisateurs d'OSN et de leurs messages publiés afin, d'une part, d'identifier les tendances de popularité des utilisateurs et des messages et, d'autre part, de prévoir leur popularité future et leur niveau d'engagement pour les messages publiés par les utilisateurs. A cette fin, i) l'évolution de la popularité des utilisateurs de l'ONS est étudiée à l'aide d'un ensemble de données d'utilisateurs professionnels 8K Facebook collectées par un crawler avancé. L'ensemble de données collectées comprend environ 38 millions d'instantanés des valeurs de popularité des utilisateurs et 64 millions de messages publiés sur une période de 4 ans. Le regroupement des séquences temporelles des valeurs de popularité des utilisateurs a permis d'identifier des modèles d'évolution de popularité différents et intéressants. Les grappes identifiées sont caractérisées par l'analyse du secteur d'activité des utilisateurs, appelé catégorie, leur niveau d'activité, ainsi que l'effet des événements externes. Ensuite ii) la thèse porte sur la prédiction de l'engagement des utilisateurs sur les messages publiés par les utilisateurs sur les OSNs. Un nouveau modèle de prédiction est proposé qui tire parti de l'information mutuelle par points (PMI) et prédit la réaction future des utilisateurs aux messages nouvellement publiés. Enfin, iii) le modèle proposé est élargi pour tirer profit de l'apprentissage de la représentation et prévoir l'engagement futur des utilisateurs sur leurs postes respectifs. L'approche de prédiction proposée extrait l'intégration de l'utilisateur de son historique de réaction au lieu d'utiliser les méthodes conventionnelles d'extraction de caractéristiques. La performance du modèle proposé prouve qu'il surpasse les méthodes d'apprentissage conventionnelles disponibles dans la littérature. Les modèles proposés dans cette thèse, non seulement déplacent les modèles de prédiction de réaction vers le haut pour exploiter les fonctions d'apprentissage de la représentation au lieu de celles qui sont faites à la main, mais pourraient également aider les nouvelles agences, les campagnes publicitaires, les fournisseurs de contenu dans les CDN et les systèmes de recommandation à tirer parti de résultats de prédiction plus précis afin d'améliorer leurs services aux utilisateurs
Nowadays, social media has widely affected every aspect of human life. The most significant change in people's behavior after emerging Online Social Networks (OSNs) is their communication method and its range. Having more connections on OSNs brings more attention and visibility to people, where it is called popularity on social media. Depending on the type of social network, popularity is measured by the number of followers, friends, retweets, likes, and all those other metrics that is used to calculate engagement. Studying the popularity behavior of users and published contents on social media and predicting its future status are the important research directions which benefit different applications such as recommender systems, content delivery networks, advertising campaign, election results prediction and so on. This thesis addresses the analysis of popularity behavior of OSN users and their published posts in order to first, identify the popularity trends of users and posts and second, predict their future popularity and engagement level for published posts by users. To this end, i) the popularity evolution of ONS users is studied using a dataset of 8K Facebook professional users collected by an advanced crawler. The collected dataset includes around 38 million snapshots of users' popularity values and 64 million published posts over a period of 4 years. Clustering temporal sequences of users' popularity values led to identifying different and interesting popularity evolution patterns. The identified clusters are characterized by analyzing the users' business sector, called category, their activity level, and also the effect of external events. Then ii) the thesis focuses on the prediction of user engagement on the posts published by users on OSNs. A novel prediction model is proposed which takes advantage of Point-wise Mutual Information (PMI) and predicts users' future reaction to newly published posts. Finally, iii) the proposed model is extended to get benefits of representation learning and predict users' future engagement on each other's posts. The proposed prediction approach extracts user embedding from their reaction history instead of using conventional feature extraction methods. The performance of the proposed model proves that it outperforms conventional learning methods available in the literature. The models proposed in this thesis, not only improves the reaction prediction models to exploit representation learning features instead of hand-crafted features but also could help news agencies, advertising campaigns, content providers in CDNs, and recommender systems to take advantage of more accurate prediction results in order to improve their user services

De nos jours, les médias sociaux ont largement affecté tous les aspects de la vie humaine. Le changement le plus significatif dans le comportement des gens après l'émergence des réseaux sociaux en ligne (OSNs) est leur méthode de communication et sa portée. Avoir plus de connexions sur les OSNs apporte plus d'attention et de visibilité aux gens, où cela s'appelle la popularité sur les médias sociaux. Selon le type de réseau social, la popularité se mesure par le nombre d'adeptes, d'amis, de retweets, de goûts et toutes les autres mesures qui servaient à calculer l'engagement. L'étude du comportement de popularité des utilisateurs et des contenus publiés sur les médias sociaux et la prédiction de leur statut futur sont des axes de recherche importants qui bénéficient à différentes applications telles que les systèmes de recommandation, les réseaux de diffusion de contenu, les campagnes publicitaires, la prévision des résultats des élections, etc. Cette thèse porte sur l'analyse du comportement de popularité des utilisateurs d'OSN et de leurs messages publiés afin, d'une part, d'identifier les tendances de popularité des utilisateurs et des messages et, d'autre part, de prévoir leur popularité future et leur niveau d'engagement pour les messages publiés par les utilisateurs. A cette fin, i) l'évolution de la popularité des utilisateurs de l'ONS est étudiée à l'aide d'un ensemble de données d'utilisateurs professionnels 8K Facebook collectées par un crawler avancé. L'ensemble de données collectées comprend environ 38 millions d'instantanés des valeurs de popularité des utilisateurs et 64 millions de messages publiés sur une période de 4 ans. Le regroupement des séquences temporelles des valeurs de popularité des utilisateurs a permis d'identifier des modèles d'évolution de popularité différents et intéressants. Les grappes identifiées sont caractérisées par l'analyse du secteur d'activité des utilisateurs, appelé catégorie, leur niveau d'activité, ainsi que l'effet des événements externes. Ensuite ii) la thèse porte sur la prédiction de l'engagement des utilisateurs sur les messages publiés par les utilisateurs sur les OSNs. Un nouveau modèle de prédiction est proposé qui tire parti de l'information mutuelle par points (PMI) et prédit la réaction future des utilisateurs aux messages nouvellement publiés. Enfin, iii) le modèle proposé est élargi pour tirer profit de l'apprentissage de la représentation et prévoir l'engagement futur des utilisateurs sur leurs postes respectifs. L'approche de prédiction proposée extrait l'intégration de l'utilisateur de son historique de réaction au lieu d'utiliser les méthodes conventionnelles d'extraction de caractéristiques. La performance du modèle proposé prouve qu'il surpasse les méthodes d'apprentissage conventionnelles disponibles dans la littérature. Les modèles proposés dans cette thèse, non seulement déplacent les modèles de prédiction de réaction vers le haut pour exploiter les fonctions d'apprentissage de la représentation au lieu de celles qui sont faites à la main, mais pourraient également aider les nouvelles agences, les campagnes publicitaires, les fournisseurs de contenu dans les CDN et les systèmes de recommandation à tirer parti de résultats de prédiction plus précis afin d'améliorer leurs services aux utilisateurs
Nowadays, social media has widely affected every aspect of human life. The most significant change in people's behavior after emerging Online Social Networks (OSNs) is their communication method and its range. Having more connections on OSNs brings more attention and visibility to people, where it is called popularity on social media. Depending on the type of social network, popularity is measured by the number of followers, friends, retweets, likes, and all those other metrics that is used to calculate engagement. Studying the popularity behavior of users and published contents on social media and predicting its future status are the important research directions which benefit different applications such as recommender systems, content delivery networks, advertising campaign, election results prediction and so on. This thesis addresses the analysis of popularity behavior of OSN users and their published posts in order to first, identify the popularity trends of users and posts and second, predict their future popularity and engagement level for published posts by users. To this end, i) the popularity evolution of ONS users is studied using a dataset of 8K Facebook professional users collected by an advanced crawler. The collected dataset includes around 38 million snapshots of users' popularity values and 64 million published posts over a period of 4 years. Clustering temporal sequences of users' popularity values led to identifying different and interesting popularity evolution patterns. The identified clusters are characterized by analyzing the users' business sector, called category, their activity level, and also the effect of external events. Then ii) the thesis focuses on the prediction of user engagement on the posts published by users on OSNs. A novel prediction model is proposed which takes advantage of Point-wise Mutual Information (PMI) and predicts users' future reaction to newly published posts. Finally, iii) the proposed model is extended to get benefits of representation learning and predict users' future engagement on each other's posts. The proposed prediction approach extracts user embedding from their reaction history instead of using conventional feature extraction methods. The performance of the proposed model proves that it outperforms conventional learning methods available in the literature. The models proposed in this thesis, not only improves the reaction prediction models to exploit representation learning features instead of hand-crafted features but also could help news agencies, advertising campaigns, content providers in CDNs, and recommender systems to take advantage of more accurate prediction results in order to improve their user services

Problemas de projeto de redes (PPRs) são muito importantes uma vez que envolvem uma série de aplicações em áreas da engenharia e ciências. Para solucionar as limitações de algoritmos convencionais para PPRs que envolvem redes complexas do mundo real (em geral modeladas por grafos completos ou mesmo esparsos de larga-escala), heurísticas, como os algoritmos evolutivos (EAs), têm sido investigadas. Trabalhos recentes têm mostrado que estruturas de dados adequadas podem melhorar significativamente o desempenho de EAs para PPRs. Uma dessas estruturas de dados é a representação nó-profundidade (NDE, do inglês Node-depth Encoding). Em geral, a aplicação de EAs com a NDE tem apresentado resultados relevantes para PPRs de larga-escala. Este trabalho investiga o desenvolvimento de uma nova representação, baseada na NDE, chamada representação nó-profundidade-grau (NDDE, do inglês Node-depth-degree Encoding). A NDDE é composta por melhorias nos operadores existentes da NDE e pelo desenvolvimento de novos operadores de reprodução possibilitando a recombinação de soluções. Nesse sentido, desenvolveu-se um operador de recombinação capaz de lidar com grafos não-completos e completos, chamado EHR (do inglês, Evolutionary History Recombination Operator). Foram também desenvolvidos operadores de recombinação que lidam somente com grafos completos, chamados de NOX e NPBX. Tais melhorias tem como objetivo manter relativamente baixa a complexidade computacional dos operadores para aumentar o desempenho de EAs para PPRs de larga-escala. A análise de propriedades de representações mostrou que a NDDE possui redundância, assim, foram propostos mecanismos para evitá-la. Essa análise mostrou também que o EHR possui baixa complexidade de tempo e não possui tendência, além de revelar que o NOX e o NPBX possuem uma tendência para árvores com topologia de estrela. A aplicação de EAs usando a NDDE para PPRs clássicos envolvendo grafos completos, tais como árvore geradora de comunicação ótima, árvore geradora mínima com restrição de grau e uma árvore máxima, mostrou que, quanto maior o tamanho das instâncias do PPR, melhor é o desempenho relativo da técnica em comparação com os resultados obtidos com outros EAs para PPRs da literatura. Além desses problemas, um EA utilizando a NDE com o operador EHR foi aplicado ao PPR do mundo real de reconfiguração de sistemas de distribuição de energia elétrica (envolvendo grafos esparsos). Os resultados mostram que o EHR possibilita reduzir significativamente o tempo de convergência do EA
Network design problems (NDPs) are very important since they involve several applications from areas of Engineering and Sciences. In order to solve the limitations of traditional algorithms for NDPs that involve real world complex networks (in general, modeled by large-scale complete or sparse graphs), heuristics, such as evolutionary algorithms (EAs), have been investigated. Recent researches have shown that appropriate data structures can improve EA performance when applied to NDPs. One of these data structures is the Node-depth Encoding (NDE). In general, the performance of EAs with NDE has presented relevant results for large-scale NDPs. This thesis investigates the development of a new representation, based on NDE, called Node-depth-degree Encoding (NDDE). The NDDE is composed for improvements of the NDE operators and the development of new reproduction operators that enable the recombination of solutions. In this way, we developed a recombination operator to work with both non-complete and complete graphs, called EHR (Evolutionary History Recombination Operator). We also developed two other operators to work only with complete graphs, named NOX and NPBX. These improvements have the advantage of retaining the computational complexity of the operators relatively low in order to improve the EA performance. The analysis of representation properties have shown that NDDE is a redundant representation and, for this reason, we proposed some strategies to avoid it. This analysis also showed that EHR has low running time and it does not have bias, moreover, it revealed that NOX and NPBX have bias to trees like stars. The application of an EA using the NDDE to classic NDPs, such as, optimal communication spanning tree, degree-constraint minimum spanning tree and one-max tree, showed that the larger the instance is, the better the performance will be in comparison whit other EAs applied to NDPs in the literatura. An EA using the NDE with EHR was applied to a real-world NDP of reconfiguration of energy distribution systems. The results showed that EHR significantly decrease the convergence time of the EA

Thesis (Ph.D)--Electrical and Computer Engineering, Georgia Institute of Technology, 2010.
Committee Chair: Madisetti, Vijay; Committee Member: Jayant, Nikil; Committee Member: Lee, Chin-Hui; Committee Member: Ramachandran, Umakishore; Committee Member: Yalamanchili, Sudhakar. Part of the SMARTech Electronic Thesis and Dissertation Collection.

Dans cette thèse nous contribuons à répondre aux questions sur les processus dynamiques sur réseaux temporels. En particulier, nous etudions l'influence des représentations de données sur les simulations des processus épidémiques, le niveau de détail nécessaire pour la représentation des données et sa dépendance des paramètres de la propagation de l'épidémie. Avec l'introduction de la matrice de distributions du temps de contacts nous espérons pouvoir améliorer dans le futur la précision des prédictions des épidémies et des stratégies d'immunisation en intégrant cette représentation des données aux modèles d'épidémies multi-échelles. De plus nous montrons comment les processus épidémiques dynamiques sont influencés par les propriétés temporelles des données
In this thesis we contribute to provide insights into questions concerning dynamic epidemic processes on data-driven, temporal networks. In particular, we investigate the influence of data representations on the outcome of epidemic processes, shedding some light on the question how much detail is necessary for the data representation and its dependence on the spreading parameters. By introducing an improvement to the contact matrix representation we provide a data representation that could in the future be integrated into multi-scale epidemic models in order to improve the accuracy of predictions and corresponding immunization strategies. We also point out some of the ways dynamic processes are influenced by temporal properties of the data

Les données métagénomiques du microbiome humain constituent une nouvelle source de données pour améliorer le diagnostic et le pronostic des maladies humaines. Cependant, réaliser une prédiction basée sur l'abondance de bactéries individuelles est un défi, car le nombre de caractéristiques est beaucoup plus grand que le nombre d'échantillons et les difficultés liées au traitement de données dimensionnelles, ainsi que la grande complexité des données hétérogènes. L'apprentissage automatique a obtenu de grandes réalisations sur d'importants problèmes de métagénomique liés au regroupement d'OTU, à l'assignation taxonomique, etc. La contribution de cette thèse est multiple: 1) un cadre de sélection de caractéristiques pour approche pour prédire les maladies à l'aide de représentations d'images artificielles. La première contribution, qui est une approche efficace de sélection de caractéristiques basée sur les capacités de visualisation de la carte auto-organisée, montre une précision de classification raisonnable par rapport aux méthodes de pointe. La seconde approche vise à visualiser les données métagénomiques en utilisant une méthode simple de remplissage, ainsi que des approches d'apprentissage de réduction dimensionnelle. La nouvelle représentation des données métagénomiques peut être considérée comme une image synthétique et utilisée comme un nouvel ensemble de données pour une méthode efficace d'apprentissage en profondeur. Les résultats montrent que les méthodes proposées permettent d'atteindre des performances prédictives à la pointe de la technologie ou de les surpasser sur des benchmarks métagénomiques riches en public
Metagenomic data from human microbiome is a novel source of data for improving diagnosis and prognosis in human diseases. However, to do a prediction based on individual bacteria abundance is a challenge, since the number of features is much bigger than the number of samples. Hence, we face the difficulties related to high dimensional data processing, as well as to the high complexity of heterogeneous data. Machine Learning has obtained great achievements on important metagenomics problems linked to OTU-clustering, binning, taxonomic assignment, etc. The contribution of this PhD thesis is multi-fold: 1) a feature selection framework for efficient heterogeneous biomedical signature extraction, and 2) a novel deep learning approach for predicting diseases using artificial image representations. The first contribution is an efficient feature selection approach based on visualization capabilities of Self-Organizing Maps for heterogeneous data fusion. The framework is efficient on a real and heterogeneous datasets containing metadata, genes of adipose tissue, and gut flora metagenomic data with a reasonable classification accuracy compared to the state-of-the-art methods. The second approach is a method to visualize metagenomic data using a simple fill-up method, and also various state-of-the-art dimensional reduction learning approaches. The new metagenomic data representation can be considered as synthetic images, and used as a novel data set for an efficient deep learning method such as Convolutional Neural Networks. The results show that the proposed methods either achieve the state-of-the-art predictive performance, or outperform it on public rich metagenomic benchmarks

The automatic recognition of sound events has gained attention in the past few years, motivated by emerging applications in fields such as healthcare, smart homes, or urban planning. When the work for this thesis started, research on sound event classification was mainly focused on supervised learning using small datasets, often carefully annotated with vocabularies limited to specific domains (e.g., urban or domestic). However, such small datasets do not support training classifiers able to recognize hundreds of sound events occurring in our everyday environment, such as kettle whistles, bird tweets, cars passing by, or different types of alarms. At the same time, large amounts of environmental sound data are hosted in websites such as Freesound or YouTube, which can be convenient for training large-vocabulary classifiers, particularly using data-hungry deep learning approaches. To advance the state-of-the-art in sound event classification, this thesis investigates several strands of dataset creation as well as supervised and unsupervised learning to train large-vocabulary sound event classifiers, using different types of supervision in novel and alternative ways. Specifically, we focus on supervised learning using clean and noisy labels, as well as self-supervised representation learning from unlabeled data. The first part of this thesis focuses on the creation of FSD50K, a large-vocabulary dataset with over 100h of audio manually labeled using 200 classes of sound events. We provide a detailed description of the creation process and a comprehensive characterization of the dataset. In addition, we explore architectural modifications to increase shift invariance in CNNs, improving robustness to time/frequency shifts in input spectrograms. In the second part, we focus on training sound event classifiers using noisy labels. First, we propose a dataset that supports the investigation of real label noise. Then, we explore network-agnostic approaches to mitigate the effect of label noise during training, including regularization techniques, noise-robust loss functions, and strategies to reject noisy labeled examples. Further, we develop a teacher-student framework to address the problem of missing labels in sound event datasets. In the third part, we propose algorithms to learn audio representations from unlabeled data. In particular, we develop self-supervised contrastive learning frameworks, where representations are learned by comparing pairs of examples computed via data augmentation and automatic sound separation methods. Finally, we report on the organization of two DCASE Challenge Tasks on automatic audio tagging with noisy labels. By providing data resources as well as state-of-the-art approaches and audio representations, this thesis contributes to the advancement of open sound event research, and to the transition from traditional supervised learning using clean labels to other learning strategies less dependent on costly annotation efforts.
El interés en el reconocimiento automático de eventos sonoros se ha incrementado en los últimos años, motivado por nuevas aplicaciones en campos como la asistencia médica, smart homes, o urbanismo. Al comienzo de esta tesis, la investigación en clasificación de eventos sonoros se centraba principalmente en aprendizaje supervisado usando datasets pequeños, a menudo anotados cuidadosamente con vocabularios limitados a dominios específicos (como el urbano o el doméstico). Sin embargo, tales datasets no permiten entrenar clasificadores capaces de reconocer los cientos de eventos sonoros que ocurren en nuestro entorno, como silbidos de kettle, sonidos de pájaros, coches pasando, o diferentes alarmas. Al mismo tiempo, websites como Freesound o YouTube albergan grandes cantidades de datos de sonido ambiental, que pueden ser útiles para entrenar clasificadores con un vocabulario más extenso, particularmente utilizando métodos de deep learning que requieren gran cantidad de datos. Para avanzar el estado del arte en la clasificación de eventos sonoros, esta tesis investiga varios aspectos de la creación de datasets, así como de aprendizaje supervisado y no supervisado para entrenar clasificadores de eventos sonoros con un vocabulario extenso, utilizando diferentes tipos de supervisión de manera novedosa y alternativa. En concreto, nos centramos en aprendizaje supervisado usando etiquetas sin ruido y con ruido, así como en aprendizaje de representaciones auto-supervisado a partir de datos no etiquetados. La primera parte de esta tesis se centra en la creación de FSD50K, un dataset con más de 100h de audio etiquetado manualmente usando 200 clases de eventos sonoros. Presentamos una descripción detallada del proceso de creación y una caracterización exhaustiva del dataset. Además, exploramos modificaciones arquitectónicas para aumentar la invariancia frente a desplazamientos en CNNs, mejorando la robustez frente a desplazamientos de tiempo/frecuencia en los espectrogramas de entrada. En la segunda parte, nos centramos en entrenar clasificadores de eventos sonoros usando etiquetas con ruido. Primero, proponemos un dataset que permite la investigación del ruido de etiquetas real. Después, exploramos métodos agnósticos a la arquitectura de red para mitigar el efecto del ruido en las etiquetas durante el entrenamiento, incluyendo técnicas de regularización, funciones de coste robustas al ruido, y estrategias para rechazar ejemplos etiquetados con ruido. Además, desarrollamos un método teacher-student para abordar el problema de las etiquetas ausentes en datasets de eventos sonoros. En la tercera parte, proponemos algoritmos para aprender representaciones de audio a partir de datos sin etiquetar. En particular, desarrollamos métodos de aprendizaje contrastivos auto-supervisados, donde las representaciones se aprenden comparando pares de ejemplos calculados a través de métodos de aumento de datos y separación automática de sonido. Finalmente, reportamos sobre la organización de dos DCASE Challenge Tasks para el tageado automático de audio a partir de etiquetas ruidosas. Mediante la propuesta de datasets, así como de métodos de vanguardia y representaciones de audio, esta tesis contribuye al avance de la investigación abierta sobre eventos sonoros y a la transición del aprendizaje supervisado tradicional utilizando etiquetas sin ruido a otras estrategias de aprendizaje menos dependientes de costosos esfuerzos de anotación.

by Fung Tze Wa.
Thesis (M.Phil.)--Chinese University of Hong Kong, 2003.
Includes bibliographical references (leaves 92-96).
Abstracts in English and Chinese.
Abstract in English --- p.i
Abstract in Chinese --- p.ii
Acknowledgements --- p.iii
Table of Contents --- p.iv-vi
List of Figures --- p.vii-ix
List of Tables --- p.x
Chapter Chapter 1 --- Introduction
Chapter 1.1 --- Introduction --- p.1
Chapter 1.2 --- Motivation --- p.3
Chapter 1.3 --- Purposes of this Research --- p.6
Chapter 1.4 --- Contribution of this Research --- p.7
Chapter 1.5 --- Outline of the Thesis --- p.9
Chapter Chapter 2 --- Literature Review And Research Issues
Chapter 2.1 --- Introduction --- p.11
Chapter 2.2 --- Spatial Access Methods --- p.14
Chapter 2.2.1 --- R-Tree --- p.15
Chapter 2.2.2 --- R*-Tree --- p.19
Chapter 2.2.3 --- R+-Tree --- p.21
Chapter 2.3 --- Spatial Network Analysis --- p.22
Chapter 2.4 --- Nearest Neighbor Queries --- p.23
Chapter 2.5 --- Summary --- p.25
Chapter Chapter 3 --- Data Preparation
Chapter 3.1 --- "Introduction (XML, GML), XML indexing" --- p.26
Chapter 3.2 --- Spatial data from Lands Department --- p.31
Chapter 3.3 --- Graph representation for Road Network data --- p.32
Chapter 3.4 --- Summary --- p.35
Chapter Chapter 4 --- XML Indexing for Spatial Data
Chapter 4.1 --- Introduction --- p.36
Chapter 4.2 --- STR Packed R-Tree --- p.38
Chapter 4.2.1 --- Implementation --- p.39
Chapter 4.2.2 --- Experimental Result --- p.41
Chapter 4.3 --- Summary --- p.48
Chapter Chapter 5 --- Spatial Network
Chapter 5.1 --- Introduction --- p.50
Chapter 5.2 --- CCAM: Connectivity-Clustered Access Method --- p.53
Chapter 5.3 --- Shortest Path in Spatial Network --- p.56
Chapter 5.4 --- A New Algorithm Specially for Partitioning /Clustering Network --- p.63
Chapter 5.5 --- A New Simple heuristic for Shortest Path Problem for Spatial Network --- p.70
Chapter 5.6 --- Summary --- p.74
Chapter Chapter 6 --- Nearest Neighbor Queries
Chapter 6.1 --- Introduction --- p.76
Chapter 6.2 --- Modified Algorithm for Nearest Neighbor Queries --- p.78
Chapter 6.3 --- Summary --- p.83
Chapter Chapter 7 --- Conclusion and Future Work
Chapter 7.1 --- Conclusion --- p.84
Chapter 7.2 --- Future Work --- p.85
Appendix Space Driven Algorithm
Chapter A.1 --- Introduction --- p.87
Chapter A.2 --- Fixed Grid --- p.88
Chapter A.3 --- Z-curve --- p.89
Chapter A.4 --- Hilbert curve --- p.90
Chapter A.5 --- Conclusion --- p.91
Bibliography --- p.92

Biomechanical Big Data is of great significance to precision health applications, among which we take special interest in Physical Activity Detection (PAD). In this study, we have performed extensive research on deep learning-based PAD from biomechanical big data, focusing on the challenges raised by the need of real-time edge inference. First, considering there are many places we can place the motion sensors, we have thoroughly compared and analyzed the location difference in terms of deep learning-based PAD performance. We have further compared the difference among six sensor channels (3-axis accelerometer and 3-axis gyroscope). Second, we have selected the optimal sensor and the optimal sensor channel, which can not only provide sensor usage suggestions but also enable ultra-low-power application on the edge. Third, we have investigated innovative methods to minimize the training effort of the deep learning model, leveraging the transfer learning strategy. More specifically, we propose to pre-train a transferable deep learning model using the data from other subjects and then fine-tune the model using limited data from the target-user. In such a way, we have found that, for single-channel case, the transfer learning can effectively increase the deep model performance even when the fine-tuning effort is very small. This research, demonstrated by comprehensive experimental evaluation, have shown the potential of ultra-low-power PAD with minimized sensor stream and minimized training effort.

The detection of anomalies in real-world networks is applicable in different domains; the application includes, but is not limited to, credit card fraud detection, malware identification and classification, cancer detection from diagnostic reports, abnormal traffic detection, identification of fake media posts, and the like. Many ongoing and current researches are providing tools for analyzing labeled and unlabeled data; however, the challenges of finding anomalies and patterns in large-scale datasets still exist because of rapid changes in the threat landscape.

In this study, I implemented a novel and robust solution that combines data science and cybersecurity to solve complex network security problems. I used Long Short-Term Memory (LSTM) model, Louvain algorithm, and PageRank algorithm to identify and group anomalies in large-scale real-world networks. The network has billions of packets. The developed model used different visualization techniques to provide further insight into how the anomalies in the network are related.

Mean absolute error (MAE) and root mean square error (RMSE) was used to validate the anomaly detection models, the results obtained for both are 5.1813e-04 and 1e-03 respectively. The low loss from the training phase confirmed the low RMSE at loss: 5.1812e-04, mean absolute error: 5.1813e-04, validation loss: 3.9858e-04, validation mean absolute error: 3.9858e-04. The result from the community detection shows an overall modularity value of 0.914 which is proof of the existence of very strong communities among the anomalies. The largest sub-community of the anomalies connects 10.42% of the total nodes of the anomalies.

The broader aim and impact of this study was to provide sophisticated, AI-assisted countermeasures to cyber-threats in large-scale networks. To close the existing gaps created by the shortage of skilled and experienced cybersecurity specialists and analysts in the cybersecurity field, solutions based on out-of-the-box thinking are inevitable; this research was aimed at yielding one of such solutions. It was built to detect specific and collaborating threat actors in large networks and to help speed up how the activities of anomalies in any given large-scale network can be curtailed in time.

Artificial neural networks, including deep neural networks, play a central role in data-driven science due to their superior learning capacity and adaptability to different tasks and data structures. However, although quantitative uncertainty analysis is essential for training and deploying reliable data-driven models, the uncertainties in neural networks are often overlooked or underestimated in many studies, mainly due to the lack of a high-fidelity and computationally efficient uncertainty quantification approach. In this work, a novel uncertainty analysis scheme is developed. The Gaussian mixture model is used to characterize the probability distributions of uncertainties in arbitrary forms, which yields higher fidelity than the presumed distribution forms, like Gaussian, when the underlying uncertainty is multimodal, and is more compact and efficient than large-scale Monte Carlo sampling. The fidelity of the Gaussian mixture is refined through adaptive scheduling of the width of each Gaussian component based on the active assessment of the factors that could deteriorate the uncertainty representation quality, such as the nonlinearity of activation functions in the neural network.

Following this idea, an adaptive Gaussian mixture scheme of nonlinear uncertainty propagation is proposed to effectively propagate the probability distributions of uncertainties through layers in deep neural networks or through time in recurrent neural networks. An adaptive Gaussian mixture filter (AGMF) is then designed based on this uncertainty propagation scheme. By approximating the dynamics of a highly nonlinear system with a feedforward neural network, the adaptive Gaussian mixture refinement is applied at both the state prediction and Bayesian update steps to closely track the distribution of unmeasurable states. As a result, this new AGMF exhibits state-of-the-art accuracy with a reasonable computational cost on highly nonlinear state estimation problems subject to high magnitudes of uncertainties. Next, a probabilistic neural network with Gaussian-mixture-distributed parameters (GM-PNN) is developed. The adaptive Gaussian mixture scheme is extended to refine intermediate layer states and ensure the fidelity of both linear and nonlinear transformations within the network so that the predictive distribution of output target can be inferred directly without sampling or approximation of integration. The derivatives of the loss function with respect to all the probabilistic parameters in this network are derived explicitly, and therefore, the GM-PNN can be easily trained with any backpropagation method to address practical data-driven problems subject to uncertainties.

The GM-PNN is applied to two data-driven condition monitoring schemes of manufacturing processes. For tool wear monitoring in the turning process, a systematic feature normalization and selection scheme is proposed for the engineering of optimal feature sets extracted from sensor signals. The predictive tool wear models are established using two methods, one is a type-2 fuzzy network for interval-type uncertainty quantification and the other is the GM-PNN for probabilistic uncertainty quantification. For porosity monitoring in laser additive manufacturing processes, convolutional neural network (CNN) is used to directly learn patterns from melt-pool patterns to predict porosity. The classical CNN models without consideration of uncertainty are compared with the CNN models in which GM-PNN is embedded as an uncertainty quantification module. For both monitoring schemes, experimental results show that the GM-PNN not only achieves higher prediction accuracies of process conditions than the classical models but also provides more effective uncertainty quantification to facilitate the process-level decision-making in the manufacturing environment.

Based on the developed uncertainty analysis methods and their proven successes in practical applications, some directions for future studies are suggested. Closed-loop control systems may be synthesized by combining the AGMF with data-driven controller design. The AGMF can also be extended from a state estimator to the parameter estimation problems in data-driven models. In addition, the GM-PNN scheme may be expanded to directly build more complicated models like convolutional or recurrent neural networks.

This thesis investigates a cultural logic of information. In a world saturated with information, how is representation defined, and what kinds of boundaries does it consequently set up for establishing what can be known? I argue that a cultural logic of information articulates a common cultural definition for representation: information is understood as either a “true” representation of reality, or a substitute for reality itself. As a result, information comes to be conflated with knowledge. But, in contrast to calls (scholarly and otherwise) to police the boundaries of information, I argue 1) that information is exceedingly difficult to separate, in kind, from storytelling, because 2) the provision of information almost always entails scrambles for narrative representation, which 3) are always staged in the terms of genre. The function of these conclusions is the constant undermining of this cultural logic. I examine the intersection of a variety of cultural and theoretical objects, including: Fox News and “Make America Great Again”; scientific modelling of climate change; Claude Shannon’s mathematical theory of communication; Karl Ove Knausgaard’s My Struggle; YouTube “lifestyle” communities; and the documentary “The Act of Killing.” I suggest that a methodology that accounts for the imbrication of information and storytelling better accounts for the vicissitudes of, and ideological struggles over, these cultural phenomena. It does so, in particular, by engaging with the subjective experience of information, and assessing how subjects imagine their relations to information and to networks. The purpose of this argument is to intervene in conversations about the articulation of life in control societies.
Graduate
2021-06-20

当今，越来越多的用倾向于使用论坛、博客、脸书等在线工具来表达关于商品、电影和政治等话题的观点。这些观点不仅可以帮助用进行决策，同时也为各个商业和社会领域提供了具有重要价值的反馈信息。因此，面向观点应用成为了当前最活跃的研究领域之一，其中包括观点检索，观点摘要，观点问答。面向观点应用与面向事实应用的根本区别是信息需求的不同，分别是传统的客观信息和主观信息。所谓主观信息是指对于某个特定目标的观点或评论。为了表示主观信息，应该综合考虑观点性、主题相关性，以及观点与主题之间的关联。现有的基于词袋的表示方法将词作为描述客观信息的基本语义单元，它可以有效的表示主题相关性以满足客观信息的需求。而主观信息需要同时考虑观点性和主题相关性，由于单独一个词不能同时表示观点性和相关性，因此词不再是最小的语义单位。此外，基于词袋的表示方法忽略了词序和词义，这使得观点性和相关性两类信息通常混在一起，难以区分。因此，基于词袋方法不能够准确的表示主观信息，并严重的影响了面向观点应用的性能。
本文回答了以下几个由主观信息表示不当所引发的研究问题： 1. 对于主观信息而言单个词将不再是基本语义单元，是否存在一种有效的表示方法对其进行描述？ 2. 由于主观信息是观点信息和相关性信息的结合，如何利用新的表示方法来描述这二者之间的关联信息？3. 如何对主观信息进行量化，以便对文档进行检索和分析？ 4. 如何在面向观点应用中实现全新的主观信息表示方法？
由于观点检索的结果会直接影响到其它面向观点应用的性能，因此本文从观点检索这一问题入手。首先，我们提出了一种基于句子的方法来分析词袋表示方法的局限性。以此为据，定义了一种具有丰富语义的表达方式来表示主观信息，即词对，它是由出现在同一句子中的情感词和与之关联的目标词共同组成的。然后，我们提出了一系列方法来描述和获取两类语境信息：1）观点内信息：我们给出了三种提取词对的方法以获取观点与主题的关联信息；2）观点间信息：我们提出了一种权重计算方法来度量词对间的相关程度，从而获取词对与词对之间的关系。最后，我们集成了观点内信息和观点间信息并提出了潜在情感关联模型来解决观点检索这一问题。在标准数据集上的实验结果表明，基于词对的表示方法可以有效地描述主观信息，同时潜在情感关联模型能够获取词与词之间的关联信息，从而实现了利用语境信息提高观点检索的效果。
此外，我们将词对应用于观点摘要和观点问答中，标准数据集上的评测结果显示基于词对的主观信息表示方法对于其它面向观点应用也同样有效。
There is a growing interest for users to express their opinions about products, films, politics, by using on-line tools such as forums, blogs, facebooks, etc. These opinions cannot only help users make decisions, e.g., whether to buy a product, but also to ob-tain valuable feedback for business and social events. Today, research on opin-ion-oriented applications (OOAs) including opinion retrieval, opinion summarization and opinion question and answering is attracting much attention. The difference be-tween fact-based and opinion-oriented applications lies in users‘ information need. The former requires objective information and the latter subjective, which comprises of opinions or comments expressed on a specific target. To meet the need of subjective information, both opinionatedness and relevance together with the association between them should be taken into account. Existing systems represent documents in bag-of-word. However, this representation fails to distinguish opinionatedness from relevance. Moreover, due to the ignorance of word sequence, words associations are lost. For this reason, bag-of-word representation is ineffective for subjective information, and affects the performance of OOAs seriously.
In this thesis, we try to answer the following challenging questions arose in subjective information representation. Since word is no longer the basic semantic unit, how would subjective information be represented? Subjective information is a combination of opinionatedness and relevance, so how would the association between them be modeled? How would subjective information be measured for the purpose of document ranking, retrieval, and analysis? How would opinion-oriented applications benefit from subjective information?
We start from solving the problem of opinion retrieval whose results can directly influence the performance of other opinion-oriented applications. We first present a sentence-based approach to analyze the limitation of bag-of-word representation and define a semantically richer representation, namely word pair for subjective infor-mation. A word pair is constructed by a sentiment word and its associated target co-occurring in a sentence. We then propose techniques to capture two kinds of con-textual information. 1) Intra-opinion information: three methods are proposed to ex-tract the word pair. 2) Inter-opinion information: a weighting scheme is present to measure the weight of individual word pair. Finally, we devise an algorithm to integrate both intra-opinion and inter-opinion information into a latent sentimental association model for opinion retrieval. The evaluation on three benchmark datasets suggests the effectiveness of word pair and the latent sentimental association retrieval model provide insight into the words association to support opinion retrieval beneficial from pairwise representation. We also apply word pair to opinion summarization and opinion question answering. The evaluation on two benchmark datasets shows that word pair performs effectively in the applications.
Detailed summary in vernacular field only.
Detailed summary in vernacular field only.
Detailed summary in vernacular field only.
Detailed summary in vernacular field only.
Li, Binyang.
Thesis (Ph.D.)--Chinese University of Hong Kong, 2013.
Includes bibliographical references (leaves [96]-103).
Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web.
Abstract also in Chinese.
Abstract --- p.ii
Abstract in Chinese --- p.iv
Acknowledgements --- p.vi
Contents --- p.viii
List of Tables --- p.xi
List of Figures --- p.xiii
Chapter 1. --- Introduction --- p.1
Chapter 1.1. --- Problem and Challenges --- p.3
Chapter 1.1.1 --- Subjective Information Representation --- p.3
Chapter 1.1.2 --- Associative Information in an Opinion Expression --- p.4
Chapter 1.1.3 --- Opinion Expression Measurement --- p.5
Chapter 1.1.4 --- Applications of Subjective Information Representation to Different OOAs --- p.6
Chapter 1.2. --- Contributions --- p.6
Chapter 1.3. --- Chapter Summary --- p.7
Chapter 2. --- Pairwise Representation --- p.9
Chapter 2.1 --- Related Woks on Opinion Retrieval --- p.10
Chapter 2.1.1 --- Opinion Retrieval Models --- p.10
Chapter 2.1.2 --- Lexicon-based Opinion Identification --- p.12
Chapter 2.2 --- Sentence-based Approach for Opinion Retrieval --- p.13
Chapter 2.2.1 --- The Limitations of Document-based Approaches for Opinion Retrieval --- p.13
Chapter 2.2.2 --- Sentence-based Approach for Opinion Retrieval --- p.16
Chapter 2.2.3 --- Evaluation and Results --- p.21
Chapter 2.2.4 --- Summary --- p.26
Chapter 2.3 --- Pairwise Representation --- p.28
Chapter 2.3.1 --- Definition of Word Pair --- p.28
Chapter 2.3.2 --- Sentiment Lexicon Construction --- p.29
Chapter 2.3.3 --- Topic Term Lexicon Construction --- p.30
Chapter 2.3.4 --- Word Pair Construction --- p.31
Chapter 2.4 --- Graph-based Model for Opinion Retrieval --- p.33
Chapter 2.4.1 --- HITS Model for Opinion Retrieval --- p.34
Chapter 2.4.2 --- PageRank Model for Opinion Retrieval --- p.37
Chapter 2.4.3 --- Evaluation and Results --- p.40
Chapter 2.5 --- Chapter Summary --- p.50
Chapter 3. --- Pairwise Representation Measurement --- p.51
Chapter 3.1 --- Word Pair Weighting Scheme --- p.52
Chapter 3.1.1 --- PMI-based Weighting Scheme --- p.52
Chapter 3.1.2 --- Evaluation and Results --- p.56
Chapter 3.1.3 --- Summary --- p.60
Chapter 3.2 --- Latent Sentimental Association --- p.61
Chapter 3.2.1 --- Problem Formulation --- p.61
Chapter 3.2.2 --- LSA Integrated Generative Model --- p.62
Chapter 3.2.3 --- Modeling the Dependency between Q and d --- p.64
Chapter 3.2.4 --- Modeling the Dependency between O and d --- p.67
Chapter 3.3 --- Parameter Estimation --- p.67
Chapter 3.3.1 --- Estimating P(Q --- p.67
Chapter 3.3.2 --- Estimating MI(Q,O --- p.69
Chapter 3.4 --- Evaluation and Results --- p.69
Chapter 3.5 --- Chapter Summary --- p.72
Chapter 4. --- Pairwise Representation in Opinion-oriented Application --- p.75
Chapter 4.1. --- Opinion Questioning and Answering --- p.76
Chapter 4.1.1 --- Problem Statement --- p.76
Chapter 4.1.2 --- Existing Solution --- p.78
Chapter 4.1.3 --- A Word Pair based Approach for Sentence Ranking --- p.79
Chapter 4.1.4 --- Answer Generation --- p.82
Chapter 4.1.5 --- Evaluation and Results --- p.82
Chapter 4.2. --- Opinion Summarization --- p.86
Chapter 4.2.1 --- Problem Statement --- p.86
Chapter 4.2.2 --- Existing Solution --- p.87
Chapter 4.2.3 --- Sentence Ranking --- p.88
Chapter 4.2.4 --- Summary Generation --- p.88
Chapter 4.2.5 --- Evaluation and Results --- p.89
Chapter 4.3. --- Chapter Summary --- p.91
Chapter 5. --- Conclusions and Future Works --- p.93
Bibliography --- p.97

In recent years, deep neural networks have been very successful in computer vision, speech recognition, and artificial intelligent systems. The rapid growth of data and fast increasing computational tools provide solid foundations for the applications which rely on the learning of large scale deep neural networks with millions of parameters. The deep learning approaches have been proved to be able to learn powerful representations of the inputs in various tasks, such as image classification, object recognition, and scene understanding. This thesis demonstrates the generality and capacity of deep learning approaches through a series of case studies including image matching and human activity understanding. In these studies, I explore the combinations of the neural network models with existing machine learning techniques and extend the deep learning approach for each task. Four related tasks are investigated: 1) image matching through similarity learning; 2) human action prediction; 3) finger force estimation in manipulation actions; and 4) bimodal learning for human action understanding. Deep neural networks have been shown to be very efficient in supervised learning. Further, in some tasks, one would like to group the features of the samples in the same category close to each other, in additional to the discriminative representation. Such kind of properties is desired in a number of applications, such as semantic retrieval, image quality measurement, and social network analysis, etc. My first study is to develop a similarity learning method based on deep neural networks for image matching between sketch images and 3D models. In this task, I propose to use Siamese network to learn similarities of sketches and develop a novel method for sketch based 3D shape retrieval. The proposed method can successfully learn the representations of sketch images as well as the similarities, then the 3D shape retrieval problem can be solved with off-the-shelf nearest neighbor methods. After studying the representation learning methods for static inputs, my focus turns to learning the representations of sequential data. To be specific, I focus on manipulation actions, because they are widely used in the daily life and play important parts in the human-robot collaboration system. Deep neural networks have been shown to be powerful to represent short video clips [Donahue et al., 2015]. However, most existing methods consider the action recognition problem as a classification task. These methods assume the inputs are pre-segmented videos and the outputs are category labels. In the scenarios such as the human-robot collaboration system, the ability to predict the ongoing human actions at an early stage is highly important. I first attempt to address this issue with a fast manipulation action prediction method. Then I build the action prediction model based on Long Short-Term Memory (LSTM) architecture. The proposed approach processes the sequential inputs as continuous signals and keeps updating the prediction of the intended action based on the learned action representations. Further, I study the relationships between visual inputs and the physical information, such as finger forces, that involved in the manipulation actions. This is motivated by recent studies in cognitive science which show that the subject’s intention is strongly related to the hand movements during an action execution. Human observers can interpret other’s actions in terms of movements and forces, which can be used to repeat the observed actions. If a robot system has the ability to estimate the force feedbacks, it can learn how to manipulate an object by watching human demonstrations. In this work, the finger forces are estimated by only watching the movement of hands. A modified LSTM model is used to regress the finger forces from video frames. To facilitate this study, a specially designed sensor glove has been used to collect data of finger forces, and a new dataset has been collected to provide synchronized streams of videos and finger forces. Last, I investigate the usefulness of physical information in human action recognition, which is an application of bimodal learning, where both the vision inputs and the additional information are used to learn the action representation. My study demonstrates that, by combining additional information with the vision inputs, the accuracy of human action recognition can be improved steadily. I extend the LSTM architecture to accept both video frames and sensor data as bimodal inputs to predict the action. A hallucination network is jointly trained to approximate the representations of the additional inputs. During the testing stage, the hallucination network generates approximated representations that used for classification. In this way, the proposed method does not rely on the additional inputs for testing.

Trabalho de Projeto do Mestrado Integrado em Engenharia Biomédica apresentado à Faculdade de Ciências e Tecnologia
The recent advances in transcriptome sequencing technologies lead to the increase of gene expression studies, with significant impact in the fields of cellular biology and medicine. Typically, the work developed based on this type of data resorts to feature reduction techniques to combat the problems risen by the curse of dimensionality and from data extraction (such as dropout events, noise, etc.), especially in projects involving classification tasks. This dissertation presents a novel dimensionality reduction model inspired by deep neural networks, the Supervised Autoencoder, which combines the architecture of traditional autoencoders with a SoftMax classification layer, so the latent space maximizes different classes’ separability. To account for the recurring dropout events in this type of datasets, a Dropout layer was implemented during training, improving the model’s robustness. The present study focuses particularly on two-dimensional reductions to ease the information’s visualisation. In addition to an analysis of the effect of label usage in the feature reduction process (prior to potential classification tasks), the possibility of inferring new similarity patterns between samples through the latent space was explored.The model was validated with three datasets, comparing its results with those of Principal Component Analysis and the equivalent simple autoencoder, as well as by analysing the heatmap of the complete gene expression clustered based on the engineered features. The results show the model is capable of meaningful representations of the original data that ease the classification task compared to the ones resultant of state-of-the-art techniques. However, it is not possible to draw new parallels between samples based on those features.
Os recentes avanços nas tecnologias de sequenciação do transcriptoma humano levaram ao aumento de estudos baseados em dados de expressão genética, com notável impacto nas áreas da biologia e medicina. Tipicamente, o trabalho desenvolvido com base neste tipo de informação recorre a técnicas de redução de features para combater os problemas que advêm da curse of dimensionality e associados à extração de dados de expressão (como eventos de dropout, ruído, etc.), sobretudo em projetos com tarefas de classificação.Nesta dissertação apresenta-se um modelo de redução de dimensionalidade inspirado em redes neuronais, o Autoencoder Supervisionado, que acopla a arquitetura tradicional de autoencoders com uma camada de classificação SoftMax, para que as representações no espaço latente maximizem a separabilidade entre diferentes classes. De forma a considerar os recorrentes eventos dropout neste tipo de dados, foi usada uma camada Dropout na fase de treino, conferindo maior robustez ao modelo. O estudo em causa foca-se em particular em reduções para duas dimensões, de forma a facilitar a visualização gráfica de informação. Além da análise do efeito da contabilização de classes no processo de redução de features (a priori de potenciais tarefas de classificação), explorou-se a possibilidade de o espaço latente obtido permitir aferir novos padrões de semelhança entre amostras.O modelo foi validado usando três conjuntos de dados, comparando os seus resultados com os obtidos através de Principal Component Analysis e do autoencoder simples equivalente, bem como através da análise do mapa de calor dos dados completos de expressão genética agrupados através do clustering hierárquico das features reduzidas.Os resultados mostram que o modelo é capaz de gerar representações adequadas dos dados originais, que permitem facilitar a tarefa de classificação quando comparadas com as resultantes das técnicas estado-da-arte. No entanto, não foi possível utilizá-las para estabelecer novos paralelos entre amostras.
Outro - Projeto financiado pela Fundação para a Ciência e Tecnologia: D4 - Deep Drug Discovery and Deployment (CENTRO-01-0145-FEDER-029266)

碩士
國立臺灣大學
資訊工程學研究所
107
Current deep neural network computations incur intensive memory accesses and thus limit the performance of current Von-Neumann architecture. To bridge the performance gap, Processing-In-Memory (PIM) architecture is widely advocated and crossbar accelerators with Resistive Random-Access Memory (ReRAM) are one of the intensively-studied solutions. However, due to the programming variation of ReRAM, crossbar accelerators suffer from the serious accuracy issue. To improve the accuracy, we propose an adaptive data representation strategy to minimize the analog variation errors caused by the programming variation of ReRAM. The proposed strategy was evaluated by a series of intensive experiments based on the data collected from real ReRAM chips, and the results show that the proposed strategy can improve the accuracy for around 20% for MNIST which is close to the ideal case and 40% for CIFAR10.

Recent decades have witnessed the rise of data deluge generated by heterogeneous sources, e.g., social networks, streaming, marketing services etc., which has naturally created a surge of interests in theory and applications of large-scale convex and non-convex optimization. For example, real-world instances of statistical learning problems such as deep learning, recommendation systems, etc. can generate sheer volumes of spatially/temporally diverse data (up to Petabytes of data in commercial applications) with millions of decision variables to be optimized. Such problems are often referred to as Big-data problems. Solving these problems by standard optimization methods demands intractable amount of centralized storage and computational resources which is infeasible and is the foremost purpose of parallel and decentralized algorithms developed in this thesis.

This thesis consists of two parts: (I) Distributed Nonconvex Optimization and (II) Distributed Convex Optimization.

In Part (I), we start by studying a winning paradigm in big-data optimization, Block Coordinate Descent (BCD) algorithm, which cease to be effective when problem dimensions grow overwhelmingly. In particular, we considered a general family of constrained non-convex composite large-scale problems defined on multicore computing machines equipped with shared memory. We design a hybrid deterministic/random parallel algorithm to efficiently solve such problems combining synergically Successive Convex Approximation (SCA) with greedy/random dimensionality reduction techniques. We provide theoretical and empirical results showing efficacy of the proposed scheme in face of huge-scale problems. The next step is to broaden the network setting to general mesh networks modeled as directed graphs, and propose a class of gradient-tracking based algorithms with global convergence guarantees to critical points of the problem. We further explore the geometry of the landscape of the non-convex problems to establish second-order guarantees and strengthen our convergence to local optimal solutions results to global optimal solutions for a wide range of Machine Learning problems.

In Part (II), we focus on a family of distributed convex optimization problems defined over meshed networks. Relevant state-of-the-art algorithms often consider limited problem settings with pessimistic communication complexities with respect to the complexity of their centralized variants, which raises an important question: can one achieve the rate of centralized first-order methods over networks, and moreover, can one improve upon their communication costs by using higher-order local solvers? To answer these questions, we proposed an algorithm that utilizes surrogate objective functions in local solvers (hence going beyond first-order realms, such as proximal-gradient) coupled with a perturbed (push-sum) consensus mechanism that aims to track locally the gradient of the central objective function. The algorithm is proved to match the convergence rate of its centralized counterparts, up to multiplying network factors. When considering in particular, Empirical Risk Minimization (ERM) problems with statistically homogeneous data across the agents, our algorithm employing high-order surrogates provably achieves faster rates than what is achievable by first-order methods. Such improvements are made without exchanging any Hessian matrices over the network.

Finally, we focus on the ill-conditioning issue impacting the efficiency of decentralized first-order methods over networks which rendered them impractical both in terms of computation and communication cost. A natural solution is to develop distributed second-order methods, but their requisite for Hessian information incurs substantial communication overheads on the network. To work around such exorbitant communication costs, we propose a “statistically informed” preconditioned cubic regularized Newton method which provably improves upon the rates of first-order methods. The proposed scheme does not require communication of Hessian information in the network, and yet, achieves the iteration complexity of centralized second-order methods up to the statistical precision. In addition, (second-order) approximate nature of the utilized surrogate functions, improves upon the per-iteration computational cost of our earlier proposed scheme in this setting.

For a long time, there has been little research on dynamic social networks. However, in recent years, there has been much more focus on this field and many techniques for analyzing temporal aspects of social networks were proposed. In this work, we studied a dynamic social network based on data retrieved from the Commercial Register. This registry contains information about all economic entities that operate in the Czech Republic, including people who hold functions in entities and their addresses of living. We applied several data analysis techniques including community tracing, clustering, and methods for identifying key actors to find important entities and individuals in the social network and inspect their changes over time. 1