# Path anomoly detection using Grid Cells and Temporal Memory

I’m surprised that no one has ever tried grid cells as location encoders (like to the old GeoSpatial Encoder) for anomaly detection. So it became an experiment I ran for the final project for my ML course.

Here is a screen shot for your viewing pleasure. And letting me to explain things more clearly.

On the left you see a white and red circle revolving in a circle. That is the target. HTM will try to learn lt’s path and generate anomaly signals when even the path is altered.

On the right is an self explanatory window. It shows the input SDR of the current time step, what TemporalMemory predicts at the last time step, what has not been predicted, anomaly history, current anomaly score and a slider and threshold and display to show anomaly.

## Grid Cells

If you don’t know what gird cells are. Go watch HTMSchool Epsode 14. You have already watched? Awesome. Numenta’s view of Grid Cell module not as a hexagon but as a parallelogram is ingenious. It simplified the problem from some crazy hexagonal indexing into simple 2D geometry/algebra. Making encoding each module an O(1) process (assuming constant density). (I’m not certain. But the implementation used in HTM School, hex-gcm.js seems not have take advantage of this property. Thus the algorithmic complexity there is O(n), where n is the number of cells in a module)

I have also tried alternative forms of grid cells. Randomlly squashing/extending the x or y axis of each grid cell module, perform random transformation on the coordinate instead of rotating it, add a bias term to the coordinate etc…
Most of them failed, they underperform the grid cell modules purposed by Numenta. However, adding a bias term to shift the coordinates around seems to improve the performance a bit. But it might be random luck.

## The Test

To have a base line to compare. I compare how well anomaly detection works when the SDR is encoded using grid cells vs 2 ScalarEncoders encoding the X-Y coordinate of the circle.

The anomalies I test includes:

1. Path offset (to up/right/left/down) by 50 pixels
2. Path offset (to up/right/left/down) by 5 pixels
3. Rotation center moved from (50, 50) to (250, 250)
4. Rotation radius increased from 100 to 105
5. Reverse the rotation direction
6. Fix the circle to (50, 50)

And… Grid cells dominated ScalarEncoder. Some times ScalarEncoders can’t even detect the anomaly. The following table shows the average anomaly score among 2000 steps that HTM generates when encountering different anomalies.

Scalar Encoder Grid Cells
Normal 0.00422116 0.0645078
Shift 5 px 0.00683655 0.379953
Shift 50 px 0.115336 0.943195
Revolve at (200, 200) 0.749588 0.996648
Reverse direction 0.0170673 0.828555
Fixed at (50, 50) 0.0005 1

## Immunity to Catastrophic Forgetting

I don’t see this being discussed much in the forum. HTM is very resistant to catastrophic forgetting.
Catastrophic forgetting is a phenomenon where ML algorithms (mostly Neural Networks today) will totally forget what it had learned when training on new data that does not contain patterns of the previous data.
For amusement I trained HTM on the normal path till a low anomaly score. Than train HTM when the circle revolves around (250, 250) till a low anomaly score. When I set the circle back to it’s original orbit. HTM immediately recognized the pattern. Although giving a anomaly score of ~0.3 instead of ~0.05.
After further training to reduce the anomaly score. I set the circle orbiting around (250, 250) again. This time HTM fully recognized the path and gives a low score of ~0.05. Good job HTM!

## Further analysis

I’m curious that weather if HTM is relying on any context (higher order memory) to predict the next state. Since each location has a unique representation, first order memory should be enough to learn all the sequences. So I limited the TM to only have 1 cell in each column.

And… HTM still learns the pattern. Although the SDR density TemporalMemory generated that achieved the same anomaly score increased from 17% to 21%. (Both pretty dense.)

## The code

The source is available here on GitHub. Well… the code is very messy for now. I’ll spend some time to clean it up in the future.

`HTMPath` is a GUI application with visualizations of the HTM model and other info.
These are the controls.

• w - move orbit up 5 pixels
• a - move orbit left 5 pixels
• s - move orbit down 5 pixels
• d - move orbit right 5 pixels
• up - move orbit up 50 pixels
• down - move orbit left 50 pixels
• left - move orbit down 50 pixels
• right - move orbit right 50 pixels
• o - move orbit center to (250, 250)
• l - set orbit radius from 100 to 105
• f - fast forward
• p - slow motion (limit to 10 FPS)
• c - lock the circle at (50, 50)
• Left Shift - Force learning (Learning is disabled when orbit is altered)
• n - Force disable learning
• t - reverse orbit direction

`bench` is a CLI tool for generating test results as fast as possible. Change `GridCellEncoder2D` to `LocEncoder2D` in bench.cpp to switch between Grid Cells and Scalar Encoders.3

I think that’s enough for today, Hope someone find this helpful.

12 Likes

This is great, but I’m still trying to figure out how to run it. I was hoping someone would do something like this, but I want to explain how this is different from our current papers.

In my video and the way I implemented grid cell modules, SDRs were created that had semantic similarity to other locations nearby. In our current papers, we do not assume this or depend on it at all. So current HTM theory does not require that SDRs representing locations be semantically similar to SDRs representing nearby locations. I explained it that way and visualized it that way because I thought people would relate to it, and it clearly exposes an interesting property of SDRs. Just FYI.

1 Like

After building (aka `make`), you should be able to run it via `bin/HTMPath`

1 Like

While the theory does not requiring locations near to each other to be semantically similar, It seems to me that in practice that they probably will be. I recall that the current implementation has bumps of activity in the GCM being nudged around as location is updated. Depending on the radius/certainty and velocity, this results in some overlap in the activity between time steps.

Additionally, if topology is added to the mix, then the activity-nudging strategy would also result in locations being partially within the receptive field of cells connected to other nearby locations.

