Bucket Selection : A Model-Independent Diverse Selection Strategy for Widening

Fillbrunn, Alexander; Wörteler, Leonard; Grossniklaus, Michael; Berthold, Michael R.

Bucket Selection : A Model-Independent Diverse Selection Strategy for Widening

Dateien

Fillbrunn_2-3rvszn8syv2l7.pdfGröße: 210.02 KBDownloads: 421

Datum

2017

Publikationstyp

Beitrag zu einem Konferenzband

Publikationsstatus

Published

Erschienen in

ADAMS, Niall, ed., Allan TUCKER, ed., David WESTON, ed.. Advances in Intelligent Data Analysis XVI Proceedings. Cham: Springer, 2017, pp. 87-98. Lecture Notes in Computer Science. 10584. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-319-68764-3. Available under: doi: 10.1007/978-3-319-68765-0_8

Zusammenfassung

When using a greedy algorithm for finding a model, as is the case in many data mining algorithms, there is a risk of getting caught in local extrema, i.e., suboptimal solutions. Widening is a technique for enhancing greedy algorithms by using parallel resources to broaden the search in the model space. The most important component of widening is the selector, a function that chooses the next models to refine. This selector ideally enforces diversity within the selected set of models in order to ensure that parallel workers explore sufficiently different parts of the model space and do not end up mimicking a simple beam search. Previous publications have shown that this works well for problems with a suitable distance measure for the models, but if no such measure is available, applying widening is challenging. In addition these approaches require extensive, sequential computations for diverse subset selection, making the entire process much slower than the original greedy algorithm. In this paper we propose the bucket selector, a model-independent randomized selection strategy. We find that (a) the bucket selector is a lot faster and not significantly worse when a diversity measure exists and (b) it performs better than existing selection strategies in cases without a diversity measure.

Fachgebiet (DDC)

004 Informatik

Konferenz

Advances in Intelligent Data Analysis XVI : IDA 2016, 26. Okt. 2017 - 28. Okt. 2017, London, UK

Zitieren

ISO 690

FILLBRUNN, Alexander, Leonard WÖRTELER, Michael GROSSNIKLAUS, Michael R. BERTHOLD, 2017. Bucket Selection : A Model-Independent Diverse Selection Strategy for Widening. Advances in Intelligent Data Analysis XVI : IDA 2016. London, UK, 26. Okt. 2017 - 28. Okt. 2017. In: ADAMS, Niall, ed., Allan TUCKER, ed., David WESTON, ed.. Advances in Intelligent Data Analysis XVI Proceedings. Cham: Springer, 2017, pp. 87-98. Lecture Notes in Computer Science. 10584. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-319-68764-3. Available under: doi: 10.1007/978-3-319-68765-0_8

BibTex

@inproceedings{Fillbrunn2017-10-04Bucke-41134,
  year={2017},
  doi={10.1007/978-3-319-68765-0_8},
  title={Bucket Selection : A Model-Independent Diverse Selection Strategy for Widening},
  number={10584},
  isbn={978-3-319-68764-3},
  issn={0302-9743},
  publisher={Springer},
  address={Cham},
  series={Lecture Notes in Computer Science},
  booktitle={Advances in Intelligent Data Analysis XVI Proceedings},
  pages={87--98},
  editor={Adams, Niall and Tucker, Allan and Weston, David},
  author={Fillbrunn, Alexander and Wörteler, Leonard and Grossniklaus, Michael and Berthold, Michael R.}
}

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/41134">
    <dc:creator>Berthold, Michael R.</dc:creator>
    <dc:creator>Fillbrunn, Alexander</dc:creator>
    <dc:creator>Wörteler, Leonard</dc:creator>
    <dcterms:abstract xml:lang="eng">When using a greedy algorithm for finding a model, as is the case in many data mining algorithms, there is a risk of getting caught in local extrema, i.e., suboptimal solutions. Widening is a technique for enhancing greedy algorithms by using parallel resources to broaden the search in the model space. The most important component of widening is the selector, a function that chooses the next models to refine. This selector ideally enforces diversity within the selected set of models in order to ensure that parallel workers explore sufficiently different parts of the model space and do not end up mimicking a simple beam search. Previous publications have shown that this works well for problems with a suitable distance measure for the models, but if no such measure is available, applying widening is challenging. In addition these approaches require extensive, sequential computations for diverse subset selection, making the entire process much slower than the original greedy algorithm. In this paper we propose the bucket selector, a model-independent randomized selection strategy. We find that (a) the bucket selector is a lot faster and not significantly worse when a diversity measure exists and (b) it performs better than existing selection strategies in cases without a diversity measure.</dcterms:abstract>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2018-01-24T14:28:08Z</dc:date>
    <dc:contributor>Fillbrunn, Alexander</dc:contributor>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/41134/3/Fillbrunn_2-3rvszn8syv2l7.pdf"/>
    <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dcterms:issued>2017-10-04</dcterms:issued>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2018-01-24T14:28:08Z</dcterms:available>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:creator>Grossniklaus, Michael</dc:creator>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/41134"/>
    <dc:contributor>Berthold, Michael R.</dc:contributor>
    <dc:rights>terms-of-use</dc:rights>
    <dc:contributor>Wörteler, Leonard</dc:contributor>
    <dc:language>eng</dc:language>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/41134/3/Fillbrunn_2-3rvszn8syv2l7.pdf"/>
    <dc:contributor>Grossniklaus, Michael</dc:contributor>
    <dcterms:title>Bucket Selection : A Model-Independent Diverse Selection Strategy for Widening</dcterms:title>
  </rdf:Description>
</rdf:RDF>

Universitätsbibliographie

Ja