Bachelor's and Master's Theses

Master's Theses
Bachelor's Theses

Master's Theses

Years: 2020 | 2019 | 2018 | 2017 | 2016 | 2015 | 2014 | 2013 | 2012 | 2011 | 2010

back to the top of all theses

2020

Engy Nasr
Evaluation of Automatic Ontology Matching for Materials Sciences and Engineering Presentation

Abstract A challenge of managing various amounts and types of data has raised due to the exponential increase in information and communication technologies. Creating strategies for handling those exponentially increased amounts of data using logic, semantics and computers, allowing reasoning between various data entities, is still under progress. Ontologies present a promising solution as a high-level knowledge representation system with strong semantics. Accordingly, institutions develop and establish ontologies according to their needs, resulting in various ontologies created for a specific field by different actors. To enable interoperability between actors and systems, mapping between ontologies is crucial. One way to establish a mapping between different ontologies is ontology matching, where actual relations and alignments between entities of different ontologies are found. As Huschka and Dlugosch have stated, “Digitization is increasingly entering classical engineering disciplines. Especially in the field of materials science, pioneering innovations are characterized by modern methods of data processing”. [1] Many automatic ontology matching tools (matchers) have been introduced, evaluated and approved by the “Ontology Alignment Evaluation Initiative (OAEI)”, recently in the field of Bioinformatics and Biomedical domains. However, until now, there have not yet been evaluations performed for automatic ontology matching (evaluation workflows) for Materials Sciences. Consequently, there is no available benchmark for Materials Sciences ontologies to evaluate the already existing ontology matchers in terms of the Materials Sciences domain. Other domains’ benchmarks cannot be used as Materials Sciences benchmark due to the different concepts represented in different domains’ ontologies. Therefore, in this thesis, creating a Materials Sciences benchmark with test cases, controls and supporting ontologies, and performing evaluations of the existing ontology matchers are crucial for the application of automatic ontology matching in the Materials Sciences domain. The evaluation results have shown that the usage of “LogMap”, an ontology matching tool, is recommended for applications that demand high precision. “Agreement Maker Light (AML)”, another ontology matching tool, provides a background knowledge ontology matcher, which uses the supporting background knowledge ontologies and boosts the number of correct alignments found by the tool. Accordingly, a mature Materials Sciences background knowledge (semantics bridge) ontology is essential in getting more correct and complete alignments. The usage of the property matcher is currently not recommended until it is improved to include logically correct alignments. Finally, the fully automated ontology matching is not achieved since all alignments are only equivalences and no sub or super alignments are detected; accordingly, human interference is also needed because the results are not 100 % correct and complete.

2019

Ibrahim Alshibani
A Cryptocurrency Evaluation and Trading System Presentation

Abstract Accurately predicting asset prices in a financial market is a very difficult task. This difficulty arises from the large number of real-world factors that drive the price. Often these factors are hard to model or follow a random behaviour. This thesis studies the predictability of a financial market of a new type of asset, cryptocurrencies. We employ two types of approaches to this problem, the first one is based on Technical Analysis. We utilized an approach based on grid search and cross validation to find the best set of parameters for the trading strategies based on technical analysis. This approach was applied to 5 different cryptocurrencies and 7 different trading strategies. All candidate strategies that resulted from the cross-validated grid search method performed well on out-of-sample data, yielding positive returns. The second approach used to tackle the problem was based on computer learning. We fitted historical data for 5 different cryptocurrencies to a Recurrent Neural Network model that uses the Long Short Term Memory (LSTM) architecture. The model was able to achieve limited accuracy improvement over a random classifier by around 5% for 3 out of 5 currencies. Complementary to the first approach, we designed a trading system that enables the user to run trading simulations on historical data, and launch a trading bot to perform automated trading based on a selected trading strategy. By comparing the performance of the trading bot to that of the offline trading simulations, we found that our offline simulation is a realistic approximation to real-world live trading.
Nishat Fariha Rimi
Comparative Study of Forecasting Algorithms for Energy Data Presentation

Abstract Accurate forecasting data is an important requirement of energy management systems and subsequent decision-making processes to ensure proper balance between supply and demand. The energy industry commonly carries out planning and forecasting of energy consumption for three types of prediction intervals: short-term, medium-term and long-term. The accuracy of a forecast depends on different parameters. Influence of the forecast horizon and the dataset type is significant among them. Often PV generation and electrical load profiles are subject to forecasting. Furthermore, different forecasting methods yield different accuracy. This study aims to identify the most appropriate method for accurately forecasting energy data based on the desired prediction horizon and the type of predicted dataset. The analysed methods include three categories of approaches– statistical, machine learning and deep learning. Statistical approaches include: Autoregressive moving average (ARMA), Autoregressive integrated moving average (ARIMA), Exponential smoothing (ES) and Holt-Winters method (HW). Machine learning approaches are K-nearest neighbor (KNN) and Random forest (RF). From the deep learning approaches, Artificial neural network (ANN) and Recurrent neural network (RNN) have been focused. The forecasting quality for each method was measured using mean absolute error, mean absolute percentage error, root mean squared error, and the correlation coefficient R value. The results suggest that RF and KNN were the most appropriate forecasting algorithms for short-term (daily), medium-term (monthly) and long-term (3 monthly) forecasting horizon for both energy datasets. During the comparisons, these two methods provided higher accuracy and required minimum computational time to forecast among the compared methods. Additionally, ARIMA and ARMA methods performed better for very short-term (hourly) forecasting.
Sameed Hayat
De-Identification of free text Presentation

Abstract Sharing data in the form of text is important for a wide range of activities but it also raises a concern about privacy when sharing data that could be sensitive. Text-based patient medical records are a vital resource in medical research. Processing of a large amount of medical data can be done in order to derive meaningful statistical information from such data as well as for other research purposes. The use of such data usually imposes problems with privacy of patients’ personally identifiable information. Automated text de-identification is a solution for removing all the sensitive information from documents. However, this is a challenging task due to the unstructured form of textual data and the ambiguity of natural language. In this thesis, we developed two models that use semi-supervised approaches. These approaches use mix of labeled and unlabeled data to remove personal information from the data. First approach uses contextualized characterlevel word embedding trained on large corpus of unlabeled data. This model outperforms the state-of-the-art systems on i2b2 2014 de-identification challenge dataset without using hand-curated feature. This model yields an F1-score of 97.99%, with a recall 97.52% and a precision of 98.46%. Whereas, the second approach uses Cross-View Training (CVT) algorithm, which aims at improving the performance of the model by incorporating unlabeled data. Our results show that this approach can aid in increasing the performance of the model on the de-identification task. This model outperforms the state-of-the-art systems on i2b2 2014 de-identification challenge dataset without using hand-curated feature. Our best performing model yields an F1-score of 97.99%, with a recall 97.52% and a precision of 98.46%. We also showed with our experiments that as the amount of data decreases the performance of semi-supervised approaches grow larger over purely supervised learning approaches.
Muhammad Hamiz Ahmed
Meta Data Inference on Building Sensors Data Presentation

Abstract Modern buildings are equipped with complex heating, cooling and ventilation sys-tems. In the group "Building Performance Optimization" at Fraunhofer ISE, various methods are investigated for detecting faulty or suboptimal operation of such systems (e.g. simultaneous heating and cooling). These methods require data of a multitude of sensors for input (like temperature, pressure, current etc.). For this, a manual labelling of the sensor is required, which is excessively time consuming. The labelling convention called data point naming convention marks the origin and type of the sensor. Every sensor has recorded time series data as well as a small description text describing the nature of the sensor. In this thesis, we create a supervised machine learning system that utilizes the time series and description text data and automates the labelling of the data point name of the sensor. The proposed system is able to predict with an accuracy of 88% with 218 labels in the dataset, outperforming the baseline score of 76% which only used 81 labels.
Matthias Hertel
Neural Language Models for Spelling Correction Presentation

Abstract Spelling correction is the task of automatically recovering the intended text froma misspelled text. This enhances digital communication and enables Natural Lan-guage Processing and Information Retrieval systems to work with misspelled text.We propose NLMspell, a spelling corrector based on a neural language model.NLMspell achieves correction F-scores of 91.5 % on artificial misspellings and88.4 % on real misspellings. It outperforms our baselines methods based on tra-ditional language models, as well as our neural machine translation approach tospelling correction, and the commercial product of a large Internet company.
Theresa Klumpp
Neural Word Embeddings as Matrix Factorization Presentation

Abstract The problem of finding continuous word vectors is central and well studied in natural language processing (NLP). In this thesis, we consider two neural networks that yield lowdimensional word embeddings: skip-gram and skip-gram with negative sampling (SGNS),0 introduced by Mikolov et al. in [10] and [11]. Assuming the dimension of these word embeddings was large (at least as large as the size of the vocabulary), we show that a different method, namely the factorization of a word-context matrix using singular value decomposition (SVD), also maximizes the objective function of the neural network. Even though we cannot make this link for low-dimensional embeddings, we can still use SVD and show that this method performs even better in some linguistic tasks than the neural network that it stems from. This connection between the SGNS neural network and SVD was presented by Levy and Goldberg in [8]. We analyze the cosine similarity, commonly used in NLP to measure the similarity between word vectors, and we derive a formula that gives us a heuristic understanding of what `close' in Rd is. We compare the different methods for finding low-dimensional word vectors and evaluate them on word similarity and semantic and syntactic analogy tasks. Our data clearly shows that SVD prefers a low number of `negative samples', whereas the SGNS neural network generally performs better for a higher number. Furthermore, the neural network is evidently superior in the analogy tasks, while SVD gains the advantage on word similarity tasks, if the number of negative samples is low.
Omar Kassem
Predicting Personalities through Multimodal Signals Presentation

Abstract Automatic personality perception is a research area that has recently gained attention from the scientific community due to the wide range of fields that could benefit from personality predictions. The rise of social media platforms is providing access to huge amounts of labelled personality data. The dataset used for this research has been collected from the social media website Youtube. In this thesis, deep neural networks have been used to predict personality from one of three communication modalities: text, audio and images, or combinations thereof. The performance of the different trained models was used to compare the information embedded in each modality with respect to personality. This work’s analysis points to visual information has the most personality content.
Natalie Prange
Question Auto-Completion using a Typed LSTM Language Model Presentation

Abstract Query auto-completion (QAC) is the task of predicting a user’s query as they type. A QAC system presents completion predictions to the user to ease the process of entering a query. Most approaches to QAC heavily rely on query logs - large collections of queries asked by users in the past. These logs are often used to estimate the probability of a query based on how frequently it occurs in the logs. Major limitations of this approach are the inability to predict queries that have not been asked before as well as the fact that search engines with a small user base or recently deployed search engines usually do not have access to large enough and up-to-date query logs. We therefore explore the possibilities of QAC independent of query logs. For this work, we focus on questions as opposed to queries which are often just fragments of the question a user has in mind. We deploy a typed Long Short Term Memory (LSTM) language model trained on more than 11 million questions. In our language model, we replace concrete entities by abstract types in order to overcome the problem of data sparsity. When predicting a query completion, we insert entities for the types that the language model predicts by using an entity prominence score, co-occurrence between entities and word vector similarity. We evaluate our system over a hand-crafted ground truth of question prefixes and reasonable completions. Additionally, we evaluate our system over three question test sets. We compare several versions of our system. Apart from illustrating the importance of various system components, the results show that using co-occurrence to insert entities is superior to inserting entities purely based on an entity prominence score or word vector similarity.
Tobias Matysiak
Tabular Information Extraction Presentation

Abstract Searching for content in knowledge bases can involve some challenges, especially for inexperienced users. On the one hand, they need to know the underlying data structure (mostly represented by an ontology), on the other hand, they need to know how to query the knowledge base. This thesis introduces a web application called Knowledge Base Table Extractor (KBTE) that is able to generate SPARQL queries for Freebase and Wikidata back-ends to retrieve information in a tabular form. For this, the thesis provides a simple tabular description format for specifying table definitions like city | country | population as input. KBTE tries to find a table matching which maps each column keyword to a class or property of the knowledge base and relates the columns to each other. Unlike keyword search and question answering approaches, it is not focused on matching entities. The algorithm for table matching exploits the combined use of a search index and a column graph. The search index is used for the mapping part, the column graph is used to find relations between two columns. Furthermore, the thesis provides three datasets for evaluation. One is created from tables of Wikipedia, the other two contain hand-crafted table definitions. The evaluation compares the table matching algorithm used by KBTE with a simple baseline algorithm. The results can confirm the better performance of the former.

