Kali  

Oct 2012 Notes

Kali uses state automata functioning on finite sets of temporal sequences to model the synapses of neurons processing information. Specifically, Kali uses the parallel string matching algorithm of Aho-Corasick to simulate the communication filter or method between groups of neurons. The components of this algorithm may be regarded as a string prefix identifier called a trie or prefix-tree. That is, a set of prefix-trees constructed for parallel string matching using a set of push-down stacks and fail-states is functionally what the Aho-Corasick algorithm does.

Connections

  A connection is the path of transition between two states. 

      x_k+1 = W(x_k|x_k+1) x_k


      Temporal Connection Diagram


            U1        x_1 = U(x_0|x_1) x_0
          .---> x1
        /
       /   U2         x_2 = U(x_0|x_1) x_0
      x0 -----> x2
      | \
      |  \  U3        x_3 = U(x_0|x_3) x_0
      |   `---> x3
      |
      |    U4         x_4 = U(x_0|x_4) x_0
       `------> x4
                       ...


  The trellis of the temporal connections, U, can be computed from the
  frequency of occurrance of the x_k's relative to each other in the
  compilation phase.
  
            U1
      x0 -----> x1             U4
        \                   .-----> x4
         \  U2      U3     /
          `---> x2 ----> x3 
                           \   U5
                            `-----> x5



Parallel Execution of Cell-Connections

  Let M_k define a state machine.  We can execute in parallel the
  running of multiple state machines by passing messages between M_k's.
  (state automata: Cell -> State, Connection -> Transition)

  (time)  t0-->t1-->t2-->...

    M_0 (x00->x02->x03->...)
    M_1 (x10->x11->x15->...)
    M_2 (x20->x23->x26->...)
    ...

    X = M * x 

      Time   ---->
      States  x_0 x_1 ... x_(n-1)  N states
               |    |        |
               v    v        v
Observations  y_0 y_1 ... Y_(n-1)  Y (y_0, ... y_n-1)

               4    5   ...

        
               P(x_5 | y_0:4) = ?

              x_k+1 = x+k + e(k+1|k)
       e(k+1|k) = ETA w(k+1|k) u(k)  ~=  1/ETA**2



Creating a Trellis

Creating connecting paths in a trellis.

   sequence of cell traversals
   sequence goes through layers
  
     start  ----------------->                end (i-th pattern) 
   
     layer 0 (root layer)
      _       _       _       _               _
     |_| --> |L| --> |_| --> |_| --> ... --> |_|   

         layer 1
          _       _       _       _               _
         |_| --> |L| --> |_| --> |_| --> ... --> |_|   

             layer 2
              _       _       _       _               _
             |_| --> |L| --> |_| --> |_| --> ... --> |_|   

                 ...

     layer 0
         layer 1
             layer 2
                 layer 3
 
     0-> 1-> 2-> 3

    |---------------------------------------------->
                       time, t         


The length of the sequence is a function of the fidelity of the signal.
Assume that the length of a sequence is equal to the duration of a
consonant or vowel demarcated pause in speech.  This is about 200
milli-second.  So for a fidelity of about 500 Hz, the binary sample
size would need span to be about 200 milli-sec or (500 * 0.2 cycles)
100 data points.


Rules

Rules may also be associated with slots or sets of slots[1]. If an if-added
rule is associated with a slot r, or with a set of which r is a member,
then it is applied whenever a value is added to the r slot of any frame
(if-needed rules associated with slots and sets of slots are similar).

For example, one might want to put the slot less in the set of partial
orders, and thus inherit rules, associated with the set of partial orders,
for transitivity, reflexivity, and antisymmetry. 

By associating rules with sets of individuals, or with slots representing
specific relations, we are imposing a semantically-motivated organization
on the knowledge-base, which clarifies the structure of its knowledge.

We are also limiting access to those rules, thereby reducing the number
of times their antecedents must be tested, and hence gaining efficiency. 

tell  path &key  :retrieve  :eval  :collect  :comment 
ask   path &key  :retrieve  :eval  :collect  :comment 

The functions assert or query a given access path in the context of the
rule set, RS.  These operations may branch on multiple bindings while
following the path.  If the keyword :retrieve is t, only facts explicitly
stored in the RS are retrieved, and no backward-chaining rules are invoked.
If no sets of bindings are found, the operation fails and nil is returned. 

1.  Slots - define the relations that may hold among those objects. 

2.  Rules - define the forward-and backward-chaining inferences that
can take place using those relations. 


