Tesis sobre el tema "Graph Pooling and Convolution"

With the development of graph neural networks, this novel neural network has been applied in a broader and broader range of fields. One of the thorny problems researchers face in this field is selecting suitable pooling methods for a specific research task from various existing pooling methods. In this work, based on the existing mainstream graph pooling methods, we develop a benchmark neural network framework that can be used to compare these different graph pooling methods. By using the framework, we compare four mainstream graph pooling methods and explore their characteristics. Furthermore, we expand two methods for explaining neural network decisions for convolution neural networks to graph neural networks and compare them with the existing GNNExplainer. We run experiments on standard graph classification tasks using the developed framework and discuss the different pooling methods’ distinctive characteristics. Furthermore, we verify the proposed extensions of the explanation methods’ correctness and measure the agreements among the produced explanations. Finally, we explore the characteristics of different methods for explaining neural network decisions and the insights of different pooling methods by applying these explanation methods.
Med utvecklingen av grafneurala nätverk har detta nya neurala nätverk tillämpats i olika område. Ett av de svåra problemen för forskare inom detta område är hur man väljer en lämplig poolningsmetod för en specifik forskningsuppgift från en mängd befintliga poolningsmetoder. I den här arbetet, baserat på de befintliga vanliga grafpoolingsmetoderna, utvecklar vi ett riktmärke för neuralt nätverk ram som kan användas till olika diagram pooling metoders jämförelse. Genom att använda ramverket jämför vi fyra allmängiltig diagram pooling metod och utforska deras egenskaper. Dessutom utvidgar vi två metoder för att förklara beslut om neuralt nätverk från convolution neurala nätverk till diagram neurala nätverk och jämföra dem med befintliga GNNExplainer. Vi kör experiment av grafisk klassificering uppgifter under benchmarkingramverk och hittade olika egenskaper av olika diagram pooling metoder. Dessutom verifierar vi korrekthet i dessa förklarningsmetoder som vi utvecklade och mäter överenskommelserna mellan dem. Till slut, vi försöker utforska egenskaper av olika metoder för att förklara neuralt nätverks beslut och deras betydelse för att välja pooling metoder i grafisk neuralt nätverk.

De nos jours, les contenus vidéos sont omniprésents grâce à Internet et les smartphones, ainsi que les médias sociaux. De nombreuses applications de la vie quotidienne, telles que la vidéo surveillance et la description de contenus vidéos, ainsi que la compréhension de scènes visuelles, nécessitent des technologies sophistiquées pour traiter les données vidéos. Il devient nécessaire de développer des moyens automatiques pour analyser et interpréter la grande quantité de données vidéo disponibles. Dans cette thèse, nous nous intéressons à la reconnaissance d'actions dans les vidéos, c.a.d au problème de l'attribution de catégories d'actions aux séquences vidéos. Cela peut être considéré comme un ingrédient clé pour construire la prochaine génération de systèmes visuels. Nous l'abordons avec des méthodes d'intelligence artificielle, sous le paradigme de l'apprentissage automatique et de l'apprentissage profond, notamment les réseaux de neurones convolutifs. Les réseaux de neurones convolutifs actuels sont de plus en plus profonds, plus gourmands en données et leur succès est donc tributaire de l'abondance de données d'entraînement étiquetées. Les réseaux de neurones convolutifs s'appuient également sur le pooling qui réduit la dimensionnalité des couches de sortie (et donc atténue leur sensibilité à la disponibilité de données étiquetées)
Nowadays, video contents are ubiquitous through the popular use of internet and smartphones, as well as social media. Many daily life applications such as video surveillance and video captioning, as well as scene understanding require sophisticated technologies to process video data. It becomes of crucial importance to develop automatic means to analyze and to interpret the large amount of available video data. In this thesis, we are interested in video action recognition, i.e. the problem of assigning action categories to sequences of videos. This can be seen as a key ingredient to build the next generation of vision systems. It is tackled with AI frameworks, mainly with ML and Deep ConvNets. Current ConvNets are increasingly deeper, data-hungrier and this makes their success tributary of the abundance of labeled training data. ConvNets also rely on (max or average) pooling which reduces dimensionality of output layers (and hence attenuates their sensitivity to the availability of labeled data); however, this process may dilute the information of upstream convolutional layers and thereby affect the discrimination power of the trained video representations, especially when the learned action categories are fine-grained