2018

Mostafa M. Mohamed
Automatic Correction of Misaligned Spaces and Typos Using Deep Learning Presentation

Abstract Large text corpora could get corrupted for a variety of reasons, such corruptions could be tokenization corruptions, like removing correct spaces between words, adding wrong spaces in-between words, splitting words across lines or garbling some characters in words. These mistakes could make it hard for systems, that process large text corpora, to identify the words within a text correctly, and as a result, lose a lot of information about the text. This thesis developed a model which utilizes characterbased language models, that are trained as recurrent neural networks via deep learning. The model automatically detects the tokenization mistakes in a given text and fixes them accordingly. The model can successfully classify, and hence fix, the tokenization errors with a mean F1-score that, depending on the model’s specifications, training settings, and evaluation settings, varies between to 81% to 96%. Furthermore, two non-learning dictionary-based approaches are presented, using a baseline greedy strategy and dynamic programming, in addition to an end-to-end deep learning approach and a baseline learning approach using 3-Gram Markov models. The models are trained and evaluated using two datasets: Simple-Wikipedia and Reuters-21578. The presented approaches are empirically evaluated to demonstrate the superior performance of the presented model. Additionally, it is experimented using different RNN architectures, RNN history length, model size, beam size in Beam-search, training data size, tokenization errors and some internal features.
Bhashitha Gamage
Automatic Generation of Frequency Maps for Public Transit Networks Presentation

Abstract This thesis addresses the problem of automatically generating the frequency map of a public transit network when given its GTFS [1] data feed. Normally, the drawing of a frequency graph is completely done manually and doing it automatically is extremely complicated. Our approach consists of a few major steps including extraction of the transit graph from the GTFS data, implementation of the frequency finding algorithm, extraction of the frequencies among interested nodes, creation of the frequency lines and finally the drawing of frequency lines and nodes in a convenient way to resemble a schematic map. The last step which is the drawing of a frequency map automatically was the most challenging step, and several approaches experimented until satisfactory results were achieved. We explain each of this steps in detail and discuss how the appeared challenges are solved and overcome in a scientific manner. We tested our approach against several examples GTFS Feeds, evaluated it concerning the running time and the frequency coverage and compared our results to the official, hand-drawn frequency graph published by the Swiss Federal Railways.
Sumitra Magdalin Corraya
Dehyphenation of Words and Guessing Ligatures Presentation

Abstract The accurate extraction of text from PDF (e.g. in order to be able to search in it) can prove to be a difficult task as on some occasions long words at the end of the line are split into two words joined with a hyphen. Moreover, PDF contains ligatures (multiple characters, which translate to one/single character in the PDF) that can be hard to search for as well. In this thesis we propose solutions to the aforementioned problems, i.e. deciding if the hyphen (-) in the words is necessary or not, and proposing a method for guessing ligatures by looking up in a large dictionary. In both cases, we try to provide a fast response of time and good accuracy. In PDF, long words can be split into two parts with a hyphen between them, when they do not fit in one line and as a result appear in different lines. The reason for the hyphen is to show that the words had a combined meaning or that there is a relationship between the words (also known as compound words). However, not all compound words need to be hyphenated which can prove to be problematic. This thesis proposes a procedure to decide when to dehyphenate the word. We decide upon the necessity of the hyphen by using the dictionary of words. Our approach provides efficiency and good accuracy, which we demonstrate with different experimental results. During the making of PDF files, some combination of character (ligature) translates to a single character (for example the ligatures: "ffi","ffl" are translated to some special characters). This can be problematic as when the text is extracted from the PDF, e.g. for searching, one wants to extract the individual characters within the word and not the special character. This issue is further aggravated by the fact that PDF has different fonts and encoding. We propose a method for guessing ligatures from such special characters. We do so, by trying different ligatures and searching the formed words in the dictionary. Finally, we also discuss what to do in case of an ambiguity when looking up the word.
Mohammad Mahadi Hasan
Efficient Database Model to Represent Numerical Research Data of Material Flow Analysis Presentation

Abstract The research group of Industrial Ecology Freiburg (IEF) produces research results consisting material stock and flow data between industrial sectors and regions. Most of these data are stored in .mat or .csv files on a local machine which makes data accessibility difficult to other users. Usually these datasets are big, and it is difficult to re-generate a specific part (based on specific region or industrial sector) on request from another interested user. An efficient data storing and retrieving mechanism could provide a solution to this problem. While, Relational Databases (RDB) have been meeting this criterion for decades, Triple Store is a new kind of database which has grown in popularity in recent years due to its applications towards Semantic Web Technology which assures that data to be shared and reused. In this thesis, we provide a study on both relational databases and triple stores. We start with constructing a relational database from our dataset and design a web interface so that users can retrieve data by their own. To examine the offerings that triple stores provide us, we design a triple store to store the same dataset. In relational databases where data is stored in relational tables, triple stores store data as semantic triples using the Resource Description Framework (RDF); a semantic web standard for publishing and sharing data on the Web. Therefore, we transform our entire dataset from the relational database to RDF and load into the triple store. Finally, we do the performance evaluation on both database models in terms of query processing time running equivalent test queries. This evaluation also includes the additional offerings triple stores and relational databases provide which summarize the argument to choose more suitable database model for industrial ecology research data.
Philip Schledermann
Knowledgebase construction of genetic variants in literature Presentation

Abstract In Publikationen werden oftmals synonyme Begriffe für eine genetische Variation verwendet. Für die verbesserte Suche nach Veröffentlichungen über genetische Variationen in wissenschaftlichen Publikationsdatenbanken wie PubMed und PubMedCentral, sollen die unterschiedlich verwendeten Begriffe auf die präferierte Bezeichnung der jeweiligen genetischen Variation zurückgeführt werden. Mit ClinVar existiert eine manuell kurierte Datenbank, in der die Begriffe welche in Standardnomenklatur geschrieben werden enthalten sind. Um auch Begriffsvariationen zusammenzuführen, welche nicht der Norm entsprechen sollen diese aus den Veröffentlichungen extrahiert werden. Der Text wird mittels Named Entity Recognition und anderen Algorithmen der Sprachverarbeitung vereinfacht. In einem "word embedding"Modell werden aus dem Text Begriffe und ihre Kontexte extrahiert und miteinander verglichen. Gleiche Kontexte für unterschiedliche Begriffe weisen darauf hin, dass es sich bei den Begriffen um Synonyme handeln könnte. Dieses Modell wird auf unterschiedliche Schreibweisen von genetischen Variationen angewandt. Das Modell wird gegen ClinVar evaluiert. Hierbei zeigt sich, dass der überwiegende Teil der normierten Standardbegriffe teils verschwindend gering in der verwendeten wissenschaftlichen Literatur enthalten ist. Zudem zeigt sich, dass das Modell nicht ohne zusätzliche Filterung der Ergebnisse verwendet werden kann.
Daniel Tischner
Multi-Modal Route Planning in Road and Transit Networks Presentation

Abstract Wir präsentieren Algorithmen für multi-modale Routenplanung in Straßennetzwerken und Netzwerken des öffentlichen Personennahverkehrs (ÖPNV), so, wie in kombinierten Netzwerken. Dazu stellen wir das Nächste-Nachbar- und das Kürzester-Pfad-Problem vor und schlagen Lösungen basierend auf Cover Trees,ALT und CSA vor. Des Weiteren erläutern wir die Theorie hinter den Algorithmen, geben eine kurze Übersicht über andere Techniken, zeigen Versuchsergebnisse auf und vergleichen die Techniken untereinander.

2017

Johannes Güttler
Semantische Personensuche auf Hochschulwebsites Presentation

Abstract Die Arbeit zeigt wie Personendaten aus einem Webcrawl extrahiert und als Grund-lage für eine Suchmaschine aufbereitet werden können. Es wird vorgestellt, wie sich die Texte deutscher Hochschulwebsites aus einem vorhandenen Webcrawl extrahie-ren lassen. Dazu wird die ungeordnete Menge der Daten mehrerer CommonCrawl-Webcrawls verarbeitet. Mittels Named Entity Recognition werden Personennamen extrahiert und in eine Ontologie überführt. Diese wird mit zusätzlichen Informatio-nen wie zum Beispiel der persönlichen Homepages angereichert. Die Ontologie und extrahierten Websitetexte werden für die Suchmaschine Brocco-li aufbereitet. Sie lassen sich beschränkt auf geografische Gebiete und zusätzlicher Volltextsuche in den Websitetexten durchsuchen. Die Qualität der Ergebnisse va-riiert stark. Sie ist nicht nur von der Art der Suchanfrage abhängig, sondern auch stark von der Darstellung von Personen auf der entsprechenden Hochschulwebsite.

2016

Tobias Sommer
Movie Search - Building semantic search queries with suggestions Presentation

Abstract MovieSearch helps with building semantic queries for tasks like ”find movies with Arnold Schwarzenegger where he fights with a sword”. The suggestions by MovieSearch aim to enable the usage of semantic queries. Usability of semantic queries is the main contri-bution of MovieSearch. The tasks of our user study could be successfully answered in 94% of the cases.MovieSearch provides a user-friendly and effective semantic search system for non-experts. Semantic search shall become available for users who have no knowledge about database languages like SPARQL. The interactive query building delivers trace-able results in contrast to natural-language-based approaches with their hidden query building. We build queries by stepwise adding conditions to specify what we are looking for. The conditions consist of facts and plot. MovieSearch implements an approach with those two input categories. Our example task looks for a movie with actor Arnold Schwarzenegger as a fact, and the plot description fights with a sword. MovieSearch enriches the fact options by 3-ary relations. This allows to connect certain fact parts, for example to look for a movie where the actor Elijah Wood played the character Frodo. The results for the queries will be answered by the SPARQL Server provided by [? ].

2015

Max Lotstein
Mitigating Feature Exclusion to Improve Hypernymy Recognition Presentation

Abstract Hypernymy, which is the sort of relationship exemplified in the pair (dog, animal)when both take their conventional senses, lies at the heart of many applications in artificial intelligence and natural language processing. In this work, I investigate automatic methods of identifying such sense-pairs. Many existing models for this task implement feature inclusion, which is the intuition that senses like dog are semantically narrower than senses like animal in that the properties one can apply to the former can always conceivably be applied to the latter, but not the inverse. Stateof-the-art performance of these models has been limited by the Feature Exclusion Problem, which is that in the sparse feature vectors representing a sense like dog, in which a non-zero feature is interpreted as an applicable one, there are many nonzero features that should also be non-zero in the representation of animal but aren’t. This work begins by exploring in greater detail the nature of this problem before exploring a post-processing technique designed to mitigate it.
Tobias Faaß
Ontology-Based Route Queries with Time Windows Presentation

Abstract Most of the time we use route planning to get from A to B. However, we can also incorporate stopovers into our route so that we may get things done along the way. A route from A to B via a gas station, for example, is of no use if the gas station is closed upon arrival. As a consequence, the opening hours and the duration of stay become necessary considerations. In this thesis we define an ontology to be a hierarchical structure of groups to serve us as stopovers. We fill this ontology with POI extracted from the open source project OpenStreetMap. Since the extracted POI rarely have attached opening hours, these opening hours must be calculated based on existing ones or defined by hand. To calculate the route along which a sequence of POI groups are visited, we implement known approaches of sequenced route planning and extended them to match the time window requirements. Different test queries were executed on the system. Within a test area of about 25 km, query times under a half second were measured. During these tests, it was discovered that the route starting time influences the running time, which is due to the fact that during the night most POI are closed. The implemented system covering all of Germany can be found at http://panarea.informatik.uni-freiburg.de/osm-search/.
Fabian Schillinger
Strukturierte Extraktion von Text aus PDF Presentation

