We consider the problem of maximizing the second smallest eigenvalue of the weighted Laplacian of a (simple) graph over all nonnegative edge weightings with bounded total weight. We generalize this problem by introducing node significances and edge lengths. We give a formulation of this generalized problem as a semidefinite program. The dual program can be equivalently written as embedding problem. This is fifinding an embedding of the n nodes of the graph in n-space so that their barycenter is at the origin, the distance between adjacent nodes is bounded by the respective edge length, and the embedded nodes are spread as much as possible. (The sum of the squared norms is maximized.) We proof the following necessary condition for optimal embeddings. For any separator of the graph at least one of the components fulfills the following property: Each straight-line segment between the origin and an embedded node of the component intersects the convex hull of the embedded nodes of the separator. There exists always an optimal embedding of the graph whose dimension is bounded by the tree-width of the graph plus one. We defifine the rotational dimension of a graph. This is the minimal dimension k such that for all choices of the node significances and edge lengths an optimal embedding of the graph can be found in k-space. The rotational dimension of a graph is a minor monotone graph parameter. We characterize the graphs with rotational dimension up to two.:1 Introduction 1.1 Notations and Preliminaries 1.2 The Algebraic Connectivity 1.3 Two applications 1.4 Outline 2 The Embedding Problem 2.1 Semidefinite formulation 2.2 The dual as geometric embedding problem 2.3 Physical interpretation and examples 2.4 Formulation without fifixed barycenter 3 Geometrical Operations 3.1 Congruent transformations 3.2 Folding a flat halfspace 3.3 Folding and Collapsing 4 Structural properties of optimal embeddings 4.1 Separator-Shadow 4.2 Separators containing the origin 4.3 The tree-width bound 4.4 Application to trees 5 The Rotational Dimension of a graph 5.1 Defifinition and basic properties 5.2 Characterization of graphs with small rotational dimension 5.3 The Colin de Verdi ere graph parameter List of Figures Bibliography Theses

The use of Deep Learning methods for Document Understanding has been embraced by the research community in recent years. A requirement for Deep Learning methods and especially Transformer Networks, is access to large datasets. The objective of this thesis was to evaluate a state-of-the-art model for Document Layout Analysis on a public and custom dataset. Additionally, the objective was to build a pipeline for building a dataset specifically for Visually Rich Documents. The research methodology consisted of a literature study to find the state-of-the-art model for Document Layout Analysis and a relevant dataset used to evaluate the chosen model. The literature study also included research on how existing datasets in the domain were collected and processed. Finally, an evaluation framework was created. The evaluation showed that the chosen multi-modal transformer network, LayoutLMv2, performed well on the Docbank dataset. The custom build dataset was limited by class imbalance, although good performance for the larger classes. The annotator tool and its auto-tagging feature performed well and the proposed pipelined showed great promise for creating datasets with Visually Rich Documents. In conclusion, this thesis project answers the research questions and suggests two main opportunities. The first is to encourage others to build datasets with Visually Rich Documents using a similar pipeline to the one presented in this paper. The second is to evaluate the possibility of creating the visual token information for LayoutLMv2 as part of the transformer network rather than using a separate CNN. / Användningen av Deep Learning-metoder för dokumentförståelse har anammats av forskarvärlden de senaste åren. Ett krav för Deep Learning-metoder och speciellt Transformer Networks är tillgång till stora datamängder. Syftet med denna avhandling var att utvärdera en state-of-the-art modell för analys av dokumentlayout på en offentligt tillgängligt dataset. Dessutom var målet att bygga en pipeline för att bygga en dataset specifikt för Visuallt Rika Dokument. Forskningsmetodiken bestod av en litteraturstudie för att hitta modellen för Document Layout Analys och ett relevant dataset som användes för att utvärdera den valda modellen. Litteraturstudien omfattade också forskning om hur befintliga dataset i domänen samlades in och bearbetades. Slutligen skapades en utvärderingsram. Utvärderingen visade att det valda multimodala transformatornätverket, LayoutLMv2, fungerade bra på Docbank-datasetet. Den skapade datasetet begränsades av klassobalans även om bra prestanda för de större klasserna erhölls. Annotatorverktyget och dess autotaggningsfunktion fungerade bra och den föreslagna pipelinen visade sig vara mycket lovande för att skapa dataset med VVisuallt Rika Dokument.svis besvarar detta examensarbete forskningsfrågorna och föreslår två huvudsakliga möjligheter. Den första är att uppmuntra andra att bygga datauppsättningar med Visuallt Rika Dokument med en liknande pipeline som den som presenteras i denna uppsats. Det andra är att utvärdera möjligheten att skapa den visuella tokeninformationen för LayoutLMv2 som en del av transformatornätverket snarare än att använda en separat CNN.

