<div class="csl-bib-body">
<div class="csl-entry">Eiben, E., Ganian, R., Kanj, I., Ordyniak, S., & Szeider, S. (2023). The Computational Complexity of Concise Hypersphere Classification. In A. Krause, E. Brunskill, K. Cho, B. Engelhardt, S. Sabato, & J. Scarlett (Eds.), <i>Proceedings of the 40th International Conference on Machine Learning</i> (pp. 9060–9070). http://hdl.handle.net/20.500.12708/188983</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/188983
-
dc.description.abstract
Hypersphere classification is a classical and foundational method that can provide easy-to-process explanations for the classification of real-valued as well as binary data. However, obtaining an (ideally concise) explanation via hypersphere classification is much more difficult when dealing with binary data as opposed to real-valued data. In this paper, we perform the first complexity-theoretic study of the hypersphere classification problem for binary data. We use the fine-grained parameterized complexity paradigm to analyze the impact of structural properties that may be present in the input data as well as potential conciseness constraints. Our results include not only stronger lower bounds but also a number of new fixed-parameter algorithms for hypersphere classification of binary data, which can find an exact and concise explanation when one exists.
en
dc.language.iso
en
-
dc.relation.ispartofseries
Proceedings of Machine Learning Research
-
dc.subject
Computational Complexity
en
dc.subject
Concise Hypersphere Classification
en
dc.title
The Computational Complexity of Concise Hypersphere Classification
en
dc.type
Inproceedings
en
dc.type
Konferenzbeitrag
de
dc.contributor.affiliation
Royal Holloway University of London, United Kingdom of Great Britain and Northern Ireland (the)
-
dc.contributor.affiliation
DePaul University, United States of America (the)
-
dc.contributor.editoraffiliation
Ben-Gurion University of the Negev, Israel
-
dc.description.startpage
9060
-
dc.description.endpage
9070
-
dc.type.category
Full-Paper Contribution
-
tuw.booktitle
Proceedings of the 40th International Conference on Machine Learning
-
tuw.container.volume
202
-
tuw.peerreviewed
true
-
tuw.researchTopic.id
I1
-
tuw.researchTopic.name
Logic and Computation
-
tuw.researchTopic.value
100
-
tuw.linking
https://proceedings.mlr.press/v202/eiben23a.html
-
tuw.publication.orgunit
E192 - Institut für Logic and Computation
-
tuw.publication.orgunit
E192-01 - Forschungsbereich Algorithms and Complexity
-
dc.description.numberOfPages
11
-
tuw.editor.orcid
0000-0002-3971-7127
-
tuw.editor.orcid
0000-0002-6139-7334
-
tuw.editor.orcid
0000-0002-7975-0044
-
tuw.editor.orcid
0000-0003-1403-9160
-
tuw.event.name
40th International Conference on Machine Learning
en
tuw.event.startdate
23-07-2023
-
tuw.event.enddate
29-07-2023
-
tuw.event.online
On Site
-
tuw.event.type
Event for scientific audience
-
tuw.event.place
Honolulu
-
tuw.event.country
US
-
tuw.event.presenter
Eiben, Eduard
-
wb.sciencebranch
Informatik
-
wb.sciencebranch
Mathematik
-
wb.sciencebranch.oefos
1020
-
wb.sciencebranch.oefos
1010
-
wb.sciencebranch.value
80
-
wb.sciencebranch.value
20
-
item.openairecristype
http://purl.org/coar/resource_type/c_5794
-
item.languageiso639-1
en
-
item.fulltext
no Fulltext
-
item.grantfulltext
none
-
item.openairetype
conference paper
-
item.cerifentitytype
Publications
-
crisitem.author.dept
E186 - Institut für Computergraphik und Algorithmen
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity
-
crisitem.author.dept
DePaul University
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity
