Effektives Widening mit Hashbasierter Partitionierung des Hypothesenraums
Dateien
Datum
Autor:innen
Herausgeber:innen
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
URI (zitierfähiger Link)
Internationale Patentnummer
Link zur Lizenz
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Sammlungen
Core Facility der Universität Konstanz
Titel in einer weiteren Sprache
Publikationstyp
Publikationsstatus
Erschienen in
Zusammenfassung
Im maschinellen Lernen werden Modelle so auf zuvor gesammelte Daten angepasst, dass sie diese Daten einerseits gut beschreiben und es andererseits auch erlauben, neue Daten aus derselben Quelle zu klassifizieren oder zu erklären. Die Anpassung eines Modells an die Daten geschieht dabei bei vielen Lernverfahren durch schrittweises Verändern. Änderungen, die zu einer Verringerung einer Kostenfunktion führen, werden übernom- men, andere verworfen. Damit handelt es sich beim Lernen um eine kombinatorische Optimierung und ein Suchproblem. Der Raum, in dem diese Suche ausgeführt wird, ist der Hypothesenraum, dessen Elemente durch Modelle repräsentiert werden. Inner- halb des Hypothesenraums erschweren topologische Merkmale wie lokale Minima und Maxima die Suche nach den besten Modellen. Trotz ihrer Anfälligkeit für solche Hinder- nisse sind heuristische Greedy-Algorithmen aufgrund ihrer Geschwindigkeit ein belieb- tes Verfahren zum Ermitteln geeigneter Modelle. In den meisten Fällen machen diese Algorithmen jedoch keinen Gebrauch von parallelen Recheneinheiten, wie sie heutzu- tage alltäglich sind. Im sogenannten Widening werden parallele Rechnerarchitekturen genutzt, um Greedy-Algorithmen im maschinellen Lernen zu verbessern, indem der Hy- pothesenraum auf verteilten Recheneinheiten breiter durchsucht wird. Dabei spielt eine große Rolle, dass parallel möglichst unterschiedliche Regionen des Raums durchsucht werden und so kritische Strukturen, wie beispielsweise die oben genannten lokalen Op- tima, umgangen werden können. In bisherigen Arbeiten zu dem Thema wurden dabei vor allem Verfahren erforscht, die entweder keine Kommunikation zwischen den Rechen- einheiten erlauben und den Hypothesenraum vor der Ausführung partitionieren, oder Distanzmaße für die Modelle verwenden, um diese explizit und mit ausgiebiger Kommu- nikation auseinanderzuhalten. In der vorliegenden Arbeit wird mit dem Bucket-Selektor ein Widening-Verfahren vorgestellt, welches mit relativ geringer Kommunikation, aber ohne Berechnung von Distanzen zwischen den Modellen, ein breites Durchlaufen des Hypothesenraums ermöglicht und damit qualitativ bessere Modelle findet als andere Verfahren. Besonders effizient kann diese Methode auf MapReduce-Systemen ausgeführt werden. Am Beispiel von zwei Problemen, dem hierarchischen agglomerativen Cluste- ring und der Join-Order-Optimierung, wird gezeigt, dass der Bucket-Selektor schneller bessere Ergebnisse erzielt als andere Methoden.
Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
Schlagwörter
Konferenz
Rezension
Zitieren
ISO 690
FILLBRUNN, Alexander, 2019. Effektives Widening mit Hashbasierter Partitionierung des Hypothesenraums [Dissertation]. Konstanz: University of KonstanzBibTex
@phdthesis{Fillbrunn2019Effek-46160, year={2019}, title={Effektives Widening mit Hashbasierter Partitionierung des Hypothesenraums}, author={Fillbrunn, Alexander}, address={Konstanz}, school={Universität Konstanz} }
RDF
<rdf:RDF xmlns:dcterms="http://purl.org/dc/terms/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:bibo="http://purl.org/ontology/bibo/" xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#" xmlns:foaf="http://xmlns.com/foaf/0.1/" xmlns:void="http://rdfs.org/ns/void#" xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/46160"> <dc:rights>terms-of-use</dc:rights> <dc:creator>Fillbrunn, Alexander</dc:creator> <dcterms:abstract xml:lang="deu">Im maschinellen Lernen werden Modelle so auf zuvor gesammelte Daten angepasst, dass sie diese Daten einerseits gut beschreiben und es andererseits auch erlauben, neue Daten aus derselben Quelle zu klassifizieren oder zu erklären. Die Anpassung eines Modells an die Daten geschieht dabei bei vielen Lernverfahren durch schrittweises Verändern. Änderungen, die zu einer Verringerung einer Kostenfunktion führen, werden übernom- men, andere verworfen. Damit handelt es sich beim Lernen um eine kombinatorische Optimierung und ein Suchproblem. Der Raum, in dem diese Suche ausgeführt wird, ist der Hypothesenraum, dessen Elemente durch Modelle repräsentiert werden. Inner- halb des Hypothesenraums erschweren topologische Merkmale wie lokale Minima und Maxima die Suche nach den besten Modellen. Trotz ihrer Anfälligkeit für solche Hinder- nisse sind heuristische Greedy-Algorithmen aufgrund ihrer Geschwindigkeit ein belieb- tes Verfahren zum Ermitteln geeigneter Modelle. In den meisten Fällen machen diese Algorithmen jedoch keinen Gebrauch von parallelen Recheneinheiten, wie sie heutzu- tage alltäglich sind. Im sogenannten Widening werden parallele Rechnerarchitekturen genutzt, um Greedy-Algorithmen im maschinellen Lernen zu verbessern, indem der Hy- pothesenraum auf verteilten Recheneinheiten breiter durchsucht wird. Dabei spielt eine große Rolle, dass parallel möglichst unterschiedliche Regionen des Raums durchsucht werden und so kritische Strukturen, wie beispielsweise die oben genannten lokalen Op- tima, umgangen werden können. In bisherigen Arbeiten zu dem Thema wurden dabei vor allem Verfahren erforscht, die entweder keine Kommunikation zwischen den Rechen- einheiten erlauben und den Hypothesenraum vor der Ausführung partitionieren, oder Distanzmaße für die Modelle verwenden, um diese explizit und mit ausgiebiger Kommu- nikation auseinanderzuhalten. In der vorliegenden Arbeit wird mit dem Bucket-Selektor ein Widening-Verfahren vorgestellt, welches mit relativ geringer Kommunikation, aber ohne Berechnung von Distanzen zwischen den Modellen, ein breites Durchlaufen des Hypothesenraums ermöglicht und damit qualitativ bessere Modelle findet als andere Verfahren. Besonders effizient kann diese Methode auf MapReduce-Systemen ausgeführt werden. Am Beispiel von zwei Problemen, dem hierarchischen agglomerativen Cluste- ring und der Join-Order-Optimierung, wird gezeigt, dass der Bucket-Selektor schneller bessere Ergebnisse erzielt als andere Methoden.</dcterms:abstract> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dc:contributor>Fillbrunn, Alexander</dc:contributor> <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/46160/3/Fillbrunn_2-1jg2009qsp3hw8.pdf"/> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-06-27T10:52:45Z</dc:date> <dcterms:issued>2019</dcterms:issued> <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/> <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/46160"/> <foaf:homepage rdf:resource="http://localhost:8080/"/> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/> <dcterms:title>Effektives Widening mit Hashbasierter Partitionierung des Hypothesenraums</dcterms:title> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-06-27T10:52:45Z</dcterms:available> <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/46160/3/Fillbrunn_2-1jg2009qsp3hw8.pdf"/> <dc:language>deu</dc:language> </rdf:Description> </rdf:RDF>