Modern Graph Theory is a newly emerging field that involves all of those approaches that study graphs differently from Classic Graph Theory. The main difference between Classic and Modern Graph Theory regards the analysis and the use of graph's structures (micro/macro). The former aims to solve tasks hosted on graph nodes, most of the time with no insight into the global graph structure, the latter aims to analyze and discover the most salient features characterizing a whole network of each graph, like degree distributions, hubs, clustering coefficient and network motifs. The activities carried out during the PhD period concerned, after a careful preliminary study on the applications of the Modern Graph Theory, the development of an innovative Convolutional Model to model brain connections at the cellular level capable of combining exponential models and power law models. This new theoretical framework has been introduced in the first instance with an aspatial graph formulation and then proposed a spatial graph model with Convolutive connectivity able to fit the degree distributions of data driven Connectome reconstructions. In order to evaluate the qualities of the Convolutional Model, theoretical graphical models capable of characterizing brain activity were taken into consideration. In the specific case, the model examined characterizes the epileptic activity through a simple Hindmarsh-Rose model system of point neurons and reproduces the functional characteristics observed in the data driven model. Such a model provides insight into the deep impact of micro connectivity in macro-scale brain activity. Other evaluations have been done in different applications, in the field of image cell segmentation with Explainable Artificial Intelligence's neuronal agents in which has been used a methodology that is not only explainable but also resistant to adversarial noise and also in the field of modelling Covid-19 outbreak in gaining insight on vaccines and role of our habits as individuals in the pandemic spread. Therefore, the core of the thesis is to introduce Modern Graph Theory with a new competitive Convolutive Model and then expose some applications to real-world problems like a characterization of Brain networks, simulation and analysis of Brain dynamics with a particular focus on Epilepsy, Immunofluorescence images segmentation with neuronal based agents and modelling of Covid-19 Epidemic spread with a specific interest in human social networks. All this takes continuously into account the whole dialogue between Graph Theory and its applications.

In recent years we have seen an increase in the number of public transit service disruptions due to aging infrastructure, system failures and the regular need for maintenance. With the fleeting growth in the usage of these transit networks there has been an increase in the need for the timely detection of such disruptions. Any types of disruptions in these transit networks can lead to delays which can have major implications on the daily passengers. Most current disruption detection systems either do not operate in real-time or lack transit network coverage. The theme of this thesis was to leverage Twitter data to help in earlier detection of service disruptions. This work involves developing a pure Data Mining approach and a couple different approaches that use Graph Neural Networks to identify transit disruption related information in Tweets from a live Twitter stream related to the Washington Metropolitan Area Transit Authority (WMATA) metro system. After developing three different models, a Dynamic Query Expansion model, a Tweet-GCN and a Tweet-Level GCN to represent the data corpus we performed various experiments and benchmark evaluations against other existing baseline models, to justify the efficacy of our approaches. After seeing astounding results across both the Tweet-GCN and Tweet-Level GCN, with an average accuracy of approximately 87.3% and 89.9% we can conclude that not only are these two graph neural models superior for basic NLP text classification, but they also outperform other models in identifying transit disruptions.
Master of Science
Millions of people worldwide rely on public transit networks for their daily commutes and day to day movements. With the growth in the number of people using the service, there has been an increase in the number of daily passengers affected by service disruptions. This thesis and research involves proposing and developing three different approaches to help aid in the timely detection of these disruptions. In this work we have developed a pure data mining approach along with two deep learning models using neural networks and live data from Twitter to identify these disruptions. The data mining approach uses a set of dirsuption related input keywords to identify similar keywords within the live Twitter data. By collecting historical data we were able to create deep learning models that represent the vocabulary from the disruptions related Tweets in the form of a graph. A graph is a collection of data values where the data points are connected to one another based on their relationships. A longer chain of connection between two words defines a weak relationship, a shorter chain defines a stronger relationship. In our graph, words with similar contextual meanings are connected to each other over shorter distances, compared to words with different meanings. At the end we use a neural network as a classifier to scan this graph to learn the semantic relationships within our data. Afterwards, this learned information can be used to accurately classify the disruption related Tweets within a pool of random Tweets. Once all the proposed approaches have been developed, a benchmark evaluation is performed against other existing text classification techniques, to justify the effectiveness of the approaches. The final results indicate that the proposed graph based models achieved a higher accuracy, compared to the data mining model, and also outperformed all the other baseline models. Our Tweet-Level GCN had the highest accuracy of 89.9%.

