I think if we used this algorithm we could get the same output in every implemented language.
We should implement this, and cut out all place where fancy RNG methods are used and simply use this integer generator and where necessary convert to float format in a universal way.
This RNG method is frighteningly fast, deterministic and simple!
/**
* Implementation of George Marsaglia's elegant Xorshift random generator
* 30% faster and better quality than the built-in java.util.random see also
* see http://www.javamex.com/tutorials/random_numbers/xorshift.shtml
*/
protected int next(int nbits) {
long x = seed;
x ^= (x << 21);
x ^= (x >>> 35);
x ^= (x << 4);
seed = x;
x &= ((1L << nbits) - 1);
return (int) x;
}
The obvious benefit is 100% parity between all HTM implementations!
Using a super fast RNG algorithm even if it is considered less “secure” since that isn’t too important for us
But I’m wary of agreeing on any specific implementation until we look at our usage and understand the implications. Plus, this won’t get us 100% parity by itself. Different implementations may request random numbers in different orders and they may have floating point differences. We could mitigate those issues by eliminating floats and being explicit about calling order to RNG. Not sure if that’s worth the effort but seems intriguing.
This would make my life very different! I would wake up in the morning with a smile on my face continuously. My son would start doing things the first time I tell him. The Lotto numbers would bend to my will (not that I play it). …and rainbows would appear on a daily basis!
Since my implementation mirrors Numenta’s exactly (algorithmically), I could actually run both side by side and get the same results! Look - there’s a rainbow!
I have experienced the floating point differences, but if we only use integers and do the conversion in code (when floats are desired) - we may be able to avoid this?
I just mentioned that implementation because it is sooooo much faster than all the others I have used. This is the implementation that the guys who did ATAD (Air Traffic Anomaly Detector) (2nd place Numenta Challenge Winners) used in their HTM.Java implementation.
@scott I agree with all of your concerns. It would require deliberate effort and maybe < 1 week engineering allocation (due to subtle changes in all the tests) - but the differences would be felt downstream for the life of the project. Performance all around would improve, but parity between implementations that had the same algorithm and thus made the same number of calls (such as HTM.Java) could be debugged with ease (my personal dream at the moment).
Before NuPIC goes to version 1.0 is the time to do it…
Worth having a look at this one http://www.pcg-random.org/
The minimal implementation is also very simple and a complete library is available to take care of seeding and distributions, though the white paper demonstrating its superior performance is still under review.
Has any consideration been given lately to making HTM.java a binding around nupic.core, thus guaranteeing that the algorithm implementations used by nupic and HTM.java are exactly identical and follow DRY? And rainbows all around
The importance of a Java implementation of NuPIC (either through bindings or a pure implementation), is profound and immediate.
Java is a very popular programming language (with over 9 million developers according to Oracle); and the accessibility that a Java implementation provides to its profoundly wide audience is inarguably a boost to NuPIC’s popularity, attractiveness and accessibility.
(HTM.Java doesn’t enjoy the same channels of advertisement as NuPIC due to its peripheral placement in the literature and website references - but despite all of that and its young age it gets over 1000 views every two weeks, and growing).
This is all to say that supporting HTM.Java is more of an immediate concern, than a nebulous “to-do” item on some future itinerary.
The needed support comes in the form of easing development integration, debugging and verification.
Enter the idea of a universal RNG…
Standardizing on a simple; fast; efficient and portable RNG algorithm does not exist in contradiction to eventual development of a Java binding for nupic.core, and it gives HTM.Java the support it needs sooner rather than later.
I would agree that development of a Java binding is an important proposition but one who’s time is future bound and not as relevant to this current discussion, imho.
P.S.
To the extent that the Python version of nupic mirrors the algorithms used by nupic.core, HTM.Java’s algorithms are exactly the same. This is its number one mandate. I just want to squash any entertainment of the fact that this isn’t the case. (using the formal definition of the term “algorithm”)
You could also just replicate the Numpy code in Java, which would give you the same result (identical sequence of outputs) but would not require changing anything in NuPIC. I did this in Go a few months ago, it’s very simple. I can put that up in a Gist if you’re interested.
[Edit: Forgot I had actually published on my github here!]
NuPIC uses a custom random implementation which is cryptography worthy (and quite overkill), and I don’t believe that the same random implementation is used everywhere - but I may be mistaken. We simply need to call nextInt() or next() - all the time using the same seed.
But yeah - we should use a simple generator because the ones in the libs seem to be much slower… (java.util.Random and MersenneTwister are very much slower than the above)
I don’t want the conversation to get things off track. Figuring out how not to change NuPIC is not the topic of conversation because I assure you there are multiple ways randoms are being requested that depart from the normal basic ways it could be used.
The topic is using the above mentioned code with a simple call to return a integer value everywhere a random is used so that we can be assured that the same values are returned every time so that code which makes the same number of calls in the same sequence will always have the same random numbers available - regardless of language.
NuPIC uses lots of exotic methods and calls which we will need to get rid of so that we can have the same executions on the same code.
I don’t think we should be trying to see how we can duplicate the exoticness in other languages - that’s chasing the rhino up the wrong tree
These are both very interesting links… I wonder how Adam is coming along with an implementation of SparseMatrices? Last I talked with him, he said the intention is there for the future but that immediate business needs didn’t give him time (at that time) to look into it…? (re: nd4j)
anyway thanks for the link to javacpp - interesting!
They both need to be “cleaned up” (documentation added and neatened up) - If someone wants to clean up the Python file in a Pythonic way, please feel welcome? I’ll do the Java file…
They both have runnable methods that can be run with an example output which you should see is the same.
I’m going to substitute this into the Python temporal_memory.py file so that I can get the exact same outputs (at least during development) !! Yay!
EDIT: Could someone please write a C++ version of these?
If I read Scott’s comment correctly, he’s not going to approve this RNG swap until we do some research into how and where all RNGs are used in the NuPIC codebase, so this is not just going to turn into a quick swap. (I just want to level your expectations, David.)
@rhyolight I understand (and totally agree that’s what he should do), I just want to remove as many impediments or “one-day-we-shoulds” from the situation. We now have a viable implementation which is tested to work, and can be seriously considered. That takes us a great distance…
In the meantime this is very useful because I can now exactly vet every unit test by temporarily substituting this working RNG into the Python version! Which took ALOT of work and I am ecstatic about!
(this is all part and parcel of my efforts to debug the NAB, btw)
Added universal sample() method to be used in the SpatialPooler.mapPotential() method
The method has tests which not only test that the output is the same for both languages; but also test that all the interim random numbers generated are the same!
From a performance perspective, the strategy of inner looping to find randoms can in certain cases have a performance hit if the number of choices is very large and the number of indices to select is a high percentage of them. Obviously it depends on the actual use case, but thought I would point it out.
while (temp.contains(choices.get(randomIdx))) {
randomIdx = nextInt(upperBound);
}
If it becomes a performance issue, another strategy that trades performance for extra memory consumption, is maintaining a second collection, and splicing out each element that is chosen (so that you know you are always choosing from indices that have not yet been chosen).
That’s a strategy that’s used a lot 'round these parts; and in this case I think it would be most beneficial since the number of choices is not that many. I wasn’t too worried about it since mapPotential is a start up method, but the sample() method can be used more generally so it should be as efficient as possible. Thanks for suggesting that.
Ok, now I’ve added a compatibility_mode where the Python version will “emulate” Java’s (Or C’s) overflows by using the c_longlong ctypes function:
from ctypes import c_longlong as ll
There are cases where the Java version will overflow and the Python version will not. This guards against that case in an “optional” way so that if you choose to run in compatibility mode, then you will get the same exact output - but you may run slightly slower. Since this RNG is faster than most, it may not make a difference - however if you run it by instantiating like:
