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.