Le reti neurali artificiali hanno visto, negli ultimi anni, una crescita vertiginosa nelle loro applicazioni e nelle architetture dei modelli impiegati. In questa tesi introduciamo le reti neurali su domini euclidei, in particolare mostrando l’importanza dell’equivarianza di traslazione nelle reti convoluzionali, e introduciamo, per analogia, un’estensione della convoluzione a dati strutturati come grafi. Inoltre presentiamo le architetture dei principali Graph Neural Network ed esponiamo, per ognuna delle tre architetture proposte (Spectral graph Convolutional Network, Graph Convolutional Network, Graph Attention neTwork) un’applicazione che ne mostri sia il funzionamento che l’importanza. Discutiamo, ulteriormente, l’implementazione di un algoritmo di classificazione basato su due varianti dell’architettura Graph Convolutional Network, addestrato e testato sul dataset PROTEINS, capace di classificare le proteine del dataset in due categorie: enzimi e non enzimi.

Pour l’apprentissage automatisé de données régulières comme des images ou des signaux sonores, les réseaux convolutifs profonds s’imposent comme le modèle de deep learning le plus performant. En revanche, lorsque les jeux de données sont irréguliers (par example : réseaux de capteurs, de citations, IRMs), ces réseaux ne peuvent pas être utilisés. Dans cette thèse, nous développons une théorie algébrique permettant de définir des convolutions sur des domaines irréguliers, à l’aide d’actions de groupe (ou, plus généralement, de groupoïde) agissant sur les sommets d’un graphe, et possédant des propriétés liées aux arrêtes. A l’aide de ces convolutions, nous proposons des extensions des réseaux convolutifs à des structures de graphes. Nos recherches nous conduisent à proposer une formulation générique de la propagation entre deux couches de neurones que nous appelons la contraction neurale. De cette formule, nous dérivons plusieurs nouveaux modèles de réseaux de neurones, applicables sur des domaines irréguliers, et qui font preuve de résultats au même niveau que l’état de l’art voire meilleurs pour certains
Convolutional neural networks have proven to be the deep learning model that performs best on regularly structured datasets like images or sounds. However, they cannot be applied on datasets with an irregular structure (e.g. sensor networks, citation networks, MRIs). In this thesis, we develop an algebraic theory of convolutions on irregular domains. We construct a family of convolutions that are based on group actions (or, more generally, groupoid actions) that acts on the vertex domain and that have properties that depend on the edges. With the help of these convolutions, we propose extensions of convolutional neural netowrks to graph domains. Our researches lead us to propose a generic formulation of the propagation between layers, that we call the neural contraction. From this formulation, we derive many novel neural network models that can be applied on irregular domains. Through benchmarks and experiments, we show that they attain state-of-the-art performances, and beat them in some cases

Recommender systems are widely used in websites and applications to help users find relevant content based on their interests. Graph neural networks achieved state- of-the- art results in the field of recommender systems, working on data represented in the form of a graph. However, most graph- based solutions hold challenges regarding computational complexity or the ability to generalize to new users. Therefore, we propose a novel graph- based recommender system, by modifying Simple Graph Convolution, an approach for efficient graph node classification, and add the capability of generalizing to new users. We build our proposed recommender system for recommending the articles of Peltarion Knowledge Center. By incorporating two data sources, implicit user feedback based on pageview data as well as the content of articles, we propose a hybrid recommender solution. Throughout our experiments, we compare our proposed solution with a matrix factorization approach as well as a popularity- based and a random baseline, analyse the hyperparameters of our model, and examine the capability of our solution to give recommendations to new users who were not part of the training data set. Our model results in slightly lower, but similar Mean Average Precision and Mean Reciprocal Rank scores to the matrix factorization approach, and outperforms the popularity- based and random baselines. The main advantages of our model are computational efficiency and its ability to give relevant recommendations to new users without the need for retraining the model, which are key features for real- world use cases.
Rekommendationssystem används ofta på webbplatser och applikationer för att hjälpa användare att hitta relevant innehåll baserad på deras intressen. Med utvecklingen av grafneurala nätverk nådde toppmoderna resultat inom rekommendationssystem och representerade data i form av en graf. De flesta grafbaserade lösningar har dock svårt med beräkningskomplexitet eller att generalisera till nya användare. Därför föreslår vi ett nytt grafbaserat rekommendatorsystem genom att modifiera Simple Graph Convolution. De här tillvägagångssätt är en effektiv grafnodsklassificering och lägga till möjligheten att generalisera till nya användare. Vi bygger vårt föreslagna rekommendatorsystem för att rekommendera artiklarna från Peltarion Knowledge Center. Genom att integrera två datakällor, implicit användaråterkoppling baserad på sidvisningsdata samt innehållet i artiklar, föreslår vi en hybridrekommendatörslösning. Under våra experiment jämför vi vår föreslagna lösning med en matrisfaktoriseringsmetod samt en popularitetsbaserad och en slumpmässig baslinje, analyserar hyperparametrarna i vår modell och undersöker förmågan hos vår lösning att ge rekommendationer till nya användare som inte deltog av träningsdatamängden. Vår modell resulterar i något mindre men liknande Mean Average Precision och Mean Reciprocal Rank poäng till matrisfaktoriseringsmetoden och överträffar de popularitetsbaserade och slumpmässiga baslinjerna. De viktigaste fördelarna med vår modell är beräkningseffektivitet och dess förmåga att ge relevanta rekommendationer till nya användare utan behov av omskolning av modellen, vilket är nyckelfunktioner för verkliga användningsfall.

