Anubhav, Does this scheme not ensure that adjacent buckets share w-1 bits?
- Chetan On Feb 19, 2014 9:37 AM, "Anubhav Chaturvedi" <[email protected]> wrote: > I will present the code in some time but till then here is an explanation > with example. > > Take n=10, w = 3 and r=1 ( to say that each integer itself constitutes the > bucket ) > > now Initially no bucket is created and the input given is 1 > Hence any random representation can be taken. > *1 --> 100 010 100 0* > > Next 2 arrives, > its window lies from 0 to 4 ( both inclusive ) and everything else is > outside > 1 is within the window and the only bucket present > So it randomly chooses a representation with 2 bits differing ( i.e, 2 1s > maintain their place ) > *2 --> 101 000 100 0* > > > > *------------------------------------------------------------------------------------------------------------------------------* > > *Present map state :* > *01 --> 100 010 100 0* > *02 --> 101 000 100 0* > > Now lets say there was a spike and 50 was given as input > Its window is from 50-3+1=48 to 50+3-1=52 > All the existing buckets are outside its window, and it should not have > any bits in common with that > *01* or *02* = 101 010 100 0 ---- the 0s are the places that this > bucket should have an encoding in > > selecting any 3 bits in random satisfies the condition, with both the > existing buckets 1 and 2 > hence *50 --> 010 000 011 0* > > > *------------------------------------------------------------------------------------------------------------------------------* > > *Present map state :* > *01 --> 100 010 100 0* > *02 --> 101 000 100 0* > *50 --> 010 000 011 0* > > Now let the input be 5 > Its window is from (5-3+1)=3 to (5+3-1)=7 > All existing buckets are outside its window > *01* or *02* or *50 = *111 010 111 0 ---------- the 0s are the > bits this can occupy without conflict > Selecting the only possible encoding > *05 --> 000 101 000 1* > > > *------------------------------------------------------------------------------------------------------------------------------* > > *Present map state :* > *01 --> 100 010 100 0* > *02 --> 101 000 100 0* > *05 --> 000 101 000 1* > *50 --> 010 000 011 0* > > Now let the input be 4 > Its window is from (4-3+1)=2 to (4+3-1)=6 > 2 and 5 lies within the window and rest are outside > *01* or *50* = 110 010 111 0 > The encoding should occupy the maximum of the places containing 0s > Let the possible encoding be 001 101 000 0 > condition between 4 -- 1 > satisfied ( 2*3 bits differ ) > condition between 4 -- 2 > satisfied ( 2*2 bits differ ) > condition between 4 -- 5 > satisfied ( 2*1 bits differ ) > condition between 4 -- 50 > satisfied ( 2*3 bits differ ) > > Hence its fine to choose this as encoding > *04 --> 001 101 000 0* > > > *------------------------------------------------------------------------------------------------------------------------------* > > *Present map state :* > *01 --> 100 010 100 0* > *02 --> 101 000 100 0* > *04 --> **001 101 000 0* > *05 --> 000 101 000 1* > *50 --> 010 000 011 0* > > Let the input be 3 > Its window is from (3-3+1)=1 to (3+3-1)=5 > 1, 2, 4, 5 lie in the window. 50 is outside > 50 = 010 000 011 0 > The encoding should occupy the maximum of the places containing 0s > > Let the randomly chosen encoding be 101 010 000 0 > condition between 3 -- 1 > Not satisfied ( 2 bits differ , expected 4 ) > condition between 3 -- 2 > Satisfied ( 2 bits differ ) > condition between 3 -- 4 > Not satisfied ( 4 bits differ, expected 2 ) > condition between 3 -- 5 > Not satisfied ( 6 bits differ, expected 4 ) > condition between 3 -- 50 > Satisfied ( 6 bits differ ) > Score = 2 ( #conditions satisfied ) > > Let the next possible encoding be 101 100 000 0 > condition between 3 -- 1 > Satisfied ( 4 bits differ ) > condition between 3 -- 2 > Satisfied ( 2 bits differ ) > condition between 3 -- 4 > Satisfied ( 2 bits differ ) > condition between 3 -- 5 > Satisfied ( 4 bits differ ) > condition between 3 -- 50 > Satisfied ( 6 bits differ ) > Score = 5 ( #conditions satisfied ) == number of existing buckets > > Hence select the encoding > *3 --> 101 100 000 0* > > > > *------------------------------------------------------------------------------------------------------------------------------* > *Overflow case* > > *Present map state :* > *01 --> 100 010 100 0* > *02 --> 101 000 100 0* > *03 --> 101 100 000 0* > *04 --> **001 101 000 0* > *05 --> 000 101 000 1* > *50 --> 010 000 011 0* > > Let the input be 6 > Its window is from (6-3+1)=4 to (6+3-1)=8 > 4, 5 lie in the window. 1 ,2 ,3 ,50 are outside > *01* or *02* or *03* or *50* = 111 110 111 0 > The encoding should occupy the maximum of the places containing 0s > > But this is a tricky case : > Encoding 100 001 000 1 gets the lowest score and is closer to bucket 1,2,3 > in representation > > Encoding 000 001 100 1 gets median score and is closer to bucket 1,2 in > representation > > Encoding 010 001 000 1 } > Encoding 000 001 010 1 }------ gets highest score and is closer to > bucket 50 in representation > Encoding 000 001 001 1 } > > Encoding 000 011 000 1 }------ gets highest score and is closer to > bucket 1 in representation. > > > *WHICH TO CHOOSE?? * > According to me the last option is better and more logical in this case > but we will have to think more carefully the selection condition. > > This exercise did get a lot more things clear, things i was stuck at while > coding. > > Please provide your feedback. > > *Regards,* > *Anubhav Chaturvedi* > > *Birla Institute of Technology & Science, Pilani* > KK Birla Goa Campus > +91-9637399150 > > *" You can do anything if you stop doing everything "* > > > On Wed, Feb 19, 2014 at 12:04 AM, Chetan Surpur <[email protected]>wrote: > >> To be clear, I don't mean necessarily in code, I mean just a simple email >> explanation using a toy example. >> >> >> On Tue, Feb 18, 2014 at 1:28 AM, Anubhav Chaturvedi < >> [email protected]> wrote: >> >>> Sure , I can try that. I will be using the same testing technique as >>> used in Fergal Byrne's example (http://fergalbyrne.github.io/rdse.html) >>> . >>> >>> *Regards,* >>> *Anubhav Chaturvedi* >>> >>> *Birla Institute of Technology & Science, Pilani* >>> KK Birla Goa Campus >>> +91-9637399150 >>> >>> *" You can do anything if you stop doing everything "* >>> >>> >>> On Tue, Feb 18, 2014 at 11:24 AM, Chetan Surpur <[email protected]>wrote: >>> >>>> Hi Anubhav, >>>> >>>> Thanks for sharing your thoughts on this. Do you think you can show a >>>> small example of your algorithm? >>>> >>>> Thanks, >>>> Chetan >>>> >>>> >>>> On Sat, Feb 15, 2014 at 4:35 PM, Anubhav Chaturvedi < >>>> [email protected]> wrote: >>>> >>>>> Hi >>>>> >>>>> Chetan Surpur presented a great idea of RDSE. The video got me >>>>> thinking if I could optimize it a bit and here is what I came up with. >>>>> Please provide your feedback. >>>>> >>>>> URL : >>>>> https://docs.google.com/document/d/1obYHE4-3q-oR1zbazUJWLTXBIzmt3GlG0wcKVT_Ohgg/edit?usp=sharing >>>>> >>>>> I have tried to optimize it for memory and convergence of two extremes >>>>> of representation. >>>>> >>>>> *Regards,* >>>>> *Anubhav Chaturvedi* >>>>> >>>>> *Birla Institute of Technology & Science, Pilani* >>>>> KK Birla Goa Campus >>>>> +91-9637399150 >>>>> >>>>> *" You can do anything if you stop doing everything "* >>>>> >>>>> _______________________________________________ >>>>> nupic mailing list >>>>> [email protected] >>>>> http://lists.numenta.org/mailman/listinfo/nupic_lists.numenta.org >>>>> >>>>> >>>> >>>> _______________________________________________ >>>> nupic mailing list >>>> [email protected] >>>> http://lists.numenta.org/mailman/listinfo/nupic_lists.numenta.org >>>> >>>> >>> >>> _______________________________________________ >>> nupic mailing list >>> [email protected] >>> http://lists.numenta.org/mailman/listinfo/nupic_lists.numenta.org >>> >>> >> >> _______________________________________________ >> nupic mailing list >> [email protected] >> http://lists.numenta.org/mailman/listinfo/nupic_lists.numenta.org >> >> > > _______________________________________________ > nupic mailing list > [email protected] > http://lists.numenta.org/mailman/listinfo/nupic_lists.numenta.org > >
_______________________________________________ nupic mailing list [email protected] http://lists.numenta.org/mailman/listinfo/nupic_lists.numenta.org
