Turing Meets Machine Learning: Uncomputability of Zero-Error Classifiers

Research output: Contribution to book/conference proceedings/anthology/reportConference contributionContributedpeer-review

Contributors

Abstract

In almost all areas of information technology, the importance of automated decision-making based on intelligent algorithms has been increasing steadily within recent years. Since many of the envisioned near-future applications of these algorithms involve critical infrastructure or sensitive human goods, a sound theoretical basis for integrity assessment is required, if for no other reason than the legal accountability of system operators. This article aims to contribute to the understanding of integrity of automated decision-making under the aspect of fundamental mathematical models for computing hardware. To this end, we apply the theory of Turing machines to the problem of separating the support sets of smooth functions, which provides a simple yet mathematically rigorous framework for support-vector machines on digital computers. Further, we investigate characteristic quantities and objects, such as the distance between two separated support sets, or separating hyperplanes themselves, with regards to their computability properties, and provide non-technical interpretations of our findings in the context of machine learning and technological trustworthiness.

Details

Original languageEnglish
Title of host publication2023 62nd IEEE Conference on Decision and Control, CDC 2023
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages8559-8566
Number of pages8
ISBN (electronic)9798350301243
Publication statusPublished - 2023
Peer-reviewedYes

Publication series

SeriesProceedings of the IEEE Conference on Decision and Control
ISSN0743-1546

Conference

Title62nd IEEE Conference on Decision and Control, CDC 2023
Duration13 - 15 December 2023
CitySingapore
CountrySingapore