Lo scopo del geometric deep learning è quello di estendere l'algoritmo di deep learning sviluppato per la classificazione di immagini a domini non euclidei come grafi e complessi simpliciali.In questa tesi ci proponiamo di dare una definizione matematica dei concetti cardine utilizzati nel geometric deep learning quali equivarianza e convoluzione sui grafi. Vedremo inoltre come definire una rete convoluzionale invariante rispetto all'azione di gruppi.

Le but de cette thèse est d'étudier la reconnaissance d'insectes comme un problème de reconnaissance des formes basé images. Bien que ce problème ait été étudié en profondeur au long des trois dernières décennies, un aspect reste selon nous toujours à expérimenter à ce jour : les approches profondes (deep learning). À cet effet, la première contribution de cette thèse consiste à déterminer la faisabilité de l'application des réseaux de neurones convolutifs profonds (CNN) au problème de reconnaissance d'images d'insectes. Les limitations majeures ont les suivantes: les images sont très rares et les cardinalités de classes sont hautement déséquilibrées. Pour atténuer ces limitations, le transfer learning et la pondération de la fonction de coûts ont été employés. Des méthodes basées graphes sont également proposées et testées. La première consiste en la conception d'un classificateur de graphes de type perceptron. Le second travail basé sur les graphes de cette thèse est la définition d'un opérateur de convolution pour construire un modèle de réseaux de neurones convolutifs s'appliquant sur les graphes (GCNN.) Le dernier chapitre de la thèse s'applique à utiliser les méthodes mentionnées précédemment à des problèmes de reconnaissance d'images d'insectes. Deux bases d'images sont ici proposées. Là première est constituée d'images prises en laboratoire sur arrière-plan constant. La seconde base est issue de la base ImageNet. Cette base est composée d'images prises en contexte naturel. Les CNN entrainés avec transfer learning sont les plus performants sur ces bases d'images
The goal of this thesis is to investigate insect recognition as an image-based pattern recognition problem. Although this problem has been extensively studied along the previous three decades, an element is to the best of our knowledge still to be experimented as of 2017: deep approaches. Therefore, a contribution is about determining to what extent deep convolutional neural networks (CNNs) can be applied to image-based insect recognition. Graph-based representations and methods have also been tested. Two attempts are presented: The former consists in designing a graph-perceptron classifier and the latter graph-based work in this thesis is on defining convolution on graphs to build graph convolutional neural networks. The last chapter of the thesis deals with applying most of the aforementioned methods to insect image recognition problems. Two datasets are proposed. The first one consists of lab-based images with constant background. The second one is generated by taking a ImageNet subset. This set is composed of field-based images. CNNs with transfer learning are the most successful method applied on these datasets