Alzheimer’s sjukdom är en neurodegenerativ sjukdom som leder till demens. Den kan börja tyst i de tidiga stadierna och fortsätta under åren till en allvarlig och obotlig fas. Språkstörningar uppstår ofta som ett av de tidiga symptomen och kan till slut leda till fullständig mutism i de avancerade stadierna av sjukdomen. Därför är tal- och språkbaserad analys en lovande och icke-invasiv metod för att upptäcka Alzheimer’s sjukdom i dess tidiga stadier. Vårt mål är att använda maskininlärning för att jämföra informationmängden hos språkliga representationer i stora språkmodeller och förtränade akustiska representationer. Såvitt vi vet är detta första gången som GPT-3 och wav2vec2.0 har använts tillsammans för klassificering av Alzheimer’s sjukdom. Dessutom utnyttjade vi för första gången en kombination av två stora språkmodeller, GPT-3 och BERT, för denna specifika uppgift. Genom att utvärdera vår metod på två datamängder på engelska och svenska kan vi också belysa språkskillnaderna mellan dessa två språk. / Alzheimer’s disease is a neurodegenerative disease that leads to dementia. It can begin silently in the early stages and progresses over the years to a severe and incurable stage. Language impairment often emerges as one of the early symptoms and can eventually progress to complete mutism in advanced stages of the disease. As a result, speech processing is a promising and non-invasive approach for detecting Alzheimer’s disease in its early stages. Our objective is to compare the informativeness levels of linguistic embedding derived from large language models and pre-trained acoustic embedding extracted using wav2vec2.0, in a machine learning-based approach. To the best of our knowledge, this is the first time that fusing GPT-3 text embedding and wav2vec2.0 acoustic embedding has been explored for Alzheimer’s disease classification. In addition, we utilized a combination of two large language models, GPT-3 and BERT, for the first time on this specific task. By evaluating our method on two datasets in English and Swedish, we can also highlight the language differences between these two languages.

Le regroupement est une tâche non supervisée consistant à rassembler les éléments semblables sous un même groupe et les éléments différents dans des groupes distincts. Le regroupement de textes est effectué en représentant les textes dans un espace vectoriel et en étudiant leur similarité dans cet espace. Les meilleurs résultats sont obtenus à l’aide de modèles neuronaux qui affinent une représentation vectorielle contextuelle de manière non supervisée. Or, cette technique peuvent nécessiter un temps d’entraînement important et sa performance n’est pas comparée à des techniques plus simples ne nécessitant pas l’entraînement de modèles neuronaux. Nous proposons, dans ce mémoire, une étude de l’état actuel du domaine. Tout d’abord, nous étudions les meilleures métriques d’évaluation pour le regroupement de textes. Puis, nous évaluons l’état de l’art et portons un regard critique sur leur protocole d’entraînement. Nous proposons également une analyse de certains choix d’implémentation en regroupement de textes, tels que le choix de l’algorithme de regroupement, de la mesure de similarité, de la représentation vectorielle ou de l’affinage non supervisé de la représentation vectorielle. Finalement, nous testons la combinaison de certaines techniques ne nécessitant pas d’entraînement avec la représentation vectorielle contextuelle telles que le prétraitement des données, la réduction de dimensionnalité ou l’inclusion de Tf-idf. Nos expériences démontrent certaines lacunes dans l’état de l’art quant aux choix des métriques d’évaluation et au protocole d’entraînement. De plus, nous démontrons que l’utilisation de techniques simples permet d’obtenir des résultats meilleurs ou semblables à des méthodes sophistiquées nécessitant l’entraînement de modèles neuronaux. Nos expériences sont évaluées sur huit corpus issus de différents domaines. / Clustering is an unsupervised task of bringing similar elements in the same cluster and different elements in distinct groups. Text clustering is performed by representing texts in a vector space and studying their similarity in this space. The best results are obtained using neural models that fine-tune contextual embeddings in an unsupervised manner. However, these techniques require a significant amount of training time and their performance is not compared to simpler techniques that do not require training of neural models. In this master’s thesis, we propose a study of the current state of the art. First, we study the best evaluation metrics for text clustering. Then, we evaluate the state of the art and take a critical look at their training protocol. We also propose an analysis of some implementation choices in text clustering, such as the choice of clustering algorithm, similarity measure, contextual embeddings or unsupervised fine-tuning of the contextual embeddings. Finally, we test the combination of contextual embeddings with some techniques that don’t require training such as data preprocessing, dimensionality reduction or Tf-idf inclusion. Our experiments demonstrate some shortcomings in the state of the art regarding the choice of evaluation metrics and the training protocol. Furthermore, we demonstrate that the use of simple techniques yields better or similar results to sophisticated methods requiring the training of neural models. Our experiments are evaluated on eight benchmark datasets from different domains.

