Bachelor's and Master's Theses

Master's Theses
Bachelor's Theses

Master's Theses

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

back to the top of all theses

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.

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: 2018 | 2017 | 2016 | 2015 | 2014 | 2013 | 2012 | 2011 | 2010

back to the top of all theses

2018

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.
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.
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.

Bachelor's and Master's Theses

Master's Theses

2018

2017

2016

2015

2014

2013

2012

2011

2010

Bachelor's Theses

2018

2017

2016

2015

2014

2013

2012

2011

2010

Start Footer

Benutzerspezifische Werkzeuge