What Neural Networks Are (Not) Good For?

Show simple item record

dc.contributor.author Calude, CS en
dc.contributor.author Heidari, S en
dc.contributor.author Sifakis, J en
dc.date.accessioned 2022-01-14T03:42:11Z
dc.date.available 2022-01-14T03:42:11Z
dc.date.issued 2021 en
dc.identifier.citation CDMTCS Research Reports CDMTCS-556 (2021) en
dc.identifier.issn 1178-3540 en
dc.identifier.uri https://hdl.handle.net/2292/58018
dc.description.abstract Perceptron Neural Networks (PNNs) are essential components of intelligent systems because they produce efficient solutions to problems of overwhelming complexity for conventional computing methods. There are lots of papers showing that PNNs can approximate a wide variety of functions, but comparatively very few discuss their limitations, the scope of this paper. To this aim we define two classes of Boolean functions – sensitive and robust –, and prove that an exponentially large set of sensitive functions are exponentially difficult to compute by multi-layer PNNs (hence incomputable by single-layer PNNs) and a comparatively large set of functions in the second one, but not all, are computable by single-layer PNNs. Finally we used polynomial threshold PNNs to compute all Boolean functions with quantum annealing and present in detail a QUBO computation on the D-Wave Advantage. These results confirm that the successes of PNNs, or lack of them, are in part determined by properties of the learned data sets and suggest that sensitive functions may not be (efficiently) computed by PNNs.
dc.publisher Department of Computer Science, The University of Auckland, New Zealand en
dc.relation.ispartofseries CDMTCS Research Report Series en
dc.rights Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher. en
dc.rights.uri https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm en
dc.source.uri https://www.cs.auckland.ac.nz/research/groups/CDMTCS/researchreports/index.php en
dc.title What Neural Networks Are (Not) Good For? en
dc.type Technical Report en
dc.subject.marsden Fields of Research en
dc.rights.holder Copyright: The author(s) en
dc.rights.accessrights http://purl.org/eprint/accessRights/OpenAccess en

Files in this item

Find Full text

This item appears in the following Collection(s)

Show simple item record


Search ResearchSpace