Abstract Wissenschaftliche Artikel werden, vor allem in der Informatik, oft online im PDFFormat angeboten. Ein großer Vorteil ist die Plattformunabhängigkeit. Zeichenkodierungen und Schriftarten sind genauso wie Grafiken, Tabellen oder Algorithmen eingebunden. Für einige Anwendungen, wie z. B. die semantische Suche, wird jedoch nur der Informationen enthaltende Fließtext benötigt. Um den Text eines PDFDokuments zu erhalten, bieten viele Anwendungen die Möglichkeit diesen zu extrahieren. Diese Anwendungen haben aber Schwierigkeiten mit Grafiken oder Tabellen, denn diese beinhalten auch Text, der mit extrahiert wird. Weitere Schwierigkeiten für diese Systeme sind z. B. Fußnoten oder mehrspaltige Layouts. Fußnoten können einzelne Sätze, die auf zwei Seiten oder Spalten stehen, unterbrechen. Bei mehrspaltigen Layouts kommt es oft vor, dass die Aufteilung in Spalten ignoriert werden. Um nur den Informationen enthaltenden Fließtext aus PDF-Dokumenten zu extrahieren sind noch weitere Schwierigkeiten zu überwinden. Das hier vorgestellte System schafft es, die meisten dieser Schwierigkeiten zu überwinden und aus wissenschaftlichen Artikeln den Fließtext strukturiert zu extrahieren. Dabei wird das zu untersuchende Dokument in verschiedene Blöcke aufgeteilt. Diese Blöcke werden dann klassifiziert, indem z. B. nach Schlüsselworten wie “Abstract” gesucht wird. Nach und nach werden nicht benötigte Blöcke ignoriert und am Ende nur die benötigten Blöcke ausgegeben. Dabei wird sowohl eine hohe Präzision von mehr als 0,98, als auch eine hoher Sensitivität von mehr als 0,96 erreicht. Der kombinierte F1-Wert liegt bei etwa 0,97. Auf Grund der geringen Komplexität ist auch der Zeitaufwand für die strukturierte Textextraktion gering.

2014

Niklas Meinzer
Dynamic Emergency Ambulance Fleet Allocation and Management Presentation

Abstract Most countries have implemented some form of Emergency Medical Services (EMS)in order to help people with urgent medical needs. Typically a number of ambulances serve a specific geographic region by responding to emergency calls, treating patients and transporting them to a hospital. Since the number of ambulances is limited and emergency calls need to be responded to quickly by nature, EMSs have to be thoroughly managed and coordinated, which is usually done by human operators in special call centers. In this thesis we model that task and present and compare different strategies which could be employed by an automatic ambulance fleet management system. We show that continuous optimization of ambulance distribution over the region and dynamic reassignment of ambulances to incoming requests can benefit both the patients and, economically, the provider of the EMS.
Ragavan Natarajan
Entity Disambiguation using Freebase and Wikipedia Presentation

Abstract This thesis addresses the problem of entity disambiguation, which involves identifying important phrases in a given text and linking them to the appropriate entities they refer to. For this work, information extracted from both Freebase and Wikipedia served as the knowledge base. A fully functional entity disambiguation tool is made available online and the challenges involved in each stages of the development are addressed in this paper. It explains how the phrases in a text are assigned importance measure, both before and after the disambiguation process, based on several studies available in the literature and experimental analysis conducted as a part of this work. Additionally it explains the implementation of the collective-entity-linking algorithm by Han et al.[1] for entity disambiguation. Several highly reusable code have been developed, whose usability extend well beyond the work described here. Stages involved in the development, from parsing the database dump to storing them in a high-speed, memory efficient key-value store are addressed. By means of D3js a JavaScript based vector graphics library for bringing data to life, visualization of the ambiguity tree is provided, which helps the user easily comprehend the results.
Patrick Brosi
Real-Time Movement Visualization of Public Transit Data Presentation

Abstract One of the primary challenges in visualizing movement in public transportation networks is handling the amount of data. This becomes particularly difficult when the visualization should be available in real-time and for arbitrary spatial parts of the dataset, for example to provide an interactive live map. The main task is then to reduce and crop the set of trajectories to the parts currently relevant for the visualization. In this thesis, we present an approach that combines static schedule data and real-time delay information into vehicle trajectories that are treated as piecewise linear functions from the time domain to the projected map-plane, allowing for fast interpolation. We introduce a highly efficient server that accepts temporal and spatial boundaries as an input and returns trajectory parts within these limits. We discuss the implementation details, show that our approach scales well and demonstrate that it is able to handle public transit datasets of entire countries. As a client, we introduce a thin vector-layer for map services that can display thousands of (time-lapsed) vehicle-movements at the same time. This thesis also briefly outlines an approach to extract vehicle trajectories from geospatial datasets.
Eugen Sawin
Semantic Search with Keyword Queries Presentation

Abstract We present a semantic search concept, which effectively combines the simplicity of keywordbased search with the sophistication of semantic results. Our bootstrapping process is designed to utilize the efficiency and precision of full-text search to provide reliable intermediate results during the retrieval phase. In the second phase, we perform a deep semantic search, based on the previous results for their refinement. The introduced methods include lexical query analysis, ranking and answer selection algorithms and a variety of filtering solutions. We argue that a simple query interface based on keywords is essential to unlock the potential of semantic search technologies and make them accessible for a greater audience. Finally, we provide Pythia – an open source implementation of the two-phase approach – to support further practical research on this topic.

2013

Cynthia Jimenez Cardenas
Efficient Multi-modal Route Planning with Transfer Patterns Presentation

Abstract In these days, there is a big interest in route planning systems with different types of transportation. We study a way to efficiently compute optimal paths with real data in a multi-modal scenario considering walking, transit and car. Therefore, we implement Transfer Patterns, which is a state-of-the-art route planning approach. This allows to obtain shortest paths queries within milliseconds. When using a Pareto-cost model various optimal paths are provided for the user. However, the high number of optimal solutions also includes a lot of unreasonable routes, although they are Pareto-optimal. To address this problem, we use a filtering procedure called Types aNd Thresholds (TNT) [10], which provides a both small and diverse set of reasonable optimal paths decreasing the number of transfer patterns and hence resulting in faster query times. To our knowledge this is the first work which realizes the combination of these two approaches (Transfer Patterns with TNT). We present an evaluation on query times of selected optimal paths, which shows different and reasonable route options with an average query time of 14 milliseconds for the Freiburg network.
Mirko Brodesser
Multi-Modal Route Planning Presentation

Abstract We examine the computation of optimal paths, which consist of using public transportation, walking and taking a car. A challenge in itself is to determine concise and diverse sets of paths. We consider metropolises like New York, where a fast computation of the paths is difficult. We exemplify that multiple optimality criteria are necessary to obtain diverse sets of paths. This extends the set of optimal paths severely, whereas many paths are similar. To determine concise sets, we study different methods of filtering. We propose a filtering procedure, Types aNd Thresholds (TNT) , which leads to the desired sets. To reduce the high computation times, we introduce several optimality-preserving and heuristic ideas. We experimentally evaluate the found paths with respect to quality and computation time. The experiments show the claimed quality of TNT and that the running time, while accepting a fraction of suboptimal solutions, is in the magnitude of few seconds. We complete the paper by giving an outline of possible improvements.
Jonas Sternisko
On Compact Representation and Robustness of Transfer Patterns in Public Transportation Routing Presentation

Abstract Transfer pattern routing is a state-of-the-art routing algorithm for public transportation. It allows to answer multi-criteria shortest path queries within a few milliseconds. The algorithm is based on an expensive precomputation of shortest paths between stations. This thesis examines two aspects of transfer pattern routing. The first objective is to find a compact representation of the transfer patterns. We detect redundancy in the transfer patterns and present novel ways to store the information within less memory. The second objective is to analyze the robustness of the transfer patterns towards delay and to answer the question whether the patterns still allow for optimal routing, if the underlying network changes. We address the second question by introducing a framework to evaluate the robustness in networks with different delay scenarios and we present experimental results indicating that transfer patterns are quite robust.

2012

Ilinca Tudose
Automatic Population of a Pharmaceutical Company Ontology Presentation

Abstract We have implemented and evaluated a method to populate a company ontology, focusing on hierarchical relations such as acquisitions or subsidiaries. Our method searches for information about user-specified companies on the Internet using a search engine API (Google Custom Search API). From the resulted snippets we identify companies using machine learning and extract relations between them using a set of manually defined semantic patterns. We developed filtering methods both for companies and unlikely relations and from the set of company and relation instances we build this way, we construct an ontology addressing identity matching and consistency problems in a company-specific manner. We achieved a precision of 77 to 93 percent, depending on the evaluated relations.
Dirk Kienle
Efficient Multi-Modal Route Planning Presentation

Abstract We present our system for computing shortest paths from A to B where we combine two types of networks: The road network and the public transportation network. The result is a multi-modal network where we are able to state a source and target address together with a date and a departure time and the system returns optimal paths that show us what roads to use and which vehicles to take. Modeling the timetable information concerning the public transportation network, we use the time-expanded and the time-dependent approach. The main goal of this thesis is to analyze both approaches concerning the computation of the shortest paths and to evaluate the performance of both using bi-criteria optimization. Therefore, in both approaches we do not only minimize the travel time but also the number of transfers. Thus, we get several optimal solutions in order to get from A to B. For example, consider two optimal and incomparable paths where for the first we need 30 minutes and 2 transfer and for the second 45 minutes and only 1 transfer. As it depends on the customer which of the paths is preferred, we present both as optimal solutions. Comparing the efficiency of both approaches, we also minimize in combination with the number of transfers walking between and to stations. It turns out that the time- dependent approach is about four times faster in average when we only use travel time and the number of transfers as criteria costs. But with the additional option of minimizing walking the difference becomes smaller.
Manuel Braun
Multi-Modal Route Planning with Transfer Patterns Presentation

Abstract We examine a way to extend routing using transfer patterns – a state of the art route planning approach for fast routing in public transportation networks – to a multi-modal scenario that allows using public transport, cars, and walking. We specifically examine how to precompute transfer patterns for multi-criteria, multi-modal route planning. When done naively with a Pareto cost model, this leads to a large number of undesirable route variations that render precomputation computationally infeasible. We identify rea- sons why these variations appear and present ways to reduce the number of variations with appropriate graph models and by applying limits during search. Our results indicate that precomputing multi-modal transfer patterns on large datasets is feasible with such a restricted model.

2011

Florian Bäurle
A User Interface for Semantic Full Text Search Presentation

Abstract We present a powerful and comfortable interactive web user interface for semantic full-text search. It combines and extends established components of other search user interfaces - namely keyword search, facets, proposals and breadcrumbs - in a new way. The result is a reasonably easy to use semantic search application that assists its users in an incremental creation of semantic queries, without requiring them to have knowledge about any special query language or the underlying ontology. The user interface provides only a single input field as it is also common for current keyword search applications like Google . When something is typed, it automatically shows different proposals for words, relations, entities, or semantic classes that are used to build the search query. When any of the proposals is selected, it is added to the query which is displayed as a tree in an advanced breadcrumbs panel. With the help of the breadcrumbs panel, the query can easily be extended or changed by adding new proposals or replacing or deleting already existing parts. The provided proposals are context sensitive with respect to the current query to support users in the incremental creation of meaningful queries. The hits for the current query are always automatically displayed together with evidence why they suit to the query. In this work we address the design decisions that were made during the implementation of the interface application and explain its basic architecture. We also show what queries are supported by the user interface and how it is used to create them.
Claudius Korzen
Icecite: Ein System zur Verwaltung von Wissenschaftlichen Publikationen mit Automatischer Metadaten-Extraktion Presentation

Abstract Wir präsentieren in dieser Masterarbeit IceCite – ein System, mit dem wissenschaftliche Publikationen verwaltet und verwandte Publikationen gefunden werden können. Das System bestimmt die Metadaten und bibliografischen Daten (Literatur-Referenzen) von Publikationen automatisch, indem es Titel und Referenzen aus entsprechenden PDF-Dateien extrahiert und Einträgen aus den Literaturdatenbanken DBLP und Medline zuordnet. Wir erhalten damit vollständige und korrekte Metadaten, die sowohl die Publikationen als auch ihre Referenzen eindeutig identifizieren. Unter anderem weil wir damit in der Lage sind, Verknüpfungen zwischen Publikationen herzustellen, kann das System alle notwendigen Schritte einer Literaturrecherche vereinfachen. Die Schwierigkeit der Titel- und Referenzen-Extraktion aus wissenschaftlichen Publikationen liegt in der großen Variabilität in Position und Struktur der zu extrahierenden Elemente. Mögliche Fehler in den extrahierten Zeichenketten, die z.B. auf Schreib- oder Extraktionsfehler zurückzuführen sind, machen zudem eine fehlertolerante Zuordnung zu einem Literaturdatenbank-Eintrag notwendig. In ausführlichen Experimenten an 700 Publikationen aus DBLP und 500 Publikationen aus Medline haben wir unter anderem die Korrektheit der Ergebnisse unserer Algorithmen zur Extraktion und Zuordnung von Titeln und Referenzen evaluiert. Wir erreichen Ergebnisse von bis zu 98.8% korrekt extrahierter Titel und von bis zu 91.1% korrekt extrahierter Referenzen. Die Zuordnung zu repräsentierenden Einträgen aus DBLP und Medline gelingt uns für bis zu 99.9% Titel und für bis zu 94.8% Referenzen.