No description available.

This paper researches how different amounts of data affect different word vector models for classification of dialog system user input. A hypothesis is tested that there is a data threshold for dense vector models to reach the state-of-the-art performance that have been shown with recent research, and that character-level n-gram word-vector classifiers are especially suited for Swedish classifiers–because of compounding and the character-level n-gram model ability to vectorize out-of-vocabulary words. Also, a second hypothesis is put forward that models trained with single statements are more suitable for chat user input classification than models trained with full conversations. The results are not able to support neither of our hypotheses but show that sparse vector models perform very well on the binary classification tasks used. Further, the results show that 799,544 words of data is insufficient for training dense vector models but that training the models with full conversations is sufficient for single statement classification as the single-statement- trained models do not show any improvement in classifying single statements. / Detta arbete undersöker hur olika datamängder påverkar olika slags ordvektormodeller för klassificering av indata till dialogsystem. Hypotesen att det finns ett tröskelvärde för träningsdatamängden där täta ordvektormodeller när den högsta moderna utvecklingsnivån samt att n-gram-ordvektor-klassificerare med bokstavs-noggrannhet lämpar sig särskilt väl för svenska klassificerare söks bevisas med stöd i att sammansättningar är särskilt produktiva i svenskan och att bokstavs-noggrannhet i modellerna gör att tidigare osedda ord kan klassificeras. Dessutom utvärderas hypotesen att klassificerare som tränas med enkla påståenden är bättre lämpade att klassificera indata i chattkonversationer än klassificerare som tränats med hela chattkonversationer. Resultaten stödjer ingendera hypotes utan visar istället att glesa vektormodeller presterar väldigt väl i de genomförda klassificeringstesterna. Utöver detta visar resultaten att datamängden 799 544 ord inte räcker till för att träna täta ordvektormodeller väl men att konversationer räcker gott och väl för att träna modeller för klassificering av frågor och påståenden i chattkonversationer, detta eftersom de modeller som tränats med användarindata, påstående för påstående, snarare än hela chattkonversationer, inte resulterar i bättre klassificerare för chattpåståenden.

