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.