2010

Elmar Haussmann
Contextual Sentence Decomposition with Applications to Semantic Full-Text Search Presentation

Abstract In this thesis, we introduce and study contextual sentence decomposition , which, intuitively, decomposes a given sentence into parts that semantically “belong together”. For example, a valid decomposition of the sentence “ Usable parts of rhubarb include the edible stalks and the medicinally used roots, however its leaves are toxic” are the sub-sentences “ Usable parts of rhubarb include the edible stalks”, “ Usable parts of rhubarb include the edible stalks” and “however its leaves are toxic ”. Our motivation for this problem comes from semantic full-text search . For a query plant edible leaves, semantic full-text search returns passages where instances of a plant, such as “ rhubarb ” (and not the word “plant ”), are mentioned along with the words “ edible” and “leaves ”. One of the results this query might erroneously return is the original sentence above. With contextual sentence decomposition we avoid this false-positive, while at the same time maintaining the true factual contents of the original sentence. We propose two approaches for our problem, one based on a set of rules and one using machine learning. On a manually assembled ground truth, we achieve an F-measure of about 65 percent for the former and of 40 percent for the latter. For the semantic full-text search based on these approaches, evaluated on the English Wikipedia (27 GB of raw text), we achieve improvements nearly doubling the F-measure for some queries.
Björn Buchhold
SUSI: Wikipedia Search Using Semantic Index Annotations Presentation

Abstract We present Susi , a system for efficient semantic search on the English Wikipedia. Susi combines full-text and ontology search. For example, for the query penicillin scientist , Susi recognizes that scientist is a type of person, and returns a list of names of scientists that are mentioned along with the word penicillin . We argue that neither full-text search alone nor ontology-search alone is able to answer these kinds of queries satisfactorily. Along with the list of entities matching the query (the name of the scientists in the example), Susi also provides excerpts from the text as evidence. The data structure behind Susi is an index for the CompleteSearch search engine. This index is enriched by constructs derived from facts from the Yago ontology. The challenge was to do this in a way that keeps the index small and enables fast query processing times. We present an annotation style, specifically designed to eliminate index-blowup associated with adding semantic information. In our experiments on the complete English Wikipedia (26GB XML dump), Susi achieved average query times of around 200 milliseconds with an index blowup of only 42% compared to ordinary full-text search. We also examine result quality by comparing the contents of hand-compiled Wikipedia lists like " List of drug-related deaths " against the output of Susi for corresponding semantic queries ( drug death person ). We come up with a simple typification of the kinds of errors that can occur. One of our findings is that the vast majority of false-positives is due to false omissions on the side of the Wikipedia lists, while the vast majority of false-negatives is due to omissions in the Yago ontology.

Bachelor's Theses

Years: 2020 | 2019 | 2018 | 2017 | 2016 | 2015 | 2014 | 2013 | 2012 | 2011 | 2010

back to the top of all theses

2020

Florian Kramer
Effcient Property Path Evaluation within the QLever Query Engine Presentation

Abstract This work is an implementation and evaluation of the property path feature from the SPARQL query language for the QLever query engine. This allows for searching for pairs of entities that are connected by a given path in a knowledge base. An example of such a query is: SELECT ? s c i e n t i s t ? c l a s s WHERE { ? s c i e n t i s t <ht tp : / / example / i s a>/<ht tp : / / example / i s a> ? c l a s s } This work also contains a comparison against Blazegraph in the form of an evaluation on a set of 39 property paths. On average the implementation presented here was about twice as fast as Blazegraph on the evaluation queries.

2019

Tanyu Tanev
Accurate Word Extraction from Documents with Complex Layouts Presentation

Abstract PDF documents are commonly used to exchange and store information. Their compactand self-contained nature has kept them relevant for a long time. It also, however,leads to problems when trying to automate operations on them. An example of this isthe automatic extraction of textual content - a problem, which has not been entirelysolved to this day. Textual content within the documents is only stored at a characterlevel, which means that words and text lines have to be rebuilt from the groundup. There exist rule-based algorithms, which try to solve the problem by takingadvantage of the spacing within the documents. Using them on documents with astandard layout (e.g. scientific publications), which feature rectangular columns andfigures has achieved satisfactory results.It is, however, more challenging for documents, which have a complex layout. Somemagazine and news articles, for example, feature circular pull quotes in-between textcolumns, which are used to emphasize a certain point. This, in turn, makes it harderto deploy the rule-based algorithms, because the spacing in the documents becomesirregular.In the following thesis, this problem is tackled with the help of a deep learningapproach. The approach looks at the pages of a PDF document as a collection ofsequences, which are in the form of text lines. These sequences are then processed bya deep learning model and each character from them is grouped into its respectiveword. The usage of not only the distances between the characters, but also their valueand information about their font, as input features, enables the model to more easilyidentify complex elements (e.g. pull quotes) and accurately extract their textualcontents.
Nishat Fariha Rimi
Comparative Study of Forecasting Algorithms for Energy Data Presentation

Abstract Accurate forecasting data is an important requirement of energy management systems and subsequent decision-making processes to ensure proper balance between supply and demand. The energy industry commonly carries out planning and forecasting of energy consumption for three types of prediction intervals: short-term, medium-term and long-term. The accuracy of a forecast depends on different parameters. Influence of the forecast horizon and the dataset type is significant among them. Often PV generation and electrical load profiles are subject to forecasting. Furthermore, different forecasting methods yield different accuracy. This study aims to identify the most appropriate method for accurately forecasting energy data based on the desired prediction horizon and the type of predicted dataset. The analysed methods include three categories of approaches– statistical, machine learning and deep learning. Statistical approaches include: Autoregressive moving average (ARMA), Autoregressive integrated moving average (ARIMA), Exponential smoothing (ES) and Holt-Winters method (HW). Machine learning approaches are K-nearest neighbor (KNN) and Random forest (RF). From the deep learning approaches, Artificial neural network (ANN) and Recurrent neural network (RNN) have been focused. The forecasting quality for each method was measured using mean absolute error, mean absolute percentage error, root mean squared error, and the correlation coefficient R value. The results suggest that RF and KNN were the most appropriate forecasting algorithms for short-term (daily), medium-term (monthly) and long-term (3 monthly) forecasting horizon for both energy datasets. During the comparisons, these two methods provided higher accuracy and required minimum computational time to forecast among the compared methods. Additionally, ARIMA and ARMA methods performed better for very short-term (hourly) forecasting.
Anushe Glushik
Context Tracking for Question Answering with Aqqu Presentation

Abstract The goal of this work is to implement a context tracking functionality in the Aqqu question answering system and to study the influence of context tracking on the overall performance of Aqqu. A question answering system with context tracking functionality takes the context into account. To find the correct answer, the system not only processes the current question, but also the history of questions asked before. To implement context tracking for Aqqu, we developped a web user interface (UI) in the form of a chatbot. Additionally we added to it a data augmentation functionality. We call the Aqqu system with a context tracking functionality conversational Aqqu. We evaluated the conversational version of Aqqu against a newly created conversational version of the original WebQSP questions dataset. For this we transformed and reordered the original one-off questions into conversations about topic entities shared by the original questions. From the evaluation results it was apparent that the conversational question answering is slightly less accurate, when compared to a single-question answering. Yet taking into account, that it is a far more complicated task, the conversational system still showed a very good performance. Moreover context tracking brings more convenience into the question answering process.
Patrick Bumüller
Finding Names on University Web Pages Presentation

Abstract An der Universität Freiburg arbeiten 6.736 Personen, von denen viele eine eigene Webseite haben [1]. Die gesamte Anzahl an Webseiten der Universität übersteigt 300.000 Seiten (5.1.4). Beginnend bei der Startwebseite einer Universität einen Mitarbeiter zu finden ist umständlich. Ohne Vorwissen über die Struktur der Webseiten werden viele Klicks benötigt. In dieser Arbeit wird ein System vorgestellt, das für Bildungseinrichtungen die relevanten Webseiten für Mitarbeiter und andere Personen findet und bewertet. Es implementiert ein automatisches Programm, welches Hyperlinks in Webseiten folgen und Namen im sichtbaren Webseitentext erkennen kann. Es konnten in Stichproben durchschnittlich über 90 % der Mitarbeiterwebseiten gefunden werden (5.1.4).
Mari Sverresdatter Hernaes
Improved Dehyphenation of Line Breaks for PDF Text Extraction Presentation

Abstract Words in layout-based documents can contain hyphens that divide the word into two parts across two lines. PDF documents only store information about individual characters, which makes it difficult to extract text correctly. Words which are hyphenated at the end of a line are especially problematic because in English there are some words where the hyphen should be kept, while others need to be merged. For example, “high-quality” can be a compound word. If this word splits on the hyphen across two lines, then the hyphen should be retained in the extracted text. The correct dehyphenation of line breaks requires the recognition of either words or sequences of characters. In this thesis, vocabulary-based baseline algorithms, logistic regression on the word level and a bi-LSTM Language Model on the character level are used to solve this problem. On the ClueWeb12 Extract data set, the vocabulary-based algorithm achieved a balanced accuracy (bACC) of 66.87%, the logistic regression 92.38% and the bi-LSTM Language Model 90.14%. Our investigations showed a trade-off effect between recognising words which naturally contain hyphens and predicting words without hyphens correctly.
Leo Zeches
Merging of Overlapping GTFS Feeds Presentation

Abstract The General Transit Feed Specification, GTFS for short, is a commonly used format for public transportation schedules and related geographical information. Sometimes, these feeds are covering the same network of public transportation and can overlap for certain stations, routes and trips. This undergraduate thesis describes a way to merge such trips in a manner that retains all the relevant information, as well as recognizing duplicate trips and merging trips that are partially included in each other.
Felix Jablonski
NEDard: Using Multi-Sense Embeddings for Named Entity Disambiguation Presentation

Abstract This thesis deals with the task of Named Entity Disambiguation. When analyzing a text, it is important to disambiguate mentions of entities such as people, companies, or concepts so that multiple appearances of the same entity can be identified as such. One way to disambiguate entities is to link them to their unique entity in a so-called knowledge base. A knowledge base is a source that stores information about objects like companies, fruits, or people. In this thesis given a text with mentions of such entities, ambiguous mentions are disambiguated and linked to the correct entity in Wikidata. For example "Apple" as fruit or as the company. This thesis proposes two new models (called NEDard and NEDardv2) to solve this task. Machine learning is used to derive a comparable representation of mentions depending on their textual context, and this representation is used to perform the disambiguation. The models are compared to other approaches on different evaluation sets. The evaluation has shown that the proposed models do not solve the NED task better than the baselines. However, it has been shown that there is potential in combining the proposed models with others.
Pascal Muckenhirn
Präzise Erkennung von Sonderzeichen aus layout-basierten Textdokumenten am Beispiel der häufigsten europäischen Sonderzeichen Presentation

Abstract Das Ziel dieser Arbeit ist es, die Erkennung und Übersetzung von Sonderzeichen in layout-basierten Textdokumenten (hier: PDF) zu verbessern. Layout-basierte Textdokumente und insbesondere PDFs beinhalten einige Herausforderungen. Zum einen enthalten sie Ligaturen. Bei Ligaturen werden mehrere Buchstaben, die aufeinander folgen, näher zusammengeschrieben. Dies wird allerdings nur bei bestimmten Buchstabenfolgen angewandt. Gründe hierfür können stylistische oder historische sein. Ein Beispiel für solch eine Ligatur ist das Zeichen ”ffi”. Aufgrund von Ligaturen ist es dem Nutzer nur möglich nach dem Wort ”efficient” zu suchen, wenn er den Unicode des Zeichens ”ffi” als Teil des Wortes eingibt. Dieses Zeichen ist auf einem Tastaturlayout nicht zu finden, sodass der Benutzer sich den Unicode anderweitig beschaffen muss. Außerdem enthalten diese Dokumente auch kombiniert diakritische Zeichen, welche zumeist eine bestimmte Betonung signalisieren sollen. Sie werden häufig als zwei Zeichen gespeichert und müssen deshalb wieder zusammengebaut werden. Die Frage hierbei ist allerdings, wie dies gemacht wird. Für das Beispiel ”á” würde hierbei das Zeichen ”a” als Basiszeichen und das Zeichen ” ́” als diakritisches Zeichen gespeichert werden. Die größte Herausforderung ist allerdings, dass die Zeichen in bestimmten Fällen nur gezeichnet vorliegen. Hierbei ist also nur die Form des Zeichens und dessen Position zur Erkennung des Zeichens nutzbar. Um diese Ziele zu erreichen wird eine Kombination aus 2 Ansätzen genutzt. Zum einen wird die Form des Zeichens und zum anderen die umliegenden Zeichen analysiert. Diese beiden Ansätze werden mittels 2 getrennten Machine-Learning-Modellen umgesetzt, die im finalen Ablauf zusammenarbeiten. Durch Training der Modelle auf insgesamt 20 verschiedenen Schriftlayouts, zu je 100 PDFs, wird ein großes Spektrum an Dokumenten abgedeckt. Die Evaluation zeigte, dass das finale (kombinierte) Modell mehr als viermal genauer als aktuelle Ansätze ist.
Marc Ingold
Researcher Homepage Identification and Name Extraction Presentation

