Medical
Autopilot®

**Learning
with Space-Filling Curves**

While writing a neural network program in the 1990’s, the thought occurred to me
that space-filling curves (SFCs) might facilitate learning. As it happens, SFCs
are not a measure of similarity but rather a foundation. For simplicity, while
trying to work out the bugs and obtain an understanding how this might work, the
only measure we have tried so far is nearest neighbor. The idea is that since
some SFCs are one- to-one, on this side of infinity, the inputs of any output
can be generated and the output space is well defined.

Here we
use the Hilbert SFC because it is one-to-one short of infinity and associated
with gray code. In fact, an n-dimensional Hilbert curve with binary coordinates
is equivalent to gray code and the simplest model to understand what is
happening with a space-filling curve.

The
concept is to fill a space with a line such that each point on the line has a
limit in that space. In simple terms it amounts to bending a line until the
entire space is filled. Consider an n-space with binary dimensions. The inputs
are gray coordinates (vGray) while the output is the Boolean length (vBool).

For
binary coordinates, vGray has n! orderings each representing a different path
along the “edge” of the n-space and diagonals are not allowed. In addition,
nearest neighbor similarity between two sets of gray coordinates is equivalent
to XOR of those coordinates counting the number of “1”s. This can be written as
XOR(a, b) = similarity.

Since
vBool has length 2^n it is necessary to use an iterative limit to define where
one classification ends and another begins. Whereas support vectors place the
boundaries in an n-space, SFCs place the boundaries in a single dimension.

For an
n-space with binary coordinates, the origin vGrayOrigin is all zeros. Every
vGrayNext with single “1” has the similarity of XOR(vGrayOrigin, vGrayNext) = 1;
There are n possible vGrayNext, since n!/(1!(n-1)!)
= n.
If vGrayNext has two coordinates which are “1” there are n!/(2!(n-2)!) possible
combinations. The first is iteration
divides vBool into n intervals. The second iteration divides vBool into
n!/(2!(n-2)!) intervals. The boundaries
of the intervals of any given iteration have the same similarity.

If there
are x iterations, (n!/((x-1)!(n-x-1)!) / (n!/x!(n-x)!)
= x(n-x) is less than n. Thus, each iteration
divides vBool into intervals and the next iteration over any one interval
divides that interval into less than n subsequent intervals. Further, all the
similarities between the boundaries are greater or less than the boundary
similarity. This is a function which limits the XOR similarities and approaches
any point in vBool in at most n iterations.

Another
step is the determination of the possible classes between any two points in
vBool. The two points may have coordinates in common starting from the left.
Those are inserted for the left coordinates of each training example while also
flipping the training coordinates as necessary to keep within the two point
interval. After checking similarities, this gives all possible classes within
that interval. This along with the iterative limits provides a one-to-one map
from vGray to vBool such that vBool has classification intervals.

The
C++ code will be expanded and improve with time. It may be freely used, distributed and modified
at your discretion.

While there are no intentional errors, there are no implicit or explicit
guarantees or assumptions this code has any value whatsoever.

Binary Number to Gray Code and vise versa

Binary Number as a length to Gray Code Coordinates of M dimensions and N Bits per dimension. This code needs revision or replacement as it is difficulty to follow.

Gray Code Measure of Similarity (XOR) This provides a one-to-one map between the inputs and outputs of the classification system.

Get Least Upper Bound Given Total Bits and the target Similarity This is for the limit function.

My office is:

Muskegon Surgical Associates

My email address may be constructed by using the first letter from my first
name,
middle initial and the four letters of my last name "at" comcast.net

James J. Rice

Site posted
11/01/1999

Last modified 05/18/2018

Completion Date 01/01/2020