Le graphe est un concept puissant pour la représentation des relations entre des paires d'entités. Les données ayant une structure de graphes sous-jacente peuvent être trouvées dans de nombreuses disciplines, décrivant des composés chimiques, des surfaces des modèles tridimensionnels, des interactions sociales ou des bases de connaissance, pour n'en nommer que quelques-unes. L'apprentissage profond (DL) a accompli des avancées significatives dans une variété de tâches d'apprentissage automatique au cours des dernières années, particulièrement lorsque les données sont structurées sur une grille, comme dans la compréhension du texte, de la parole ou des images. Cependant, étonnamment peu de choses ont été faites pour explorer l'applicabilité de DL directement sur des données structurées sous forme des graphes. L'objectif de cette thèse est d'étudier des architectures de DL sur des graphes et de rechercher comment transférer, adapter ou généraliser à ce domaine des concepts qui fonctionnent bien sur des données séquentielles et des images. Nous nous concentrons sur deux primitives importantes : le plongement de graphes ou leurs nœuds dans une représentation de l'espace vectorielle continue (codage) et, inversement, la génération des graphes à partir de ces vecteurs (décodage). Nous faisons les contributions suivantes. Tout d'abord, nous introduisons Edge-Conditioned Convolutions (ECC), une opération de type convolution sur les graphes réalisés dans le domaine spatial où les filtres sont générés dynamiquement en fonction des attributs des arêtes. La méthode est utilisée pour coder des graphes avec une structure arbitraire et variable. Deuxièmement, nous proposons SuperPoint Graph, une représentation intermédiaire de nuages de points avec de riches attributs des arêtes codant la relation contextuelle entre des parties des objets. Sur la base de cette représentation, l'ECC est utilisé pour segmenter les nuages de points à grande échelle sans sacrifier les détails les plus fins. Troisièmement, nous présentons GraphVAE, un générateur de graphes permettant de décoder des graphes avec un nombre de nœuds variable mais limité en haut, en utilisant la correspondance approximative des graphes pour aligner les prédictions d'un auto-encodeur avec ses entrées. La méthode est appliquée à génération de molécules
Graph is a powerful concept for representation of relations between pairs of entities. Data with underlying graph structure can be found across many disciplines, describing chemical compounds, surfaces of three-dimensional models, social interactions, or knowledge bases, to name only a few. There is a natural desire for understanding such data better. Deep learning (DL) has achieved significant breakthroughs in a variety of machine learning tasks in recent years, especially where data is structured on a grid, such as in text, speech, or image understanding. However, surprisingly little has been done to explore the applicability of DL on graph-structured data directly.The goal of this thesis is to investigate architectures for DL on graphs and study how to transfer, adapt or generalize concepts working well on sequential and image data to this domain. We concentrate on two important primitives: embedding graphs or their nodes into a continuous vector space representation (encoding) and, conversely, generating graphs from such vectors back (decoding). To that end, we make the following contributions.First, we introduce Edge-Conditioned Convolutions (ECC), a convolution-like operation on graphs performed in the spatial domain where filters are dynamically generated based on edge attributes. The method is used to encode graphs with arbitrary and varying structure.Second, we propose SuperPoint Graph, an intermediate point cloud representation with rich edge attributes encoding the contextual relationship between object parts. Based on this representation, ECC is employed to segment large-scale point clouds without major sacrifice in fine details.Third, we present GraphVAE, a graph generator allowing to decode graphs with variable but upper-bounded number of nodes making use of approximate graph matching for aligning the predictions of an autoencoder with its inputs. The method is applied to the task of molecule generation

This paper is focus on flowers recognition in an image and class classification. Theoretical part is focus on problematics of deep convolutional neural networks. The practical part if focuse on created flowers database, with which it is further worked on. The database conteins it total 13000 plant pictures of 26 spicies as cornflower, violet, gerbera, cha- momile, cornflower, liverwort, hawkweed, clover, carnation, lily of the valley, marguerite daisy, pansy, poppy, marigold, daffodil, dandelion, teasel, forget-me-not, rose, anemone, daisy, sunflower, snowdrop, ragwort, tulip and celandine. Next is in the paper described used neural network model Inception v3 for class classification. The resulting accuracy has been achieved 92%.

This master´s thesis deals with the reseach of technologies using deep learning method, being able to use when processing image data. Specific focus of the work is to evaluate the suitability and effectiveness of deep learning when comparing two image input data. The first – theoretical – part consists of the introduction to neural networks and deep learning. Also, it contains a description of available methods, their benefits and principles, used for processing image data. The second - practical - part of the thesis contains a proposal a appropriate model of Siamese networks to solve the problem of comparing two input image data and evaluating their similarity. The output of this work is an evaluation of several possible model configurations and highlighting the best-performing model parameters.