Abstract The topic of this thesis is the implementation and evaluation of a machine learning approach for the information extraction from researcher homepages. The key aspects in this work are the data acquisition from the non-profit organization Common Crawl and the development and assessment of two machine learning models. A model for the identification of researcher homepages from a dataset of arbitrary web documents and a model for the extraction of information from the researchers homepage. Exemplary, the researchers name was extracted. The algorithm choice for both models was restricted to methods that are fast to train and straight forward to interpret such as the Random Forest and linear models with Stochastic Gradient Descent learning. The classification of the web document type was done using a multi-view approach. On the basis of two disjoint feature sets, namely the URL surface patterns and the web page content features, two machine learning models were trained. The final prediction was obtained by combining both of the models. A F1 score of 68% was achieved for the identification of researcher homepages. The extraction of the researchers name was done by extending a simple heuristic with machine learning features. An increase of 6 percentage points in F1 score was achieved in comparison to the heuristic, resulting in a F1 score of 94% for the final researcher name extraction model.
Katharina Matulla
Wohin mit den Ladesäulen? Lösungsansätze zur optimalen Platzierung von Ladeinfrastruktur für Elektrofahrzeuge Presentation

Abstract Recent growth of the electric vehicles – especially electric cars – market calls for setting up an efficient infrastructure for electric charging stations that doesn’t only accommodate this growth but also accounts for optimizing implementation costs and reducing drivers’ range anxiety. While there already exist multiple methods for calculating optimal locations for charging stations, most of these methods require costly or unavailable data. This thesis showcases three different algorithms that rely only on open-source Points of Interest (POIs) from OpenStreetMap (OSM) to calculate optimal placements of electric charging stations in a given area. The first algorithm is k-means clustering based on Euclidean distances. The second is a clustering method based on the betweenness centrality of POIs in a graph using shortest paths. The third is a genetic algorithm which solves the p-median problem while also using shortest paths. All three algorithms lead to consistent output; clusters of POIs where one POI is chosen as an optimal charging station for its cluster. For the purpose of this thesis, the aforementioned algorithms were applied to three areas: North-Amsterdam, North-Seattle and Davutpasa-Campus (Istanbul). The computed optimal outputs in all three areas are displayed on an interactive map in a webpage and are evaluated against optimal solutions gathered from past research. This undergraduate thesis is developed in connection to a project managed by the Fraunhofer Institute for Solar Energy Systems (ISE) called „EnStadt:Pfaff“. The project aims to transform a former industrial area in Kaiserslautern, Germany into a modern,climate neutral, urban quarter. The work presented here is supposed to not only be applicable for this area but several other areas in the future.

2018

Olivier Puraye
Dataset Format Analysis and Column Classification for CompleteSearch Presentation

Abstract In this thesis, we analyse tabular text files with the objective to find suitable parameters to make them searchable using the features of CompleteSearch. We solve this problem in two separate stages. In a first stage, we build a file analyser that parses the text files to gather relevant features related to the format of their content. In a second stage, we use a Naive Bayes classifier to associate the columns in the text files to their appropriate CompleteSearch parameter classes. Furthermore, we integrate this automatic parameter suggestion into the Complete-Search web application and incorporate its user feedback into the classifier training in order to further improve the suggested CompleteSearch configurations over time.
Johannes Kalmbach
Efficient and Effective Search on Wikidata Using the QLever Engine Presentation

Abstract The QLever engine allows effcient semantic search on a combination of RDF knowledge bases and fulltext corpora using an extension to the SPARQL query language. In this thesis we present several improvements to QLever that allow performing almost arbitrary SPARQL queries on the Wikidata knowledge base. Those improvements heavily reduce the RAM usage of QLever without significantly increasing the time needed for query processing.
Jasmin Denk
Finding Semantic Units in Deep Language Models Presentation

Abstract In this thesis, we want to reproduce the results of the paper \Learning to Generate Reviews and Discovering Sentiment" [Radford et al., 2017]. The authors achieved extraordinary results on sentiment analysis by training a neural language model on millions of product reviews to capture the concept of sentiment. Not only did their model achieve this task, it also evolved a single unit which is responsible for analysing the sentiment of the read data. Our goal is to implement our own language model and analyse its capability to evolve such a semantic, concept-containing unit following the approach described in the paper. We are also interested to observe the extent to which the size of the training data in uences the overall performance. In addition to product reviews,we train our language model on lyrics and emails. We want to see if a language model can also learn to recognize different semantic concepts, such as the mood of lyrics or to classify if an email is spam, with one single unit. While we do not quite reach the results of the paper, our model's best results approximates them. We also analyse the existence of such specific semantic units in other areas of text analysis. Furthermore, we describe a process with which we can identify potential semantic units in language models.
Patrick Bühler
GTFS-Editor Presentation

Abstract Verkehrsbetriebe können die Daten ihrer Fahrpläne in Form von GTFS-Dateien (General Transit Feed Specification) im Internet bereitstellen. Diese sind in der Form von CSV-Textdateien in einer Zip-Datei gespeichert. Diese Dateien zu verändern kann ziemlich mühselig sein, da die Textdateien in den meisten Fällen sehr groß und unübersichtlich sind. Deswegen wäre es vorteilhaft, wenn man einen Editor hätte, mit dem man diese Feeds einfach verändern könnte. Dieser GTFS-Editor soll einfaches und benutzerfreundliches Editieren der Daten ermöglichen.
Samuel Roth
Identification and Information Extraction on Scientists Homepages in the Common Crawl Web Archive Presentation

Abstract Aim of this work is the development of a system to detect personal Webpages of scientists and extract structured data - the scientist name, affiliation, gender, profession - from these personal Webpages. In addition we detect occurrences of the scientists in other Webpages text to use these texts as information sources for search queries about the scientist in question. As a source for raw data we use Common Crawl1 - an open Web archive of 3.16 billion+ crawled Webpages. For the classification task we reviewed recent work on categorizing Webpages and implementedWeb-specific features to train a supervised binary classifier using existing and manually labeled training data. To extract the correct name we utilized Named Entity Recognition techniques and Support Vector Machines with special features for gender, profession and affiliation combined with available lookup tables to improve performance. Finally we use the retrieved data to create a Broccoli [1] index so we can use the data to search for existing scientists in different contexts.
Yannick Ries
Programmierumgebung für den Informatikunterricht an Gymnasien Presentation

Abstract An Gymnasien in Baden-Württemberg wird der Informatikunterricht stark ausgebaut. Für den Unterricht werden neue, zeitgemäße und didaktisch sinnvolle Werkzeuge benötigt. Diese Arbeit befasst sich daher mit der Erstellung einer Programmierumgebung für den Unterricht. Zu diesem Zweck wurden zunächst Anforderungen an eine Programmierumgebung im Umfeld der Schule analysiert und bereits existierende Programmierumgebungen auf diese Anforderungen geprüft. Unter Beachtung der ermittelten Anforderungen und mit Kenntnis der wertvollen Komponenten der Alternativen wurde eine Programmierumgebung mithilfe des PyQt Frameworks erstellt. Sie erlaubt den Schülerinnen und Schülern (SuS) die praktische Auseinandersetzung mit den informationstechnischen Inhalten des Lehrplans mit Python. Sie bietet dabei zahlreiche, das Verständnis fördernde Features wie schrittweise Ausführung des Codes, schülergerechte Fehlermeldungen und Visualisierung des Schülercodes. Abschließend wurde die Programmierumgebung mit einer Schülergruppe im Unterricht getestet und evaluiert.
Niklas Baumert
Web-scalable Named-entity Recognition and Linking with a Wikipedia-backed Knowledge Base Presentation

Abstract This thesis is about WiNERLi, a software to solve the named-entity recognition and the entity linking tasks. It does so by utilizing a knowledge base built from Wikipedia. Its major function is to provide input files for QLever1, another system at the department. In the following I will define the named-entity recognition and entity linking tasks and take a look at how other studies tackled the tasks. A central aspect of WiNERLi is its Wikipedia-backed knowledge base. The knowledge base is built by extracting page titles, links and infoboxes from Wikipedia pages. WiNERLi uses sub-sequences of variable lengths to determine entities by querying those against the knowledge base. I performed general tests in entity detection, entity categorization and entity linking with two datasets. Its performance in those general tests is not particularly high. It has F1-Scores of 0.3810–0.4768 in entity detection; 0.1712–0.3912 in entity categorization; and 0.2857 in entity linking.
Michael Lubitz
Who drives the market? Sentiment analysis of financial news posted on Reddit and Financial Times Presentation

Abstract In this thesis, we evaluate whether the sentiment in financial news articles posted on Reddit can predict future stock market returns. For this purpose, we extracted all submissions that have been posted on the economics subreddit between January 2008 and July 2017. We evaluate the predictive power of Reddit by comparing the sentiment of all submitted articles posted on a trading day to the corresponding closing value of the S&P 500 stock index. The sentiment in these articles is calculated using a dictionary-based approach and supervised machine learning models based on different feature extraction methods. In addition, we perform a weighted sentiment calculation by incorporating the number of votes and comments for Reddit submissions into our models. News published in the Financial Times will act as a baseline. Our results suggest that the predictive power of Reddit is slightly better than using standard news paper analysis. We achieve 56.49% of accuracy in predicting the future direction of the stock market which corresponds to the results of recent academic research.

2017

Jon Ezeiza Alvarez
A review of word embedding and document similarity algorithms applied to academic text Presentation

Abstract Thanks to the digitalization of academic literature and an increase in science funding,the speed of scholarly publications has been rapidly growing during the last decade. This is obviously very positive, but it leads to a few logistical problems we have been tackling lately. Article availability is, for the most part, a solved problem, a scientist can get access to virtually any publication on demand. There’s also a very comprehensive tool-set for retrieval of relevant articles by now and the last couple of years have seen a further surge, with a new wave of AI based retrieval tools. However, the latest global surveys about reading patterns suggest that it is now harder than ever for a professional scientist to keep up. There is no human endeavor that is better publicly documented than scientific progress, yet, we are starting to loose the grasp of it. It is no longer viable for a single person to keep a global view of science, not detailed enough or updated enough to be useful at least. Conversely, recent advancements in natural language processing (NLP) and high volume distributed computation are starting to open the door to an alternative. We propose the long term goal of creating an automatic toolbox for indexing, understanding and interpreting all scientific literature. This work is intended to be a small early step in that direction. Word embeddings, which facilitate working with abstract semantic concepts in numerical form, have become the foundation of modern NLP. Here we perform a thorough review of the most pivotal word embedding algorithms and perform an empirical evaluation on academic text to identify the best alternatives for the described use case. We also extend the concept of word embeddings to documents. We perform a similar review of recent document modeling algorithms and evaluate them on titles, abstracts and full articles.
Janosch Piotr Pelzer
Entwicklung einer vernetzten Bilderbuch-Anwendung für ältere Menschen mit geringer Medienkompetenz Presentation