The field of generative graph models has seen increased popularity during recent years as it allows us to model the underlying distribution of a network and thus recreate it. From allowing anonymization of sensitive information in social networks to data augmentation of rare diseases in the brain, the ability to generate synthetic data has multiple applications in various domains. However, most current methods face the bottleneck of trying to generate the entire adjacency matrix and are thus limited to graphs with less than tens of thousands of nodes. In contrast, large real-world graphs like social networks or transaction graphs can extend significantly beyond these boundaries. Furthermore, the current scalable approaches are predominantly based on stochasticity and do not capture local structures and communities. In this paper, we propose Graphwave Edge-Linking CELL or GELCELL, a novel three-step architecture for generating graphs at scale. First, instead of constructing the entire network, GELCELL partitions the data and generates each cluster separately, allowing for efficient and parallelizable training. Then, by encoding the nodes, it trains a classifier to predict the edges between the partitions to patch them together, creating a synthetic version of the original large graph. Although it does suffer from some limitations due to necessary constraints on the cluster sizes, the results showed that GELCELL, given optimized parameters, can produce graphs with reasonable accuracy on all data tested, with the largest having 400 000 nodes and 1 000 000 edges. / Generativa grafmodeller har sett ökad popularitet under de senaste åren eftersom det möjliggör modellering av grafens underliggande distribution, och vi kan på så sätt återskapa liknande kopior. Förmågan att generera syntetisk data har ett flertal applikationsområden i en mängd av områden, allt från att möjligöra anonymisering av känslig data i sociala nätverk till att utöka mängden tillgänglig data av ovanliga hjärnsjukdomar. Dagens metoder har länge varit begränsade till grafer med under tiotusental noder, då dessa inte är tillräckligt skalbara, men grafer som sociala nätverk eller transaktionsgrafer kan sträcka sig långt utöver dessa gränser. Dessutom är de nuvarande skalbara tillvägagångssätten till största delen baserade på stokasticitet och fångar inte lokala strukturer och kluster. I denna rapport föreslår vi ”Graphwave EdgeLinking CELL” eller GELCELL, en trestegsarkitektur för att generera grafer i större skala. Istället för att återskapa hela grafen direkt så partitionerar GELCELL all datat och genererar varje kluster separat, vilket möjliggör både effektiv och parallelliserbar träning. Vi kan sedan koppla samman grafen genom att koda noderna och träna en modell för att prediktera länkarna mellan kluster och återskapa en syntetisk version av originalet. Metoden kräver vissa antaganden gällande max-storleken på dess kluster men är flexibel och kan rymma domänkännedom om en specifik graf i form av informerad parameterinställning. Trots detta visar resultaten på varierade träningsdata att GELCELL, givet optimerade parametrar, är kapabel att genera grafer med godtycklig precision upp till den största beprövade grafen med 400 000 noder och 1 000 000 länkar.

On étudie la conjecture des graphes jumeaux dénombrables, cas spécifique d’une conjecture de Thomassé, qui dit que le nombre de jumeaux d’un graphe dénombrable ( ses sous-graphes propres desquels il est aussi un sous-graphe propre) est soit nul, soit infini. On commence par étudier les graphes auto-abrités, que nous définissons, et en utilisant notre classification de ces graphes nous prouvons la conjecture dans certains cas, en précisant la cardinalité exacte du nombre de jumeaux. Nous donnons également des contre-exemples à l’article de l’arXiv «Self-contained graphs». / We make progress on the Graph Alternative Conjecture, a special case of a conjecture of Thomassé which says that the number of twins of a countable graph (i.e. its proper subgraphs of which that graph is also a proper subgraph) is either null or infinite. We begin by studying self-embedded graphs, which we define, and using our classification of these graphs, we prove the conjecture in some cases while specifying the exact number of twins. We also give counter-examples to a paper on arXiv called "Self-contained graphs".

Knowledge Tracing aims to predict future performance of users of learning platforms based on historical data, by modeling their knowledge state. In this task, the target is a binary variable representing the correctness of the exercise, where an exercise is a word uttered by the user. Current state-of-the-art models add attention layers to autoregressive models or rely on self-attention networks. However, these models are built on publicly available datasets that lack useful information about the interactions users have with exercises. In this work, various techniques are introduced that allow for the incorporation of additional information made available in a dataset provided by Astrid Education. They consist of encoding a time dimension, modeling the skill needed for each exercise explicitly, and adjusting the length of the interaction sequence. Introducing new information to the Knowledge Tracing framework allows Astrid to craft a more personalized experience for its users; thus fulfilling the purpose and goal of the thesis. Additionally, we perform experiments to understand what aspects influence the models. Results show that modeling the skills needed to solve an exercise using an encoding strategy and reducing the length of the interaction sequence lead to improvements in terms of both accuracy and AUC. The time-encoding did not lead to better results, further experimentation is needed to include the time dimension successfully. / Mänsklig kunskap är ett försök att förutsäga användarnas framtida prestanda på lärandeplattformar baserat på historiska data, genom att modellera deras kunskaps tillstånd. I denna uppgift är målet en binär variabel som representerar överensstämmelsen av övningen. Nuvarande state-of-the-art-modeller lägger till uppmärksamhetslager på autoregressiva modeller eller förlitar sig på self-attention-nätverk. Dessa modeller bygger dock på offentligt tillgängliga databaser som saknar användbar information om de interaktioner som användare har med övningar. I detta arbete introduceras olika tekniker som gör det möjligt att inkludera ytterligare information som görs tillgänglig i en databas som tillhandahålls av Astrid Education AB. De består av att koda en tidsdimension, modellera färdigheten som krävs för varje övning explicit och justera interaktionssekvenslängden. Genom att introducera ny information i ramverket för kunskapstracing tillåter Astrid att skapa en mer personlig upplevelse för sina användare; därmed uppfyller syftet och målet med denna avhandling. Dessutom genomför vi experiment för att förstå vilka aspekter som påverkar modellerna. Resultaten visar att modellering av färdigheter med en kodningsstrategi och reducering av interaktionssekvenslängden leder till förbättringar både vad gäller noggrannhet och AUC. Tidskodningen ledde inte till bättre resultat, ytterligare experimentering krävs för att inkludera tidsdimensionen på ett framgångsrikt sätt.

