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 |