Abstract Das Thema dieser Bachelorarbeit ist die Entwicklung einer Anwendung, die älteren Menschen, mit niedriger Medienkompetenz, das Betrachten von digitalen Fotoal-ben ermöglichen soll. Durch eine einfache und intuitive Bedienung der Anwendung wurde versucht dies zu erreichen. Gegenüber klassischen, physischen Bilderalben hat das Programm den Vorteil, dass digitale Bilderbücher über das Internet an die Betrachter versandt werden können. Außerdem ist das nachträgliche Editieren und Ergänzen dieser möglich. Um die Bedürfnisse der Nutzer und deren Anforderungen an die Anwendung verstehen zu können, wurde durch eine Recherche erörtert, welche Probleme und Hürden ältere Menschen bei der Benutzung moderner Computertech-nologien haben. Anschließend wurde die sogenannte Persona-Methode angewandt, in welcher mithilfe von Anwenderprofilen, die verschiedene Nutzergruppen vertreten, die jeweiligen Anforderungen der Nutzer bestimmt wurden. Das gewonnene Wis-sen ist in die Entwicklung des Programms eingeflossen. Durch eine anschließende Evaluation wurde geprüft, inwiefern die entwickelte Anwendung den Anforderungen entspricht. Das Ergebnis der Evaluation bestätigte die Nutzbarkeit des Programms.
Daniel Bindemann
Erweitern von Aqqu durch AutoSklearn Presentation

Abstract Seien es autonom fahrende Autos, Systeme für präazise Gesichtserkennung oder intelligente Anti-Spam-Filter – Eine Vielzahl heutiger Technologien verdankt ihren Erfolg den Fortschritten im Bereich des maschinelles Lernens. Ein Gebiet der Informatik, dessen Erfolg unter anderem auch auf maschinellem Lernen basiert, ist das Natural Language Processing (zu Deutsch auch als Computerlinguistik bezeichnet). In diesem Gebiet wird versucht, natürlichsprachliche Ausdrücke mit Hilfe des Computers zu analysieren und deren Bedeutung zu interpretieren, um zum Beispiel auf natürlichsprachliche Fragen die passende Antwort in einer Sammlung von Daten finden zu können. Insbesondere für Nutzer, welche nicht im Bereich der Informatik versiert sind und ihre Fragen nicht in formalen Abfragesprachen wie SQL oder SPARQL ausdrücken können, könnten solche Systeme es möglich machen, benötigte Informationen schnell und einfach durch einen kurzen Satz im Internet ausfindig zu machen. Aber auch Nutzer, welche formale Abfragesprachen beherrschen, könn- ten von solchen Systemen profitieren, da sie ohne Wissen über die genaue Art der Datenspeicherung und ohne umständliche Anfragen effizient Informationen aus Wis- sensdatenbanken extrahieren könnten. Da das maschinelle Lernen ein zentraler Bestandteil für den Erfolg solcher natürlich-sprachlicher Suchmaschinen ist und in vielen kürzlich entworfenen Systemen verwendet wird, wäre es ein sinnvoller Versuch, diese Systeme durch Fortschritte im Bereich des maschinellen Lernens zu erweitern. Das Ziel dieser Arbeit ist es, ein erfolgreiches System für das Beantworten natürlich-sprachlicher Fragen, Aqqu , mit einem modernen Toolkit für automatisiertes maschi- nelles Lernen,auto-sklearn, zu erweitern. Dadurch soll erreicht werden, dass Aqqu einen größeren Anteil an Fragen korrekt beantworten kann bzw. bei Fragen mit mehreren möglichen Antworten die Menge der korrekten Antworten präziser ausfindig machen kann. Im Folgenden stelle ich zunächst die Funktionsweise und wichtigsten Features dieser zwei Systeme vor (zusammengefasst aus den zugehörigen Papers [1] und [2]). Im Anschluss beschreibe ich meine Ansätze, um die Systeme miteinander zu verbinden und evaluiere schließlich die Ergebnisse dieser Ansätze.
Claudius Decker
Name Entity Recognition Presentation

Abstract Das Thema dieser Bachelorarbeit ist die Entwicklung einer Anwendung, die Named Entities in natürlich-sprachlichen Texten erkennt und mit ihrem korrespondierenden Eintrag in einer Wissensbasis verbinden kann. Named Entities sind Objekte der realen Welt, wie Personen, Organisationen oder Orte, die mit einem Eigennamen bezeichnet werden. Die Erkennung der Named Entities wird mit zwei Algorithmen des maschinellen Lernens, dem Perzeptron und der logistischen Regression, umgesetzt. Dabei wird versucht, die Resultate durch ein Entity-Linking-Feature zu verbessern. Die beiden Algorithmen werden hinsichtlich ihrer Performanz ausgewertet und in ihrem theoretischen Hintergrund beleuchtet. Dabei zeigt sich, dass das Perzeptron in dieser speziellen Aufgabe der logistischen Regression überlegen ist. Während mit dem Perzeptron ein maximaler F1-Score von über 0,99 erreicht werden konnte, liegt der mit der logistischen Regression erreichte, maximale F1-Score bei 0.82.
Zhiwei Zhang
Public-Transit Data Extraction from OpenStreetMap Data Presentation

Abstract The major objective of this paper is to acquaint the reader with details on how to extract public transit data from OpenStreetMap 1 (OSM) data. To achieve this aim, we implement a program extracting train-related data from an OSM file and introduce its development to help the reader understand our method. Its development is broken into three basic incremental steps. In the first step, we search for the information related to trains with the assist of some particular attributes and store it into a railway network. In the second step we fix attention on completing the network step by step through solving some problems, i.e., incorrect order, gaps, missing class label and so on. In the last step we transform the network into a General Transit Feed Specification 2 (GTFS) feed. Through uploading the feed to Transit Visualization Client 3 (TRAVIC) and OpenTripPlanner 4 (OTP), this network turns visible and we can run some routing test. The visible displayed result in TRAVIC and test result in OTP demonstrate that our method works as expected. Due to the limitation of OSM data, some gaps are irreparable and bias exists in distinguishing between regional railway and long-distance railway. Therefore, further research is needed to improve the performance of this method.
Phong Tran
Semantischer Vergleich von Fahrplandaten Presentation

Abstract Diese Bachelorarbeit beschäftigt sich mit der Entwicklung eines Programms, dass den Vergleich von zwei Fahrplandaten im GTFS (General Transit Feed Specification)Format ermöglicht. Viele Verkehrsunternehmen veröffentlichen ihre Fahrpläne als GTFS Feeds. Möchte man nun zwei Feeds zusammenfügen kann es zu Überschneidungen bei den Trips kommen, falls diese Feeds das gleiche Gebiet abdecken. Unser Programm vergleicht zwei gegebene Feeds und gibt Informationen zu abweichenden Servicezeiten, fehlenden Fahrten und Haltestellen aus. Diese Informationen können dann anschließend von weiteren Programmen verarbeitet werden.
Eneko Pinzolas Murua
Word Embeddings in Search Engines, Quality Evaluation Presentation

Abstract n the recent years, Neural networks have become very popu- lar. They are being used in almost any field of computer science, and several of them are turning out to be successful. Information retrieval requires a fast method that compares two batches of text and gives a score. That score has to represent how similar both texts are. Most approaches rely on basic text comparisons, while trying to grab extra information from the users to cater the results more to their liking. In this bachelor thesis, we propose the addition of neural network techniques to the comparison process. More specifically, the usage of word vectors. Revolving word vectors, various techniques have been documented and tested, and while most of them did not have positive results, the one that did has been more thoroughly analysed. The approach that is presented here relies on representing queries and documents as clusters of words, which are points in space. Then, to quickly compute the score, the average linkage has been selected as a comparison method, that is, the distance between the means of the clusters. This approach has given positive results over the baseline in both test databases, and the results have been documented below. The results show a high potential in the use of word vectors in the IR area.

2016

Maximilian Dippel
"Erkennung von Textparagraphen in wissenschaftlichen Publikationen mit Techniken des maschinellen Lernens" Presentation

Abstract m Rahmen dieser Arbeit werden Methoden zur automatisierten Erkennung und Visualisierung von menschlich-intuitiven Paragraphen in wissenschaftlichen Publikationen behandelt. Diese extrahierten Paragraphen sollen fur weitere Verwendungszwecke wie etwa eine Klassifizierung der Paragraphen in Uberschriften, Bildunterschriften, inhaltlichem Fließtext etc. bereitgestellt werden. Ferner sollen Teile der so klassifizierten Paragraphen perspektivisch als Basis einer semantischen Suche dienen. Es werden verschiedene Techniken des maschinellen Lernens eingesetzt und ihre Ergebnisse evaluiert. Hierzu werden geeignete Featurevektoren und entsprechende Trainingsdaten erstellt. Wir werden sehen, dass Support Vector Machines mit einer Precision von 0.98 und einem Recall von 0.98 die besten Ergebnisse liefern.
Daniel Siebrecht
Entwicklung eines Seniorenhandys auf der Basis einer Android App Presentation

Abstract Die vorliegende Arbeit beschäftigt sich damit, existierende Smartphones durch eine Anwendung (App) auf ein Minimum an Funktionalität zu reduzieren, um die Bedienung für Senioren und Menschen mit Einschränkungen zu vereinfachen. Dazu wurde untersucht, welche sensorischen, körperlichen und geistigen Einschränkungen die Bedienung eines Smartphones beeinflussen können und welche Designaspekte diesen bei der Gestaltung der App entgegenwirken können. Außerdem wurde betrachtet, welche Anforderungen Senioren an ein Handy haben. Bezugnehmend auf diese Ergebnisse wurde eine App entwickelt, welche die Benutzeroberfläche von Android durch eine einfache Darstellung ersetzt. Die App verfügt außerdem über einige Assistenzfunktionen für den Nutzer, auf welche eine autorisierte Person über ihr eigenes Handy und eine separate App zugreifen kann. Zur Evaluation der App wurde überprüft, inwieweit die herausgearbeiteten Designaspekte umgesetzt wurden. Abschließend wurde getestet, ob Senioren ohne Smartphone-Kenntnisse die App bedienen können.
David Spisla
Erkennung von Fließtext in PDF-Dokumenten Presentation

Abstract Diese Arbeit beschreibt ein Verfahren zur Erkennung und Extraktion von Fließtext in PDF-Dokumenten. Eine Extraktion von Fließtext erleichtert die inhaltliche Suche nach Informationen in einem PDF. Das Verfahren nutzt Techniken des Maschinellen Lernens, um den Fließtext in einem ersten Schritt von den übrigen Bestandteilen (Tabellen, Bil- der,Überschriften, Referenzen, usw.) auszusondern. Dies erleichtert den zweiten Schritt,in welchem zusammengehörende Abschnitte, die z.B. durch Bilder oder ein Seitenende getrennt werden, erkannt und zusammengeführt werden. In beiden Schritten wird die Erkennung mittels sorgfältig ausgewählter Featurevektoren ermöglicht. Dies ermöglicht zum Schluss eine Zusammenführung aller Fließtextelemente, die dann für eine inhaltliche Suche genutzt werden können. Trainings- und Testphasen werden mithilfe der Python- Bibliothek scikit-learn durchgeführt, welche eine Reihe von bekannten Lernalgorithmen bereitstellt. Die empirische Analyse hat für alle Lernmodelle nahezu identische Ergebnisse ergeben. 2 Varianten (einmal je 100 Trainings- und je 100 Testdaten und einmal 200 Trainingsdaten, die auch als Testdaten verwendet werden) werden ausgetestet. Bei Variante 1 werden für die Erkennung von Fließtext folgende durchschnittliche Analysewerte ermittelt: precision = 98 %, recall = 98 % und f1-score = 98 %. Bei Variante 2 liegen diese Werte alle bei 97 %. Für die Erkennung der zusammengehörenden Abschnitte werden in allen Analysewerten 100 % erreicht. Aufgrund der g ünstigen Laufzeit kommt das Lernmodell Bernoulli Naive Bayes im eigentlichen Extraktions-Programm zur Anwendung
Matthias Urban
Extended Question Answering on Freebase Presentation

Abstract Diese Bachelorarbeit beschäftigt sich mit Erweiterungen an dem Question Answering System (dt. Fragebeantwortungssystem) Aqqu [2]. Aqqu ist in der Lage einfache, natürlichsprachliche Fragen in SPARQL-Abfragen für die Wissensdatenbank Freebase zu übersetzen. Wenn man diese SPARQL-Abfragen ausführt, erhält man die Antwort auf die entsprechende Frage. Bisher war Aqqu nicht in der Lage Superlativ-Fragen wie “Was ist das größte Land in Europa?” oder Temporal-Fragen wie “Wer war der erste Präsident der Vereinigten Staaten?” zu beantworten. Aqqu konnte außerdem nur Fragen beantworten, deren SPARQL-Abfrage nur aus einer (möglicherweise k-ären) Relation besteht. Deshalb konnten Fragen wie “Wer ist die Frau des Präsidenten der Vereinigten Staaten?” nicht beantwortet werden. Im Folgenden werden diese Probleme mit mehreren Erweiterungen an Aqqu gelöst, sodass Aqqu in der Lage sein wird Fragen dieser Typen zu beantworten. Des Weiteren ist das Answer Type Matching (dt. Antworttyperkennung) von Aqqu sehr einfach gehalten. Es wurde nur das Fragewort betrachtet. Diese Bachelorarbeit stellt ein verbessertes Answer Type Matching vor. Dieses basiert auf Machine Learning und betrachtet eine Reihe verschiedener Features (dt. Merkmale). Es funktioniert mit den Typen von Freebase und ist in der Lage die Antworttypen von mehr Fragen richtig zu bestimmen.
Elke Schächtele
Inhaltsbezogene Suche nach gleichartigen Klängen Presentation

