home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / CLIPPER / MISC / AIE9003.ZIP / NET.DOC < prev    next >
Encoding:
Text File  |  1989-12-29  |  9.7 KB  |  273 lines
  1.  
  2.  
  3.              BAYSEAN OR OF ANDS NETWORK
  4.  
  5.              (C) Copyright 1989 by Instant Recall
  6.                  All rights reserved.
  7.  
  8.                   Rodger Knaus
  9.                   Instant Recall
  10.                   P.O. Box 30134
  11.                   Bethesda, Md. 20814
  12.                   (301) 530-0898
  13.  
  14. PURPOSE
  15.  
  16. This is a neural network which is designed to find and tune expert
  17. system rules.  It can be used when
  18.  
  19. * The user knows what kinds of facts are relevant to a decision,
  20.   but not how the facts combine with each other in producing
  21.   particular decision results.
  22.  
  23. * The user knows some of the rules that combine facts, and wants
  24.   to test and refine these, and also discover other rules.
  25.  
  26. * The user has guessed at confidence factors in rules and wants
  27.   to tune them.
  28.  
  29. OVERVIEW OF NETWORK
  30.  
  31. The network accepts inputs which are logical propositions and their
  32. negatives, with probability truth values.  The logical propositions
  33. do not at this time contain variables.
  34.  
  35. The 2nd. layer of the network contains AND nodes of input layer nodes.
  36. Each 2nd. layer node is an AND of a different combination of 1st. layer
  37. nodes.  The edge to an AND node is 0 if the input to the edge is not
  38. in the AND at the output.  The edge is 1 if the input to the edge
  39. is in the AND.  The edge has an intermediate value if the input has
  40. some effect on the AND, but not enough to make it completely false
  41. if the input is false.  The weights for AND nodes are computed using
  42. the Baysean formula, taking the product of input activations.
  43. Each input is raised to the power of the edge weight from it to the
  44. output and node.  This produces a weighted product similar to the
  45. usual weighted sum.  The assumption of statistical independence is
  46. not strictly satisfied, but is often approximated, because the
  47. knowledge engineer finds independent propositions solve more
  48. different problems than highly correlated ones.
  49.  
  50. The 3rd and final layer is a layer of ORs of the AND nodes.  The
  51. weights are similar to those to the AND nodes.  However, the
  52. activation of an OR is computed using the Bayean formulas for
  53. AND and NOT, plus DeMorgan's Law.
  54.  
  55. The delta rule is applied to the OR weights.  The AND weights
  56. are not changed.  This follows the approach of Pao's functional-link
  57. nets.  The ANDs form a basis of all the possible logical functions.
  58. They are in effect an enriched set of inputs for a simple 1-layer
  59. trainable network.
  60.  
  61. Any propositional function of the inputs can be represented as
  62. an OR of ANDs of inputs and their negatives.  Therefore there
  63. exists a network that solves any problem of computing the
  64. logical formula that has a given behavior.
  65.  
  66. The problem of finding this formula can also be done algebraically.
  67. However, the algebra becomes unwieldy with large numbers of inputs.
  68. Furthermore, bad data will produce a false formula in the algebraic
  69. approach, but will generally just introduce a small error into the
  70. network coefficients.
  71.  
  72. USING THE NETWORK TO IMPROVE EXPERT SYSTEM RULES
  73.  
  74. Expert system rules can be readily encoded into this network.
  75. The steps are:
  76.  
  77. 1.  Write the rules in disjuctive normal form.
  78. 2.  Create an input node for each proposition in a rule body.
  79. 3.  Create an output node for each proposition in a rule conclusion.
  80. 4.  Set the weights according to the definitions above.
  81.  
  82. Then run data with known outputs through the network.  This trains
  83. the weights.
  84.  
  85. To get expert system rules out of the network, do the following:
  86.  
  87. 1.  Set edge weights near 0 to 0 and weights near 1 to 1.
  88. 2.  Use the weight definitions above to convert each AND and OR
  89.     node to a propositional function.
  90.  
  91.  
  92.  
  93. USING THE NETWORK FOR PARAMETRIC PROBLEMS
  94.  
  95. Statements containing variables can be broken up into a series of
  96. propositions without variables.  For example, we can change
  97.  
  98. computer_budget( X )
  99.  
  100. into
  101.  
  102. Computer budget is below $1000.
  103. Computer budget is between $1000 and $2000.
  104. Computer budget is between $2000 and $3000.
  105. Computer budget is between $3000 and $4000.
  106. Computer budget is above $4000.
  107.  
  108. This process is like what happens in the ear, where a neuron is fired
  109. when and only when the ear receives sound of a particular frequency,
  110. and there is a separate neuron for each frequency.
  111.  
  112. INSTALLING THE PROGRAM
  113.  
  114. 1.  Copy the program to the subdirectory where you want to run it.
  115.  
  116. 2.  Uncomprressing the archive file :  If you get the program as a
  117.     single file BNET.EXE, then type
  118.  
  119.     >bnet
  120.  
  121.     to DOS.
  122.  
  123. RUNNING THE PROGRAM
  124.  
  125. You should have the following files in your current subdirectory:
  126.  
  127. NET.EXE   : network executable program
  128. NET.IDB   : network prolog internal database
  129. NET.CFG   : network configuration file
  130.  
  131. The other files listed below are for study purposes, but not needed
  132. for running the program:
  133.  
  134. NET.DOC   : network documentation
  135. EXEC.ARI  : network source code
  136.  
  137. Here is a sample run of BNET, with comments :
  138.  
  139. ----------------------------------------------
  140.  
  141.            % Run of BNET
  142.  
  143. >net  <return>               % DOS command to run BNET
  144.  
  145. name of net >> xor.ari       % name of file containing network definition
  146. number of cycles >> 5        % number of input sets to train net on
  147.  
  148. Errors at time 0 : 9 -1.0    % net reports its performance
  149. Errors at time 1 : 9 -1.0
  150. Errors at time 2 : 9 0.0
  151. Errors at time 3 : 9 0.0
  152. Errors at time 4 : 9 -0.6
  153.  
  154. save file >> save1.ari       % file to save final network configuration in
  155.  
  156.  
  157. ----------------------------------------------
  158.  
  159. Note the following:
  160.  
  161. * the "name of net" should be a file containing a network description,
  162.   as defined in this document.
  163.  
  164. * the "save file" should be the file where you want to save the network
  165.   in the state after its run.  You can read it back in on another run.
  166.  
  167. * We recommend using the "ari" extension for network definitions.
  168.  
  169. * We have provided a sample network definition in xor.ari, for the
  170.   exclusive or.
  171.  
  172. LOG FILE
  173.  
  174. Everything that appears on your screen during a run of net is also
  175. written to a log file called log.log.
  176.  
  177. TRACING NET BEHAVIOR
  178.  
  179. The file net.cfg contains, among other things, a set of trace
  180. switches that let you see the net behavior in more detail.
  181. Here are the list of trace switches:
  182.  
  183.  
  184. % and_learn_trace.            % learning and nodes
  185. % and_trace .                % and activations
  186.   cycle_trace .                % results after each cycle
  187. % net_trace .                % general
  188. % not_trace .                % NOT nodes
  189. % or_trace .                 % or activations
  190. % or_learn_trace.            % learning or nodes
  191.  
  192. When a % appears before the flag on in the left col., that trace
  193. is turned off.  When there is no % in col. 1, as for cycle_trace,
  194. that trace is on.
  195.  
  196. CONTROLING NET BEHAVIOR
  197.  
  198. There are also a couple data items in NET.CFG that control the
  199. net behavior.  They are shown below:
  200.  
  201. learning_rate( 1.0 ).         % learning rate
  202. backprop_to_and_edges( off ). % switch -- on or off - on whether to change
  203.                               % and edges
  204.  
  205. learning_rate controls the speed of learning by the net.  It is a number
  206. between 0 and 1.  When 0, no learning occurs.  When 1, learning occurs
  207. according to  the Baysean OR formula form of the delta rule.  See the
  208. file NET.COL for more details on the learning formula.
  209.  
  210. backprop_to_and_edges is a switch with values off and on.  It controls
  211. whether errors are propogated back to the "and" level of the net.
  212. If so, the generalized delta rule is used to compute them, i.e.
  213. the credit for an error assigned to an interior neuron is the
  214. sum of errors made by neurons to which its activation is sent, weighted
  215. by the edge weight to each such neuron.  We recommend keeping this off,
  216. making the net behave like Pao's functional linked nets.
  217.  
  218. TROUBLESHOOTING
  219.  
  220. If NET does not run on your machine, here are some things to check:
  221.  
  222. 1.  AVAILABLE MEMORY: This program is written in Prolog, a relative
  223.     memory hog.  I do not know exactly how much memory it needs, but
  224.     it definitly runs when there are over 500K memory free.  If you
  225.     have less, because you are running with RAM-resident programs,
  226.     a lot of device drivers, etc.  remove these memory-consumers
  227.     and reboot to provide more free memory.
  228.  
  229. 2.  DOS 4.0 OR ABOVE:  If you are running with these versions of DOS,
  230.     you must include ANSII.SYS/K -- the "K" option on ANSII.SYS --
  231.     in your CONFIG.SYS fiile.  This resolves a conflict between the
  232.     Prolog and DOS keyboard handlers.  Put this in your config.sys
  233.     file and reboot.
  234.  
  235. NETWORK DESCRIPTIONS
  236.  
  237. A network description file should contain facts of the form:
  238.  
  239. input(  DATA_INSTANCE_KEY  , INPUT_NEURON_NUMBER, VALUE_OF_INPUT ).
  240. input(  DATA_INSTANCE_KEY  , OUTPUT_NEURON_NUMBER, DESIRED_VALUE_OF_OUTPUT ).
  241. neuron(   KIND  , NEURON_NUMBER, DESCRIPTION  ).
  242. state( edge,  KIND, INPUT_NEURON_NUMBER , OUTPUT_NEURON_NUMBER,
  243.            0, INITIAL_WEIGHT).
  244.  
  245.    where KIND is one of : input, and, or, not( INPUT_NEURON_NUMBER )
  246.  
  247. DESCRIPTION OF NETWORK:
  248.  
  249.   INPUTS : in [0 ,1 ]
  250.  
  251.   INPUT LAYER : inputs and their negatives, i.e. ( 1 - input) 's
  252.  
  253.   MIDDLE LAYER : various ands of inputs
  254.       activation( A AND B) = activation( A ) * activation(  B)
  255.  
  256.   OUTPUT LAYER : ors of middle layer nodes
  257.       activation( A OR B) = 1 - ( 1 - activation( A )) *
  258.                                 ( 1 -  activation(  B) )
  259.  
  260.   INITIALIZATION :
  261.      edges to and layer are initialized by:
  262.         wji = 0 if input or negative of input i is not in
  263.               the and represented by node j
  264.         wji = 1 if the input or negative of input i is in
  265.               the and represented by node j
  266.      edges to or layer are initialized as all 1s
  267.  
  268.   LEARNING :
  269.      edges to or layer are updated by delta rule.
  270.      edges to and layer are not changed.
  271.  
  272.                  - eof -
  273.