Ein fragment-basierter Ansatz zur Berechnung von vertikalen Anregungsenergien in periodischen Systemen wurde entwickelt. Das Ziel war eine wellenfunktions-basierte Hierarchie von lokalen post-Hartree-Fock Methoden, welche über das weitverbreitete Ein-Elektronen Bild der Bandlücke hinausgehen und eine Möglichkeit zur systematischen Verbesserung der Ergebnisse liefern. Darüber hinaus sollte durch die Verwendung von lokalen Orbitalen eine nahtlose Einbettung des Fragments ermöglicht und eine effektive Methode für die Untersuchung von Defekten in periodischen Systemen geschaffen werden. Als erster Schritt wird das fragment-basierte Configuration Interaction Singles (CIS) Model vorgestellt. Im Anschluss erfolgt der Wechsel zum fragment-basierten lokalen algebraic-diagrammatic construction Modells zweiter Ordnung (DF-LADC(2)). Beide Methoden wurden für ein neutrales Farbzentrum in Magnesiumoxid (MgO) getestet. Dabei wurden Fragmente mit bis zu 57 Atomen verwendet. Eine Konvergenz mit der Fragmentgröße, der Größe der Superzellen und des K-mesh konnte erreicht werden. Dennoch wurde eine erste Anregungsenergie von 5.9 eV erhalten, was 0.9 eV über dem veröffentlichten experimentellen Wert liegt. Mit hoher Wahrscheinlichkeit rührt die Abweichung vom Basissatzvollständigkeitsfehler her. ”Finite-Cluster”-Berechnungen bestätigen entsprechende Basissatzfehler. Interessanterweise stimmt die erste Anregungsenergie für ein Oberflächenfarbzentrum in MgO mit einigen experimentellen Werten überein. Allerdings decken die experimentellen Werte für diese Systeme einen weiten Bereich ab (1.15 - 4.2 eV). / An embedded-fragment approach for calculation of vertical excitation energies in periodic systems has been developed. The aim is a wave-function-based hierarchy of local post-Hartree-Fock models, which goes beyond the very common one-electron picture of the band gap and offers a way for systematic improvability of the results. The use of local occupied and virtual orbitals allows for a seamless embedding model for the fragment and becomes especially effective in studying defects in solids. As a first step in the hierarchy an embedded-fragment Configuration Interaction Singles (CIS) model is presented. The second step is an embedded-fragment local algebraic diagrammatic construction scheme of second order (DF-LADC(2)). Both methods are tested for an neutral color center in bulk and surface magnesium oxide (MgO). Different fragments with up to 57 atoms were studied. A convergence with fragment size, super-cell size and k-mesh has been achieved. However a first excitation energy of 5.9 eV is obtained for the bulk MgO, which is 0.9 eV above the reported experimental value. The deviation most likely originates from the basis set incompleteness error, which, according to finite cluster studies, can be sizable. Interestingly for a surface color center in MgO the observed first excitation energy of 4.1 eV agrees with some of the experimental values (4.2 eV). However for the surface color centers in MgO the scatter of the experimental results is very large (1.15 eV - 4.2 eV).