The set contains at least the subsets rules, objects, and slots.  The
set booleans contains exactly the two elements true and false.

Several of the sets in the hierarchy are also explicitly declared as
individual elements of the set sets, but those individuals are not
completely enumerated. 


Slots Represent Relations

A slot represents a relation among cells.  The domain of an n-ary
relation is the cross-product of n sets. 

The first argument is the name of the relation. By convention, the
name P of a relation P (a, b)  is chosen to fit the template,
The P of a is b.. 

The cardinality keyword specifies how many distinct values can
consistently be in a slot.
 

Rules Specify Inferences

The rules determine which inferences will take place.   Rules are
associated with sets.

Relatively little is known about controlling mixed forward-and
backward-chaining inference, so many systems are restricted to only
one direction.

More complex rules show how to infer some relations from others. 
Note that it isn't correct to say that one relation is defined in terms
of more primitive relations. Rather, there is a network of inferences
that link relations together.



Sequence Language

   (A,B,...; S) - the sequence S is defined by A, B, C, ....
   (A,B,...: S) - the sequences A, B, C, ... yields S.

   ";" stops a sequence definition.  ":" stops sequence definition
   and says the next element is the next state to fire.
   
A neuron synapse depends on a previous sequence of neurons firing.


      A  o -
            \ G
      B  o --o
            / \
      C  o -   \
                o -->  (A,B,C: G, F: Q)
               / Q
            F o