I don’t see this continuity as a bad thing, myself. It makes it easier to visualize how path integration might work (the property whereby if I go diagonally 5 steps, I end up with the same representation as forward 3 steps then right 4).

4 Likes

Just trying to be clear about what current theory and papers are saying and what they are not. This was something Jeff and Marcus pointed out to me when I made these visualizations, and I chose not to mention it in the videos or the blog post.

1 Like

@rhyolight Have you ran the application successfully? It would be great to know that it works on anything other than my setup.

2 posts were merged into an existing topic: Help installing HTMPath on macOS

I have uploaded my slides. It contains nothing more that what I have posted. But… enjoy!

Please forgive my accent. I have made a video a while ago showing this project in action. Hopefully someone find it useful.
(Despite the title, the video is in English.)

7 Likes

Your accent is fine and very easy to hear.(at least better than mine)
It’s very interesting and now I want to see the displacment cell encoder in action!
Do you happen to have any plans on it?

2 Likes

I’m really looking forward to getting the bleeding edge theory working. And I need to get displacement cells working for my bachelor project. But now I’m occupied by researchs like HTM on FPGAs, a heterogeneous framework for HTM, etc… Laying a better ground for HTM on the CS side.
I’ll get to displacement cells eventually.

2 Likes

That video was awesome! I really need to get this project compiling and working on my iMac. I’ll make it a higher priority. I talked about it on twitch.

1 Like

@rhyolight Thanks for the awesome stream! I’ll try to catch your stream next time.

I’ll push WIndows support for HTMPath soon. You will have it up and running by then if you have a free laptop laying around. (I wish I also have a sleek Mac…)

1 Like

Hi trying to compile your great project! Got it compiled nearly everything in Ubuntu 16, but having this error:

HTMPath/HTMHelper.hpp:3:39: fatal error: nupic/algorithms/Cells4.hpp: No such file or directory

Any ideas how to solve it?

You’ll need to build and install nupic.core from source!

``````git clone https://github.com/numenta/nupic.core
cd nupic.core
export NUPIC_CORE=`pwd`
mkdir -p \$NUPIC_CORE/build/scripts
cd \$NUPIC_CORE/build/scripts
cmake \$NUPIC_CORE -DCMAKE_BUILD_TYPE=Release -NUPIC_TOGGLE_INSTALL=ON -DPY_EXTENSIONS_DIR=\$NUPIC_CORE/bindings/py/src/nupic/bindings .
make -j4
sudo make install

#Since NuPIC.core has problem installing it's own headers
cd \$NUPIC_CORE
sudo cp -r src/nupic /usr/local/include
sudo cp -r build/scripts/src/nupic /usr/local/include
``````

(nupic_src_2.7) rdaneel (master *) build \$ make -j4
[ 12%] Linking CXX shared library lib/libimgui_sfml.so
[ 25%] Building CXX object CMakeFiles/bench.dir/bench.cpp.o
/usr/bin/ld: cannot find -lnupic_core
collect2: error: ld returned 1 exit status
CMakeFiles/imgui_sfml.dir/build.make:146: recipe for target ‘lib/libimgui_sfml.so’ failed
make[2]: *** [lib/libimgui_sfml.so] Error 1
CMakeFiles/Makefile2:67: recipe for target ‘CMakeFiles/imgui_sfml.dir/all’ failed
make[1]: *** [CMakeFiles/imgui_sfml.dir/all] Error 2
make[1]: *** Waiting for unfinished jobs…
In file included from /usr/local/include/nupic/utils/Random.hpp:36:0,
from /usr/local/include/nupic/math/ArrayAlgo.hpp:43,
from /usr/local/include/nupic/algorithms/Segment.hpp:35,
from /usr/local/include/nupic/algorithms/Cells4.hpp:29,
from /home/rdaneel/Goon/HTMPath/HTMHelper.hpp:3,
from /home/rdaneel/Goon/HTMPath/bench.cpp:8:
/usr/local/include/nupic/proto/RandomProto.capnp.h:7:44: fatal error: capnp/generated-header-support.h: No such file or directory
compilation terminated.
CMakeFiles/bench.dir/build.make:62: recipe for target ‘CMakeFiles/bench.dir/bench.cpp.o’ failed
make[2]: *** [CMakeFiles/bench.dir/bench.cpp.o] Error 1
CMakeFiles/Makefile2:141: recipe for target ‘CMakeFiles/bench.dir/all’ failed
make[1]: *** [CMakeFiles/bench.dir/all] Error 2
Makefile:83: recipe for target ‘all’ failed
make: *** [all] Error 2

Now I’m having this error once I’ve installed through source. Any ideas?

Ohh… my fault. I forget that NuPIC.core 's default install directory is not the system directory. You are at the last step of building the code! Copy libnupic_core.a (should be somewhere in the build directory) to `/usr/local/lib` . Or add `-DCMAKE_INSTALL_PREFIX=/usr/local` to the cmake parameters and rebuild NuPIC,core.

Ok thanks!

Now when compilinh the HTMPath gives this error:

/usr/local/include/nupic/proto/RandomProto.capnp.h:7:44: fatal error: capnp/generated-header-support.h: No such file or directory
compilation terminated.

Any idea? I know I’m making a lot of questions but I think it woudl be great to solve these issues to have some working example of this new theory in such a simple yet very compeling example.

3 Likes

No problem! I’m always more than happy to help.

Hmm… Seems to be a problem within NuPIC.core. Anyone from Numenta can help?
capnp seems not be installed or NuPIC.core. May you check weather capnp and it’s header is installed?
Also may you try to add the flag -DNUPIC_BUILD_PYEXT_MODULES=off to CMake flags and re-build + install?

1 Like