Cette thèse a pour but de développer des approches déterministes et heuristiques pour résoudre certaines classes des problèmes d'optimisation en télécommunication et la mobilité d'un réseau de transport : problèmes de routage, problèmes de covoiturage, problèmes de contrôle de l'alimentation dans un réseau sans fil, problèmes d'équilibrage du spectre dans les réseaux DSL. Il s'agit des problèmes d'optimisation non convexe de très grande taille. Nos approches sont basées sur la programmation DC&DCA, méthode de décomposition proximale et la méthode d'étiquetage des graphes. Grâce aux techniques de formulation/reformulation et de pénalité exacte, nous avons établi des programmes DC équivalents en vue de leur résolution par DCA. Selon la structure de ces problèmes, on peut fournir des décompositions DC appropriées ou de bons points initiaux de DCA. Nos méthodes ont été programmées sous MATLAB, C/C++. Ils montrent la performance de nos algorithmes par rapport à des méthodes existantes.

博士
國立交通大學
應用數學系所
101
This dissertation contains three quite different subjects: posets, distance-regular graphs, and spectral graph theory. Motivated by the constructions of pooling designs, we study these three subjects through interesting links among them. A pooling space is a ranked poset P such that the subposet w+ induced by the elements above w is atomic for each element w of P. Pooling spaces were introduced in [Discrete Mathematics 282:163-169, 2004] for the purpose of giving a uniform way to construct pooling designs, which have applications to the screening of DNA sequences. We find that a geometric lattice, a well-studied structure in literature, is also a pooling space. This provides us many classes of pooling designs, some old and some new. Following the same concept, the poset constructed from a distance-regular graph with its distance-regular subgraphs is also a pooling space. For a special class of distance-regular graphs, we show the existence of their distance-regular subgraphs with any given diameter. The nonexistence of a class of distance-regular graphs follows from the line of study. Distance-regular graphs appear often in some extremal class of combinatorial or linear algebraic inequalities. As we can see from the inequality of arithmetic and geometric means of a sequence of positive real numbers, the equality occurs when the sequence has some regular patterns. We consider the maximum eigenvalues of the adjacency matrices of graphs and present sharp upper bounds of them. The graphs which attain the bounds also satisfy a special kind of regularity.

碩士
國立高雄大學
應用數學系碩博士班
107
The model of classical group testing is: given n items, at most d of them are defective, we want to find out all of the defectives using the minimum number of tests that are applied on a subset of these items. In a nonadaptive algorithm, also called a pooling design, one must decide all tests before any testing occurs. Pooling designs play an important role in the field of group testing, there are many applications such as blood testing, quality controlling and DNA screening. Error-correcting pooling design uses (d; z)-disjunct matrices. A binary matrix M is called (d; z)-disjunct if given any d + 1 columns of M with one designated, there are z rows intersecting the designated column and none of the other d columns. A (d; z)-disjunct matrix is called completely (d; z)-disjunct if it is not (d; z1)-disjunct whenever z1 > z. Let M(m,m,d) be the 01-matrix whose rows are indexed by all d-matchings on K2m and whose columns are indexed by all perfect matchings on K2m. M(m,m,d) has a 1 in row i and column j if and only if the i-th d-matching is contained in the j-th m-matching. In this thesis, we study a pooling design M(m,m,d) and find its corresponding error-tolerance capabilities. Our results are divided into three parts: when m-d = 1 (resp. m-d = 2), M(m,m,d) is completely (d; z)-disjunct with z = m (resp. z =("m" ¦"2" )-d); when m≥d+3 and 1 ≤ d ≤ ⌊"m" /"2" ⌋, M(m,m,d) is completely (d; "2" ^"d" )-disjunct; when m≥d+3 and ⌊"m" /"2" ⌋< d < m, M(m,m,d) is completely (d; z)-disjunct where z = O("4" ^"(2d−m)/3" ∙"3" ^"m−d" ).