If (A,B,C; F) fires, then Q fires.  Conversely, if Q fires, then
(A,B,C; F), or another sequence occurring with an uncertainty
or probability, p_i, had previously fired.



     A o -
          \
           o - C     (A,B: C)
          /
     B o -

     A o -
          \ 
           o -
          /   \
     B o -     o - G    (A,B; F: G) -> (D, F: G) => (A,B: D)
              /
          F o-


  In Kali, sequences are the set of ascii characters, representing signals
  from input receptors, modified state transitions, and output signals.
  A sequence S, {s_0, s_1, s_2, ..., s_N-1}, is a set of numbers
  representing a signal.  The sequence P, {p_0, p_1, p_2, ..., p_N-1},
  represents the pattern we want to extract from the sequence S.

  S = {s_0, s_1, ..., (s_i, s_i+1, ..., s_N-1}
                      |<-- sub-sequence -->|
                          word or atom

  The smallest sequence with a unique hash value is an atom.  The
  sequence maybe handled as a recursive structure.  Elements in a
  sequence maybe composed or decomposed from the basic atoms of the
  sequence; like running a compression or decompression algorithm
  on the sequence.

  The cell are linked to related cells which contain associated
  attributes.

  A cell is a representation of:

(1) Contextual pathways model
    There are two types of context: associative and temporal.
      (a) The context in which a sequence is
          processed is associative, AC.
      (b) Time is an attribute of the temporal
          context or constraint, TC.

(2) Gates/Switches (nodes in a trellis)


Architecture

Processing cycle, PARA:
pattern -> association -> resolution -> action

  The pattern->association phase occurs when the brain tries to overlay the
  new input pattern on an existing template, archetype pattern.

  In the temporal sequence processor, a node or cell, the object at the
  lowest level of organization, acts as a gate directing the propagation
  pathways of signals.  Hebbian training works within the context of
  building signal transmission pathways.

  The cell soma, is the signal processor (the gate or switch), and the axon
  is the signal transmission line. 

  The pattern->association phase of the PARA process is constrained by
  the context the input is stored and retrieved by.  The "association"
  or selection of a pattern is determined by it's contextual setting.
  Context is built by creating a word list in which each item is
  correlated together, and extrapolated using the contextual environment.

             ________
     -----> | Search | ------>
       ^    |________|    | 
       |     _________    v
       '----| Context |---'
            |__Path___|


  State propagation

    \
     \
    -- ---
     /
    /


  ---> signal propagation (traverses trellis from top down)
  Each pattern token is processed in layers.  For example, if the
  sequence is s = {001, 002, 003}, the token 001 is processed in
  the first layer (layer 0), the token 002 is processed in the second
  layer (layer 1), and the token 003 is processed in the third layer
  (layer 2), etc.

  layer 0
     |
     `--> layer 1 
         |
         `--> layer 2
            |
	    `--> layer 3


    |------------------------------------------------------>
                           time, t



Perception

       |
       |            g
       |            i
   ^   |            g     l
   |   |   e  g     g  s  i
   |   |   h  o  s  a  i  a
   x   |   t  d  i  w  h  t
       |
       |      *     *     *
       |   g0 g1 g2 g3 g4 g5
       |   ------|--------->
       *-----------------------------------
           t_0      t_3 
              t_1      t_4        t -->
                 t_2      t_5

           <--  delta t  -->


 Transition function: U (x_i+1; x_i)   wag (dog, tail)
                      x_i+1 = U (x_i)  dog = wag (tail)


Software Code
This software has been tested with Gauche, Bigloo, Chicken and Guile.


;; -*- scheme -*-
;; trie.scm - prefix tree routine

;; trie node

;;  0  key
;;  1  attributes       key    / right
;;  2  left                ---o
;;  3  right                   \ left

;; def .=. macro defun; set .=. macro define

(cond-expand
 ((or gauche bigloo)
  (load "struct.scm")
  )
 (chicken
  (include "struct.scm")
  )
 (guile
  (load-from-path "struct.scm")
  )
 )


(def-struct Trie (key
                  attr
                  left
                  right))


;; add the string to the trie

(def insert-trie (trie str)
   (when (> (string-length str) 0)
      (let ([c (string-ref str 0)])
         (when (null? trie)
            (set! trie (make-Trie nil nil nil nil))   ; create a new trie
            (Trie-key-set! trie c))
         (cond ((char<? c (Trie-key trie))       ;
                (Trie-left-set! trie (insert-trie (Trie-left trie) str)))
               ((char>? c (Trie-key trie))
                (Trie-right-set! trie (insert-trie (Trie-right trie) str)))
               (else
                (insert-trie trie (substring str 1 (string-length str)))))))
   trie)

;; return #t if the string exists in the trie, #f if it does not

(def search-trie (trie str)
   (call-with-current-continuation
    (lambda (return)
       (if (> (string-length str) 0)
           (let ([c (string-ref str 0)])
              (if (null? trie) (return #f))               ; no match
              (cond ((char<? c (Trie-key trie))
                     (search-trie (Trie-left trie) str))
                    ((char>? c (Trie-key trie))
                     (search-trie (Trie-right trie) str))
                    (else
                     (search-trie trie
                                  (substring str 1 (string-length str))))))
           #t))))



(set A nil)     ; trie is nil
(set! A (insert-trie A "hellosaidtheraven"))
(print A)

(if (search-trie A "helLosAidtheRaven")
    (print "found it")  (print "did not find it"))
(if (search-trie A "hellosaidtheraven")
    (print "found it")  (print "did not find it"))
(if (search-trie A "hiliiotherebirdravenflying")
    (print "found it")  (print "did not find it"))
(exit)


;; The following code is developmental, untest
;; in the Aho-Corasick algorithm implementation.

;; The struct, Tree, contains a key (string), attributes or slot (values)
;; to the matching string, and list of branch nodes.  The use of
;; this tree structure is analogous to a frame structure used in
;; production systems.                

#|
Prefix Tree
 
                           - (k_i | t_0, ...)
                          /
root-node   (k_0 | t_0, t_1, t_2, ..., t_n-1)
                     \
                      `- (k_1 | t_0, t_1)
                                       \
                                        `- (k_m | t_0, t_1, ...)
 
key         k_i
branch      t_i
branches    (t_0, t_1, ..., t_n-1)
|#


(def-struct Tree (key
                  attrs
                  branches))


;; insert - Add a leaf (k/attrs) to an existing subtree node
;;          or create a new subtree node.  Each branch element
;;          is a subtree node.  Return subtree list, t (list).
;; k - key (leaf id)
;; a - leaf attributes (anything)
;; t - subtree node (branch (singular), eg. root subtree node)

(def tree-insert (k a t)
   (if (string-null? k) t
       (if (null? t) (make-Tree k a nil)
           (make-Tree (Tree-key t)
                      (Tree-attrs t)
                      (tree-insert k a (Tree-branches t))))))


;; search - Find a subtree node containing the reference key.
;;          Return the subtree node, t, if the key is found;
;;          else return false.
;; k - key (leaf id)
;; t - subtree node (branch (singular))

(def tree-search (k a t)
   (if (string-null? k) #f
       (if (null? (Tree-branches t)) #f
           (if (string=? k (Tree-key t)) t
               (tree-search k a (Tree-branches t))))))




I do my editing in an xterm (gnome-terminal) using GNU emacs.