Abstract In der vorliegenden Arbeit wurde ein Algorithmus für die inhaltsbezogene Suche nach gleichartigen Klängen implementiert. Eine Suchanfrage wird in Form einer Beispieldatei gestellt. Zu dieser sollen ähnlich klingende Audiodateien in einer Datenbank gefunden werden. Entscheidend für die Realisierung dieses Suchszenarios ist die Beantwortung der Frage, anhand welcher Merkmale zwei Klänge als ähnlich beurteilt werden können. Im Gegensatz zu einem Großteil der bisherigen Forschungsarbeiten wird in dieser Arbeit eine umfangreichen Literaturübersicht über verschiedene Forschungsperspektiven auf das Phänomen Klang und dessen Wahrnehmung durch den Menschen der Implementation des Algorithmus voran gestellt. Der Algorithmus wird anhand eines Benchmarks evaluiert, der mithilfe von empirischen Daten erstellt wurde. Das Resultat legt nahe, dass der typische Aufbau eines Algorithmus für die inhaltsbezogene Suche nach gleichartigen Klängen der menschlichen Wahrnehmung nur teilweise gerecht werden kann. Die Ergebnisse stehen im Einklang mit Erkenntnissen vergleichbarer Arbeiten: In diesen wurde in jüngster Zeit aufgrund der Komplexität des Forschungsgebiets zunehmend die Notwendigkeit des Ausbaus von interdisziplinärer Forschung betont.
Natalie Prange
Query Auto-Completion using an Abstract Language Model Presentation

Abstract In recent years, query auto-completion has become a common feature of search engines. While typing a query into a search engine’s input field, the user receives suggestions as to how his query could be completed or extended. Most approaches towards this issue rely on query logs in order to provide meaningful completion suggestions. Sufficiently large and recent query logs, however, might not be available for researchers or search engines with a small user base. Moreover, purely rely-ing on query logs means that queries which have not been seen before will not be suggested. In this bachelor thesis, we propose a novel approach using an abstract language model in which specific entities have been replaced by abstract categories. When at some point during query completion the language model suggests such a category as the most likely word to follow, it is replaced by an entity assigned to the same category. The possible entities are ranked using an entity prominence score and word vector similarity. The top k completions are o˙ered to the user as completion suggestions. We analyzed our approach on three datasets. For each dataset, we compared di˙erent versions of our query auto-completion algorithm to a baseline given by a basic version of our algorithm. The results illustrate the role of di˙erent components of our algorithm and indicate a high quality of our completion suggestions.

2015

Rick Gelhausen
Context-Aware Search Spaces for Queries with Spatial Relations Presentation

Abstract Web-mapping services, like Google Maps, allow natural language queries, like \Hotels Freiburg". These queries are interpreted as \Hotels in Freiburg" or \Hotels near Freiburg". In this thesis, we introduce the two new spatial relation \between" and the compass directions, allowing queries like \Gas stations between Freiburg and Stuttgart" or \Hotels north of Freiburg". To achieve this, we analyse many different queries and decide whether they make sense in a given context. It might make sense to search for \cities between cities", whereas it makes less sense to search for \cities between countries". Then, we create a toolbox that returns a search polygon for every context-aware query. In a last step, we compare the results from our toolbox with our expectations. We show that nearly all of our queries return useful results and conclude what possibilities are open for future work.
Simon Weidner
Fine-Grained Population Estimation Presentation

Abstract This thesis introduces a new method to estimate population numbers for areas of various sizes. The main idea is to estimate population numbers of buildings by exploiting their environment. For this we use features as the count of nearby schools, supermarkets and many more. We obtain such data from OpenStreetMap, which is a volunteered project providing Google-Maps-like data. State of the art approaches mainly rely on costly three dimensional images and/or census data of the local areas. We use machine learning to predict population values. Therefore, our method can be used without local census data. For evaluation purposes we compared our results to the official census data of various cities, districts and villages. Our results indicate that our method basically works, but requires further research especially to distinguish between different types of houses more precisely.
Jerôme Meinke
In-memory OLAP aggregation on GPUs using CUDA Dynamic Parallelism Presentation

Abstract Most queries involved with Online Analytical Processing (OLAP) depend on the functionality of aggregating data along the multidimensional hierarchies of an OLAP cube. In real-time OLAP, aggregated data for interactive operations e.g. roll-up and drill-down is computed on-the-fly. Fast response times are essential and can be accelerated significantly through data-parallel computation on graphics processing units (GPUs). In this thesis, an existing parallel algorithm is modified to use a technology called CUDA Dynamic Parallelism (CDP). Using this technology, GPU programs can be launched directly from within other GPU programs to extract more parallelism. Furthermore, we present a preaggregation method using the CUDA shuffle command to optimize both GPU implementations. For evaluation purposes, we additionally implement a sequential aggregation algorithm. Our experiments show that the single-threaded CPU implementation is outperformed by the GPU implementations by 16 to 218 times. The experiments further show that the CDP implementation reaches a speedup of 3.72 times over the non-CDP implementation when processing queries for an artificial OLAP cube. However, using CDP causes an average of 1.42x slowdown to the processing of queries in a typical OLAP scenario.
Vivica Wirth
Kostenrundung von Kanten auf Pfaden Presentation

Abstract Diese Arbeit beschäftigt sich damit, Kosten an Kanten in Graphen zu runden. Grundlage dabei ist das mathematische Runden der einzelnen Kanten. Da dieses aber beliebig schlecht werden kann, soll ein besserer Algorithmus gefunden werden. Diese Arbeit befasst sich zunächst mit dem mathematischen Runden, um herauszufinden wo und wie dieses scheitert. Danach werden eigene Ideen entwickelt und präsentiert. Über alternierendes Runden, bei welchem Kanten abwechselnd auf- und abgerundet werden, gelangt man zu gewichtetem Runden. Bei diesem wird sich der Rundungsfehler gemerkt und in Abhängigkeit vom Rundungsfehler gerundet. Die empirische Auswertung zeigt dabei, dass das gewichtete Runden deutlich besser ist, als das mathematische Runden.
Matthias Hertel
Partitioning of Public Transit Networks Presentation

Abstract artitionierungen von öffentlichen Verkehrs-Netzwerken werden verwendet um die Berechnungszeit von Routen oder die Vorberechnungszeit bei Routenplanungs-Algorithmen zu beschleunigen. Das Ziel der Partitionierung ist es, kleine Partitionen der Haltestellen zu finden, die möglichst viel Verkehr in ihrem Inneren beinhalten, sodass möglichst wenige Verbindungen zwischen den Partitionen verkehren. Um solche Partitionen für das öffentliche Verkehrs-Netzwerk von Deutschland berechnen zu können, wird das öffentliche Verkehrs-Netzwerk als Graph modelliert, wobei Knoten Haltestellen repräsentieren und Kanten mit der Häufigkeit gewichtet werden, mit der Fahrzeuge zwischen den Haltestellen verkehren. Mit k-means-clustering, einem Fusions-basierten Algorithmus, partitioning using natural cut heuristics (PUNCH, engl. für “Partitionierung unter Verwendung von natürlichen Schnitt-Heuristiken”), und METIS werden vier Graph-PartitionierungsAlgorithmen getestet und mit einem Datensatz ausgewertet, der die Fahrpläne der Deutschen Bahn für das Jahr 2015 beinhaltet. Ergebnis der Auswertung ist, dass der Fusions-basierte Algorithmus und METIS kurze Laufzeiten haben und kleine Partitionen mit einem kleinen Schnitt erzeu- gen. K-means-clustering löst das Problem besser als erwartet. PUNCH wurde für ungewichtete Graphen entwickelt und benötigt einige Anpassungen für gewichtete Graphen.

2014

Iradj Solouk
A keyword query translator for Broccoli Presentation

Abstract A keyword query translator that is used by the semantic text search engine BROCCOLI will be introduced. This keyword translator interprets a string, which is given by the user, in a way that considers the underlying data structure of BROCCOLI and tries to consider the context of the given information. A GOOGLE-like keyword search field will be used. The keyword translation leads to user friendliness in terms of not requiring knowledge about the concept of the underlying ontology and the possibility of using keywords or parts of phrases as an input. This process provides a service that can be used in place of the normal incremental query creation process. The semantic interpretation of the input string requires natural-language-processing. WordNet, a lexical dabase for English words, and the Stanford part-of-speech tagger is used for part-of-speech tagging.
Manuel Ruder
Entitätserkennung auf einem Web-Korpus Presentation

Abstract Broccoli ist eine semantische Suchmaschine, die für das Durchsuchen der englischsprachigen Wikipedia entwickelt wurde. In einer früheren Arbeit wurde damit begonnen, broccoli für das Durchsuchen allgemeiner Web-Seiten zu erweitern. Hierzu mussten sowohl der Entitätserkenner als auch die Komponente zum Parsen der Seiten angepasst bzw. verallgemeinert werden. Hierbei zeigten sich einige Schwierigkeiten, wie etwa eine hohe Zahl an Falscherkennungen von Entitäten. In dieser Arbeit soll die Qualität der Suche durch einen verbesserten Entitätserkenner gesteigert werden. Dazu wurde unter anderem die Erkennung von Eigennamen verbessert. Ein neu geschriebener Disambiguationsalgorithmus soll zudem im Text vorhandene Mehrdeutigkeiten auflösen. Durch eine ebenfalls neu geschriebene Evaluations-Komponente können Falscherkennungen genauer untersucht werden als bisher. Für die Evaluations-Komponente wurde eine Auswahl an Artikeln aus dem Korpus mit Ground Truth Annotationen versehen.
Marcel Gangwisch
Entwicklung von Algorithmen zur Berechnung der aerodynamischen Oberflächenrauigkeit für mikroskalige Strukturen Presentation

Abstract Das thermische Wohlbefinden der Bewohner einer Stadt wird durch unterschiedliche meteorologische Größen beeinflusst. Eine wichtige Steuergröße stellt die Windgeschwindigkeit dar, da durch eine erhöhte Windgeschwindigkeit eine Reduzierung der thermischen Belastung stattfinden kann. Die bewegten Luftmassen in der Atmosphäre über einer Stadt werden durch die geometrischen Eigenschaften der Erdoberfläche beeinflusst. Insbesondere stellen Gebäude und die Vegetation ein Hindernis für die durchströmende Luft dar. Diese Wirkung wird durch die aerodynamische Oberflächenrauigkeit ausgedrückt. Zur Beurteilung dieser Wirkung wurden in der Arbeit verschiedene Ansätze zur Berechnung der Rauigkeit miteinander verglichen. Im Anschluss daran wurde das mikroskalige Modell “SkyHelios” vorbereitend für räumliche Berechnungen um eine räumliche Datenbank erweitert um das Management der Daten zu verbessern. Nachfolgend konnten der “Morphometrische Ansatz” (Lettau 1969), der “Effektive Höhen Ansatz” (Matzarakis und Mayer 1992; Mayer und Matzarakis 1992), sowie der “vereinfachte Ansatz” (Gál und Sümeghy 2007; Gál und Unger 2008) zur Berechnung der aerodynamischen Oberflächenrauigkeit implementiert werden. Dafür wurden die Daten in die Datenbank eingelesen und für jedes Gebäude mit der Rotationsmatrix für den zweidimensionalen Raum die frontale Fläche berechnet. Um eine räumliche Differenzierung der Oberflächenrauigkeit zu erhalten, wurde für jedes Gebäude eine Voronoizelle auf Basis der Gebäudeform berechnet. Im Anschluss daran konnte jeweils die Rauigkeit des Gebäudes auf Basis der Gebäudegeometrien bestimmt werden. Abschließend wurde das Verfahren für ein Modellgebiet in Stuttgart angewendet. Es wurden sowohl windrichtungsunabhängige Rauigkeitslängen, sowie effektive Höhen als auch windrichtungsabhängige Rauigkeitslängen berechnet. Die Ergebnisse der drei Ansätze wurden jeweils analysiert und miteinander verglichen.
Philipp Bausch
Semantische Suche auf einem WEB-Korpus Presentation

