home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / ai / neuraln / 3284 < prev    next >
Encoding:
Text File  |  1992-08-22  |  1.6 KB  |  39 lines
  1. Newsgroups: comp.ai.neural-nets
  2. Path: sparky!uunet!decwrl!access.usask.ca!kakwa.ucs.ualberta.ca!alberta!arms
  3. From: arms@cs.UAlberta.CA (Bill Armstrong)
  4. Subject: Re: Network Inversion
  5. Message-ID: <arms.714522787@spedden>
  6. Sender: news@cs.UAlberta.CA (News Administrator)
  7. Nntp-Posting-Host: spedden.cs.ualberta.ca
  8. Organization: University of Alberta, Edmonton, Canada
  9. References: <BtCqHo.AtH.1@cs.cmu.edu>
  10. Date: Sat, 22 Aug 1992 22:33:07 GMT
  11. Lines: 26
  12.  
  13. tjochem+@CS.CMU.EDU (Todd Jochem) writes:
  14.  
  15. >I'm looking for references to network inversion papers. The basic idea
  16. >I'm interested in is presenting the network's output with a signal and
  17. >by back-propagating this signal though the layer(s), recreating an input
  18. >which could have created the applied output signal.
  19.  
  20. This is intractable for a general multi-layer perceptron.
  21.  
  22. Proof: We have to show it for the special case of ALNs, which are
  23. trees of nodes realizing AND, OR, LEFT and RIGHT functions, with
  24. leaves connected to input bits and complements.  The same input bit or
  25. complement may be sent to many leaves.  It will be enough to show it
  26. for a two-layer tree, with ORs feeding into an AND.  Back-propagating
  27. a 1 signal is just CNF-satisfiability, and is NP-complete.
  28.  
  29. Comment: the difficulty arises because back-propagating signals often
  30. converge at the same node, either at the inputs (ALNs) or in hidden
  31. layers (MLPs), and they are likely to have contradictory values when
  32. they do.
  33.  
  34. --
  35. ***************************************************
  36. Prof. William W. Armstrong, Computing Science Dept.
  37. University of Alberta; Edmonton, Alberta, Canada T6G 2H1
  38. arms@cs.ualberta.ca Tel(403)492 2374 FAX 492 1071
  39.