Effektives Widening mit Hashbasierter Partitionierung des Hypothesenraums

Lade...
Vorschaubild
Dateien
Fillbrunn_2-1jg2009qsp3hw8.pdf
Fillbrunn_2-1jg2009qsp3hw8.pdfGröße: 3.51 MBDownloads: 360
Datum
2019
Herausgeber:innen
Kontakt
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
DOI (zitierfähiger Link)
ArXiv-ID
Internationale Patentnummer
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Open Access Green
Core Facility der Universität Konstanz
Gesperrt bis
Titel in einer weiteren Sprache
Forschungsvorhaben
Organisationseinheiten
Zeitschriftenheft
Publikationstyp
Dissertation
Publikationsstatus
Published
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)
004 Informatik
Schlagwörter
Widening, Hypothesenraum, Hierarchisches Clustering, Join Order Optimization
Konferenz
Rezension
undefined / . - undefined, undefined
Zitieren
ISO 690FILLBRUNN, Alexander, 2019. Effektives Widening mit Hashbasierter Partitionierung des Hypothesenraums [Dissertation]. Konstanz: University of Konstanz
BibTex
@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>
Interner Vermerk
xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter
Kontakt
URL der Originalveröffentl.
Prüfdatum der URL
Prüfungsdatum der Dissertation
June 13, 2019
Hochschulschriftenvermerk
Konstanz, Univ., Diss., 2019
Finanzierungsart
Kommentar zur Publikation
Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Ja
Begutachtet
Diese Publikation teilen