Abstract Broccoli ist eine auf den Texten von Wikipedia basierte Suchmaschine, welche das Durchsuchen dieser Texte mit dem Durchsuchen von strukturierten Daten (z.B. Ontologien) vereint. Wikipedia beinhaltet aber oft keine Berichte und Beschreibungen für einzelne kleinere Ereignisse. Eine in Politik interessierte Person ist vielleicht auf der Suche nach bestimmten Steuererhöhungsbeschlüssen oder -vorschlägen in den USA. Auf Wikipedia sucht man nach diesen Informationen oft vergebens. Aus diesem Grund wird in dieser Arbeit darauf eingegangen, wie die bisher von broccoli verwendeten Wikipedia Texte durch ein allgemeineren Web-Korpus ersetzt werden. Dieser wurde aus den von CommonCrawl 2012 veröffentlichten Datensatz extrahiert. Dazu ist es nötig die Texte von HTML Formatierungen zu befreien, da die von CommonCrawl angebotenen HTML-losen Texte nicht gezielt abrufbar sind und die Navigation enthalten ist. Hierzu wurde das Programm boilerpipe verwendet. Der Datensatz umfasst 3,8 Milliarden Seiten, die für jeden frei zugänglich sind. Außerdem wird beschrieben, wie Entitäten in den Texten erkannt werden, da dies bisher mit vielen Annahmen über die Strukturen in Artikeln von Wikipedia gelöst wurde. Um die Funktionsweise zu demonstrieren, wird dies für einen Korpus von rund 4,5 Millionen Webseiten untersucht. Dieser besteht aus rund 4 Millionen Seiten der TLD1 .edu und aus den Archiven von 20 Nachrichten Seiten.
Christian Ehrenfeld
Touchscreen-basierte Bedienkonzepte am Beispiel eines Bedienpanels für Frequenzumrichter Presentation

Abstract Diese Abschlussarbeit behandelt die Besonderheiten der Bedienung von berührungs- empfindlichen Anzeigen. Es wird gezeigt welche Möglichkeiten touch-bedienbare An- zeigen durch ihre direkte Steuerung bieten und welchen Einschränkungen sie unter- liegen. Für das Gestalten von Benutzeroberflächen für Touchscreens werden bewähr- te Methoden geschildert und der Unterschied zu Benutzeroberflächen, die mit Maus und Tastatur bedient werden, gezeigt. Auf der Grundlage dieser Erkenntnisse wurde die bestehende Benutzeroberfläche der Anwendung TruControl Power, welche für die Bedienung mit der Maus und Tastatur konzipiert wurde, so optimiert, dass diese auf einem Bedienpanel mit einem Touchscreen verwendet werden kann. Anschlie- ßend wurde eine Benutzerstudie durchgeführt um Bedienbarkeitsprobleme bei der Benutzung des Bedienpanels in Erfahrung zu bingen und beheben zu können.

2013

Marius Stefan Bethge
Detecting Duplicate Entities for Ontology Reconciliation Presentation

Abstract Die stetig wachsende Nachfrage nach Ontologien, in Verbindung mit dem Vorhaben mancher Ontologien das menschliche Wissen über alle Gebiete hinweg zu vereinigen, führt zur immer größer werdenden Datenmengen. Diese domänenübergreifenden Ontolgien, wie z.B. Freebase, sammeln Daten von diversen Quellen, welches je- doch leicht dazu führen kann, dass mehrere Einträge für ein einzelnes Objekt der reellen Welt stehen können. Wir stellen einen Algorithmus vor, welcher durch Iden- tifizierung und Vereinigung von duplikaten Entitäten die Anzahl an duplikaten Ein- trägen in einer Ontologie vermindert. Es war uns möglich eine hohe Präzision mit einer beachtlichen Anzahl an Vereinigungen zu erreichen. In einer angepassten, auf Freebase Daten basierenden Ontologie mit 50 Millionen Entitäten war es uns möglich 1,2 Millionen Duplikate zu identifizieren.
Axel Lehmann
Ein Kursverwaltungssystem für programmierlastige Lehrveranstaltungen Presentation

Abstract Daphne is a Coursemanagement System which is focused on programming courses. This work describes provided features and the required technical background. Daphen is used to manage participants, credits and deadlines. Using Subversion as verson control system and Jenkins to validate submission and provide feedback to participants.
Anton Stepan
Entity Unification for Semantic Search Presentation

Abstract In this paper we introduce and investigate a method to unify ontology datasets with location based data. The goal is to generate a bigger and more complex input set for semantic search engines. Our research explains a possible unification framework to solve this problem, outlines arising obstructions and demonstrates our algorithm with an application and an unification framework. The framework is based on the idea of awarding scores in the unification process, gathered from matching relations and only unifying two entities if they reach a specific score threshold. These scores and thresholds are very flexible as the user can define them in a config file, with the objective to tweak the result or set a specific weighting on a particular comparison category. With an experiment we review the performance and quality of our approach by unifying two datasets, based on Geonames (37 MB) and Freebase (244 MB) and achive more than 50% unification of the smaller ontology with an average execution time of 20 seconds.
Benjamin Malte Meier
High-Level Feature Extraktion aus Bewegungsdaten von Parkinson-Patienten Presentation

Abstract Seit über 20 Jahren wird untersucht, auf welche Weise Beschleunigungssensoren als Diagnose- und Therapieunterstützung für die sich als Bewegungsstörung manifestie- rende Parkinson-Krankheit eingesetzt werden können. Immer komplexere Sensoren und bessere Bewegungsmodelle in silicio erlauben es, diese Ansätze fortzuführen und die Bewegungen von Parkinson-Patienten als Ganzes zu untersuchen, anstatt anstatt sich auf einzelne Bereiche zu konzentrieren. Diese Arbeit steht am Beginn dieser Untersuchung und dokumentiert die Extraktion und Auswertung von ersten, komplexen High-Level Features aus Bewegungsdaten. Es werden zum Beispiel die Geschwindigkeit und die Positionen einzelner Körperteile verwendet, um die Posi- tionen einzelner Schritte oder die Vorwärtsneigung beim Gehen zu bestimmen. Mit einem Fokus auf die Auswertung der Schrittlänge beim Gehen, werden nicht nur Unterschiede zwischen Parkinson-Patienten und gesunden Versuchspersonen darge- stellt, sondern auch weitere Ansätze zur Analyse von Bewegungsdaten gezeigt.

2012

Christiane Schaffer
Automatische Relationsextraktion für die semantische Volltextsuche Presentation

Abstract Gegegeben seien Daten einer Ontologie. Das Ziel ist es, eine bestehende geografische Relation um zusätzliche Fakten zu erweitern. Dazu soll eine umfassendere, auf die Relation spezialisierte Datenbank verwendet werden. Die Herausforderung dabei liegt in der nicht vereinheitlichten Namensgebung von Ontologie und Datenbank. Da letztere weitaus mehr Fakten speichert als die bestehende Ontologie, müssen Lösungen für auftretende Mehrdeutigkeiten gefunden werden. Es werden verschie- dene Möglichkeiten beschrieben, Zuordnungen für die Relation zu finden, sowie eine Analyse dieser vorgenommen.
Robin Schirrmeister
Automatische Vorschläge zur Vervollständigung von Wikipedia Listen - Listenerkennung, Benutzeroberfläche Presentation

Abstract Diese Arbeit beschreibt das von Simon Skilevic und mir erstellte Programm WikiListSuggest, dass automatische Vorschläge zur Vervollständigung von Wikipedia-Listen generiert. In der Online-Enzyklopädie Wikipedia gibt es viele Listen zu bestimmten Themen, z.B. die Liste essbarer Blätter. Diese Wikipedia-Artikel werden von Hand erstellt und können unvollständig sein. Unser Programm WikiListSuggest versucht automatisch Vorschläge zur Erweiterung solch eines existierenden Artikels zu erstellen. Dazu versucht es im Wikipedia-Artikel die tätsächliche Liste zu erkennen und, mit Hilfe der semantischen Suchmaschine Broccoli, Vorschläge für weitere in die Liste gehörende Elemente zu generieren. In dieser Arbeit wird hauptsächlich die automatisierte Erkennung der Liste sowie die Benutzeroberfläche beschrieben.
Simon Skilevic
Automatische Vorschläge zur Vervollständigung von Wikipedia-Listen - Evaluation,Anfragegenerierung Presentation

Abstract Wikipedia-Listen sind Wikipedia-Artikel, die Listen zu einem Thema enthalten. Zum Beispiel enthält die Wikipedia-Liste mit dem Thema „essbare Pilze“ als Lis- tenelemente unterschiedliche Arten von Pilzen, die man ohne Risiko für die eigene Gesundheit verzehren kann. Da solche Listen manuell erstellt werden, können sie unvollständig sein. In dieser Arbeit beschreiben wir ein Programm, WikiListSuggest, das Vorschläge zur Vervollständigung solcher Listen liefert. Dafür extrahiert das Programm entsprechende Listenelemente einer Wikipedia-Liste und generiert automatisch eine Anfrage an die Semantische Suchmaschine “Broccoli”. Durch diese Anfrage soll WikiListSuggest möglichst die vollständige Liste zum Thema der Wikipedia-Liste erhalten. Diese Liste kann dann zur Vervollständigung der Wikipedia-Liste verwendet werden. Schwerpunkte dieser Arbeit sind die Anfragegenerierung sowie die Evaluation.

2011

Ina Baumgarten
Semantische Suche - Entitätenerkennung Presentation

Abstract This paper introduces an entity recognition for german articles, which extends the functionality of an already implemented semantic search engine at the University of Freiburg. Entities are defined as unique meaning of words and are stored by using a trie. For achieving a working entity recognition, previous knowledge was generated, consisting of a set of entities, articles and stopwords. Using the previous knowledge the entity recognition is performed in two essential steps: recognition of unambiguous entities and recognition of ambiguous entities. Moreover several methods are used for improving the results: scoring, postagging, stemming and decompounding. The entity recognition assigns with a sensitivity of 82% and an accuracy of 97% the correct meaning to an entity. Excluded are impossible entities, for which no fitting entity exist. In the future it is possible to improve the entity recognition by several modifications.
Niklas Meinzer
Semantische Suche in Zeitungstexten Presentation

Abstract Im Gegensatz zur klassischen Volltextsuche, bei der wörtliche Vorkommen der Suchanfrage in den durchsuchten Dokumenten gefunden werden, ist die Semantische Suche ein Verfahren, bei dem die Suchanfrage zunächst auf ihre Bedeutung untersucht wird. Ziel ist es, dem Benutzer zu ermöglichen, Anfragen in einer natürlicheren Form zu verfassen und abstraktere Formulierungen zu wählen. Broccoli ist eine existierende semantische Suchmaschine, die zum Beispiel die online Enzyklopädie Wikipedia durchsucht. Wir präsentieren eine semantische Suchmaschine für deutsche Nachrichtentexte, die auf Broccoli aufbaut. Das zentrale Problem hierbei ist die Entitätserkennung in deutschen Texten. Weitere Teilprobleme sind die automatisierte Datenbeschaffung von Online-Ressourcen und das Erstellen der Eingabedaten für Broccoli. In der anschließenden Evaluation der Entitätserkennung erreichen wir konstant sehr gute Werte.

2010

Mirko Brodesser
Fast Approximate Title Matching Presentation

Abstract Given a set of titles and a query, we want to find the title with the largest similarity to the query. The queries may contain spelling mistakes and words which are not part of the correct entry. Furthermore, no word separators in the query are expected and words of the correct title may be missing. Titles are usually short and consist of multiple words and numbers. We analyse several existing similarity measures like Edit distance and Jaccard similarity. Besides the quality, eÿciency is the other requirement of our algorithm and therefore we analyse and compare the best existing algorithms for eÿcient fuzzy match [CGGM03] and eÿcient duplicate detection [XWLY08]. We propose a new similarity measure as well as algorithm for its eÿcient computation in order to improve the existing algorithms in terms of quality and eÿciency. We show on two di˙erent collections that our algorithm is in most of the cases more eÿcient than the related work, yet achieves better quality.

Sektionen

Bachelor's and Master's Theses

Master's Theses

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

Bachelor's Theses

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

Start Footer

Benutzerspezifische Werkzeuge