Le discours haineux est un problème sérieux sur les média sociaux. Dans ce mémoire, nous étudions le problème de détection automatique du langage haineux sur réseaux sociaux. Nous traitons ce problème comme un problème de classification de textes. La classification de textes a fait un grand progrès ces dernières années grâce aux techniques d’apprentissage profond. En particulier, les modèles utilisant un mécanisme d’attention tel que BERT se sont révélés capables de capturer les informations contextuelles contenues dans une phrase ou un texte. Cependant, leur capacité à saisir l’information globale sur le vocabulaire d’une langue dans une application spécifique est plus limitée. Récemment, un nouveau type de réseau de neurones, appelé Graph Convolutional Network (GCN), émerge. Il intègre les informations des voisins en manipulant un graphique global pour prendre en compte les informations globales, et il a obtenu de bons résultats dans de nombreuses tâches, y compris la classification de textes. Par conséquent, notre motivation dans ce mémoire est de concevoir une méthode qui peut combiner à la fois les avantages du modèle BERT, qui excelle en capturant des informations locales, et le modèle GCN, qui fournit les informations globale du langage. Néanmoins, le GCN traditionnel est un modèle d'apprentissage transductif, qui effectue une opération convolutionnelle sur un graphe composé d'éléments à traiter dans les tâches (c'est-à-dire un graphe de documents) et ne peut pas être appliqué à un nouveau document qui ne fait pas partie du graphe pendant l'entraînement. Dans ce mémoire, nous proposons d'abord un nouveau modèle GCN de vocabulaire (VGCN), qui transforme la convolution au niveau du document du modèle GCN traditionnel en convolution au niveau du mot en utilisant les co-occurrences de mots. En ce faisant, nous transformons le mode d'apprentissage transductif en mode inductif, qui peut être appliqué à un nouveau document. Ensuite, nous proposons le modèle Interactive-VGCN-BERT qui combine notre modèle VGCN avec BERT. Dans ce modèle, les informations locales captées par BERT sont combinées avec les informations globales captées par VGCN. De plus, les informations locales et les informations globales interagissent à travers différentes couches de BERT, ce qui leur permet d'influencer mutuellement et de construire ensemble une représentation finale pour la classification. Via ces interactions, les informations de langue globales peuvent aider à distinguer des mots ambigus ou à comprendre des expressions peu claires, améliorant ainsi les performances des tâches de classification de textes. Pour évaluer l'efficacité de notre modèle Interactive-VGCN-BERT, nous menons des expériences sur plusieurs ensembles de données de différents types -- non seulement sur le langage haineux, mais aussi sur la détection de grammaticalité et les commentaires sur les films. Les résultats expérimentaux montrent que le modèle Interactive-VGCN-BERT surpasse tous les autres modèles tels que Vanilla-VGCN-BERT, BERT, Bi-LSTM, MLP, GCN et ainsi de suite. En particulier, nous observons que VGCN peut effectivement fournir des informations utiles pour aider à comprendre un texte haiteux implicit quand il est intégré avec BERT, ce qui vérifie notre intuition au début de cette étude.
Hate speech is a serious problem on social media. In this thesis, we investigate the problem of automatic detection of hate speech on social media. We cast it as a text classification problem. With the development of deep learning, text classification has made great progress in recent years. In particular, models using attention mechanism such as BERT have shown great capability of capturing the local contextual information within a sentence or document. Although local connections between words in the sentence can be captured, their ability of capturing certain application-dependent global information and long-range semantic dependency is limited. Recently, a new type of neural network, called the Graph Convolutional Network (GCN), has attracted much attention. It provides an effective mechanism to take into account the global information via the convolutional operation on a global graph and has achieved good results in many tasks including text classification. In this thesis, we propose a method that can combine both advantages of BERT model, which is excellent at exploiting the local information from a text, and the GCN model, which provides the application-dependent global language information. However, the traditional GCN is a transductive learning model, which performs a convolutional operation on a graph composed of task entities (i.e. documents graph) and cannot be applied directly to a new document. In this thesis, we first propose a novel Vocabulary GCN model (VGCN), which transforms the document-level convolution of the traditional GCN model to word-level convolution using a word graph created from word co-occurrences. In this way, we change the training method of GCN, from the transductive learning mode to the inductive learning mode, that can be applied to new documents. Secondly, we propose an Interactive-VGCN-BERT model that combines our VGCN model with BERT. In this model, local information including dependencies between words in a sentence, can be captured by BERT, while the global information reflecting the relations between words in a language (e.g. related words) can be captured by VGCN. In addition, local information and global information can interact through different layers of BERT, allowing them to influence mutually and to build together a final representation for classification. In so doing, the global language information can help distinguish ambiguous words or understand unclear expressions, thereby improving the performance of text classification tasks. To evaluate the effectiveness of our Interactive-VGCN-BERT model, we conduct experiments on several datasets of different types -- hate language detection, as well as movie review and grammaticality, and compare them with several state-of-the-art baseline models. Experimental results show that our Interactive-VGCN-BERT outperforms all other models such as Vanilla-VGCN-BERT, BERT, Bi-LSTM, MLP, GCN, and so on. In particular, we have found that VGCN can indeed help understand a text when it is integrated with BERT, confirming our intuition to combine the two mechanisms.

abstract: Mostly, manufacturing tolerance charts are used these days for manufacturing tolerance transfer but these have the limitation of being one dimensional only. Some research has been undertaken for the three dimensional geometric tolerances but it is too theoretical and yet to be ready for operator level usage. In this research, a new three dimensional model for tolerance transfer in manufacturing process planning is presented that is user friendly in the sense that it is built upon the Coordinate Measuring Machine (CMM) readings that are readily available in any decent manufacturing facility. This model can take care of datum reference change between non orthogonal datums (squeezed datums), non-linearly oriented datums (twisted datums) etc. Graph theoretic approach based upon ACIS, C++ and MFC is laid out to facilitate its implementation for automation of the model. A totally new approach to determining dimensions and tolerances for the manufacturing process plan is also presented. Secondly, a new statistical model for the statistical tolerance analysis based upon joint probability distribution of the trivariate normal distributed variables is presented. 4-D probability Maps have been developed in which the probability value of a point in space is represented by the size of the marker and the associated color. Points inside the part map represent the pass percentage for parts manufactured. The effect of refinement with form and orientation tolerance is highlighted by calculating the change in pass percentage with the pass percentage for size tolerance only. Delaunay triangulation and ray tracing algorithms have been used to automate the process of identifying the points inside and outside the part map. Proof of concept software has been implemented to demonstrate this model and to determine pass percentages for various cases. The model is further extended to assemblies by employing convolution algorithms on two trivariate statistical distributions to arrive at the statistical distribution of the assembly. Map generated by using Minkowski Sum techniques on the individual part maps is superimposed on the probability point cloud resulting from convolution. Delaunay triangulation and ray tracing algorithms are employed to determine the assembleability percentages for the assembly.
Dissertation/Thesis
Ph.D. Mechanical Engineering 2011

In this thesis we study an application of dynamic programming technique to graph problems and approximation algorithms. We improve upon state-of-the-art algorithms for All-Nodes Shortest Cycles, distance oracles, approximate algorithm for Partition, weak approximation for Subset Sum and others. We also present equivalence classes for certain problems, that admit algorithms based on dynamic programming. Namely: • (min, +)-convolution and knapsack problem, • (min, max)-convolution and strongly polynomial approximate (min, max) - convolution, • (min, max)-product and strongly polynomial approximate all-pairs shortest path.
W rozprawie przedstawiamy nowe techniki analizy algorytmów opartych na programowaniu dynamicznym. Używamy ich do rozwiązywania problemów na grafach i przyśpieszeniu wybranych algorytmów aproksymacyjnych. Zaproponowane przez nas metody pozwalają na usprawnienie obecnie znanych algorytmów dla znajdywania najkrótszych cykli, wyroczni odległości, problemów aproksymacyjnych związanych z problemem plecakowym i innych. W rozprawie proponujemy także klasy równoważności dla wybranych problemów, które mają efektywne algorytmy oparte na programowaniu dynamicznym. W szczególności: • (min, +)-konwolucji i problemu plecakowego, • (min, max)-konwolucji i silnie wielomianowej aproksymacji dla (min, +)-konwolucji, • (min, max)-produktu i silnie wielomianowej aproksymacji dla znajdywania najkrótszych ścieżek w grafie.

Title: Hybrid Deep Question Answering Author: Ahmad Aghaebrahimian Institute: Institute of Formal and Applied Linguistics Supervisor: RNDr. Martin Holub, Ph.D., Institute of Formal and Applied Lin- guistics Abstract: As one of the oldest tasks of Natural Language Processing, Question Answering is one of the most exciting and challenging research areas with lots of scientific and commercial applications. Question Answering as a discipline in the conjunction of computer science, statistics, linguistics, and cognitive science is concerned with building systems that automatically retrieve answers to ques- tions posed by humans in a natural language. This doctoral dissertation presents the author's research carried out in this discipline. It highlights his studies and research toward a hybrid Question Answering system consisting of two engines for Question Answering over structured and unstructured data. The structured engine comprises a state-of-the-art Question Answering system based on knowl- edge graphs. The unstructured engine consists of a state-of-the-art sentence-level Question Answering system and a word-level Question Answering system with results near to human performance. This work introduces a new Question An- swering dataset for answering word- and sentence-level questions as well. Start- ing from a...