verne.freenode.net changed the topic of #mlpack to: http://www.mlpack.org/ -- We don't respond instantly... but we will respond. Give it a few minutes. Or hours. -- Channel logs: http://www.mlpack.org/irc/
tsathoggua has joined #mlpack
tsathoggua has quit [Client Quit]
mentekid has joined #mlpack
mentekid_ has quit [Remote host closed the connection]
mentekid_ has joined #mlpack
mentekid__ has joined #mlpack
mentekid has quit [Read error: Connection reset by peer]
mentekid has joined #mlpack
mentekid__ has quit [Read error: Connection reset by peer]
mentekid__ has joined #mlpack
mentekid has quit [Read error: Connection reset by peer]
mentekid__ has quit [Client Quit]
< mentekid_>
rcurtin: here are the new results - http://pastebin.com/XQmgPgGv with both profiling and debugging turned off. These results look a lot more like yours
< mentekid_>
rcurtin: though I noticed that we didn't test all the same datasets, I swapped your phy for pokerhand. Anyway these results are quite more consistent, as you said unique is most of the time the fastest and find has a different behavior from unique most of the time
< mentekid_>
I don't exclude the possibility of me doing something stupid yesterday. Like not saving the file and simply re-compiling unique (or find) twice and reporting the results as if they were different
< mentekid_>
but it could also be the profiling I guess
Mathnerd314 has quit [Ping timeout: 246 seconds]
mentekid_ has quit [Ping timeout: 244 seconds]
nilay has joined #mlpack
mentekid has joined #mlpack
mentekid has quit [Ping timeout: 250 seconds]
mentekid has joined #mlpack
< rcurtin>
mentekid: now there is not a single case where unique does not outperform find... hmm...
< rcurtin>
looking through my results too, there is only one case where find is faster, and that's with OpenBLAS on the corel dataset that I have (which is weird and small and not the same one you are using)
< rcurtin>
I have to step out for a little bit... but I think I want to run a few more OpenBLAS simulations
< rcurtin>
maybe a few more non-OpenBLAS simulations too, on other datasets
< rcurtin>
it seems like maybe we can conclude that if not using OpenBLAS, unique is always the better choice
< mentekid>
so no need for cutoff either
< mentekid>
simply go with unique?
< rcurtin>
yeah, I would say "go with unique", but I want to do a little more testing with OpenBLAS first
< rcurtin>
I'll be back in a little bit
< rcurtin>
sorry that something that was supposed to be easy got so complex :(
< mentekid>
nah it's an interesting problem (made more complex by my inability to compile correctly :P)
< rcurtin>
do you think you were compiling with debugging symbols before?
< rcurtin>
er, with profiling symbols?
< mentekid>
profiling symbols yeah
< mentekid>
I'm not sure about debugging, I think they were off
< mentekid>
I also had the idea of performing the candidate retrieval during training. So for each 2nd level hash bucket, we could run retrieveIndicesFromTable and store the results in memory. That way queries would be O(1) if we use a hash table with key the level 2 Code and value the precomputed Candidate Set
< mentekid>
I'm not sure what the impact would be on memory and how longer it would take for Train() to run though
< mentekid>
but I think that's supposed to be the goal of LSH in the end, very fast queries after slow preprocessing
< rcurtin>
so the idea is, instead of having secondHashTable store the indices of points, it would store the actual points themselves?
< mentekid>
I am not sure how secondHashTable is implemented, but I think right now it works as secondHashTable[point] = code
< mentekid>
so we check if secondHashTable[point] == secondHashTable[query] and if so add point to the candidates
< mentekid>
couldn't we instead store secondHashTable[code] = list_of_points
< mentekid>
so then queries would be faster?
< mentekid>
again I haven't looked into it very carefully, I'm not sure what I'm saying makes sense
< rcurtin>
yeah, I am not sure if I completely understand. but if you try it and it speeds things up I am all for it :)
< mentekid>
I'll try and do it before Sunday then, it will be good warm-up
< rcurtin>
sure, don't feel obligated
< rcurtin>
I think it'll be a lot easier for me to understand if I see the code :)
< mentekid>
to be honest my schedule is tight because I need to deliver a first draft of my thesis until next Friday... But I'm almost done with everything but the text which is in bad shape :P
< mentekid>
But I think I'll find time on Saturday
< rcurtin>
okay, sounds good... hopefully the thesis text gets better :)
govg has joined #mlpack
Mathnerd314 has joined #mlpack
nilay has quit [Ping timeout: 250 seconds]
marcosirc has joined #mlpack
sumedhghaisas has joined #mlpack
sumedhghaisas has quit [Client Quit]
sumedhghaisas has joined #mlpack
sumedhghaisas has quit [Client Quit]
sumedhghaisas has joined #mlpack
< marcosirc>
Hi Sumedh.
sumedhghaisas has quit [Read error: Connection reset by peer]
sumedhghaisas has joined #mlpack
< sumedhghaisas>
Hi @marcosirc
< sumedhghaisas>
there is some problem in my connection... its getting disconnected frequently...
< marcosirc>
Ok. No problem.
< marcosirc>
Is it ok for you to chat now, or you would prefer another moment?
< sumedhghaisas>
@marcosirc is 17:00 GMT okay for you??
< sumedhghaisas>
I will be done with my dinner till then...
tsathoggua has joined #mlpack
< marcosirc>
Yes. Ok.
< marcosirc>
See you later.
mentekid has quit [Ping timeout: 276 seconds]
tsathoggua has quit [Client Quit]
< sumedhghaisas>
@marcosirc Hey Marcos...
nilay has joined #mlpack
< marcosirc>
Hi
< marcosirc>
Here I am
< marcosirc>
Sorry, I was having lunch.
< sumedhghaisas>
Sure no problem...
< marcosirc>
Thanks.
< marcosirc>
If you agree, acording to the timeline included in the proposal, next week, I could start modifying the existing dual tree algorithm to approximate nearest neighbor search.
< marcosirc>
I should modify the prune rule to include an epsilon, as mentioned by Ryan at the end of the paper: "Faster dual-tree traversal for nearest neighbor search". Something like: prune if d_min(N_q, N_r) > ( 1 / (1 + epsilon ) ) * B(N_q).
< marcosirc>
Would you think this would be ok?
< marcosirc>
Once that this is working properly, I could work on the command line tool.
< sumedhghaisas>
yes I talked with him on this...
< sumedhghaisas>
The current implementation will support this epsilon addition ...
< marcosirc>
Yes.
< sumedhghaisas>
but I have read that papaper long ago... let me take a look at it again today...
< marcosirc>
Ok.
< sumedhghaisas>
I am going over it now.. just a quick glance...
< sumedhghaisas>
Okay so as I understand it...
< sumedhghaisas>
the current framework is
< sumedhghaisas>
the minimum distance between nodes is < bound for nodes then prune...
< sumedhghaisas>
we want to add an epsilon parameter here to accommodate approximation...
< sumedhghaisas>
is that right?
< marcosirc>
Just the opposite, if the min distance is greater than the bound, then prune..
< sumedhghaisas>
ohh sorry my bad...
< marcosirc>
Yes. We want to add an epsilon to make it approximate.
< sumedhghaisas>
< it is...
< sumedhghaisas>
hmm...
< sumedhghaisas>
if min distance > bound - epsilon then prune...
< sumedhghaisas>
something like that...
< marcosirc>
Yes.
< marcosirc>
We make the bound smaller.
< marcosirc>
We can prune more because we are looking for an approximate solution.
< sumedhghaisas>
So your equation was (1 / (1 + epsilon) ) * bound...
< sumedhghaisas>
yes thats right... thats the general idea I got from the paper you have added in your proposal...
< marcosirc>
Yes, ok.
< sumedhghaisas>
is there any special reason for ( 1 / (1 + epsilon) ) ?
< marcosirc>
Is is mentioned in the paper: "Faster dual tree traversal for nearest neighbor search", below the "table 3".
< sumedhghaisas>
ohh... let me take a quick look...
< sumedhghaisas>
I am not sure how exactly it will differ from bound - epsilon... both will achieve same result I think...
< marcosirc>
the difference is that epsilon is a relative coefficient here.
< marcosirc>
It is not a fixed error. It is a relative error.
< sumedhghaisas>
yes you are right...
< sumedhghaisas>
In that scenario I think (1 / (1 + epsilon)) is a better choice...
< marcosirc>
We can express the same as: if (1+e) * dmin(N_q,N_r) > B , prune, because we are sure we can get a neighbor at least as good as B.
< marcosirc>
Ok.
< sumedhghaisas>
yes... reminds me of the definition of approximation algorithms...
< rcurtin>
I think relative error is better to implement than absolute error -- I think more people will want to use relative error
< marcosirc>
Ok. Maybe we can add an option later, to decide if absolute or relative error is considered.
< sumedhghaisas>
yeah... even if we go by the definition of approximation algorithms... its always a relative error... epsilon being the approximation parameter...
< sumedhghaisas>
I think just relative is fine... I am thinking of any advantage of absolute over relative...
< sumedhghaisas>
but I think an absolute error can be translated in relative error and vise versa...
< sumedhghaisas>
so either is fine...
< sumedhghaisas>
mention of it in the documentation will suffice...
< marcosirc>
Ok. The advantage of absolute error is that you can be sure the real error won't be grater than that. With relative error it depends on the real distance of the nearest neighbor. If it is greater, the real error is greater.
< marcosirc>
But, I think if we take an approach, we won't have problems to change it if we decide to do that in the future.
< sumedhghaisas>
yes true... but when I say a 1/2 approximation algorithm its always the relative error...
< sumedhghaisas>
thats why I thought that people might get confused in using absolute error in approximation algorithms...
< sumedhghaisas>
but you are right...
< sumedhghaisas>
changing it later won;t cause much of a trouble...
< marcosirc>
Yes! Ok. So we agree on this. I will make it clear in the documentation.
< sumedhghaisas>
Sure...
< sumedhghaisas>
If we decide later we will change it...
< rcurtin>
yeah, that sounds good to me too. I'm not sure what the right design is to support both relative and absolute approximation, but I don't think it will be too hard to do
< sumedhghaisas>
I agree... we can go ahead with relative for now... maybe a working example will let us do some tests to figure this problem out...
< sumedhghaisas>
We can check how absolute error fares in situations...
< marcosirc>
Yes, sounds great.
< marcosirc>
Another think I would like to talk is about github workflow.
< marcosirc>
I will start working on my forked mlpack repo. What would you prefer, many pull requests during the summer, or a unique pull request at the end of the gsoc?
< sumedhghaisas>
@rcurtin what happend to the naywhayare nickname? :P
< sumedhghaisas>
hmm... yes... thats a good point...
< sumedhghaisas>
different pull requests would let us merge the part of the code...
< sumedhghaisas>
I mean even though you will basically work on the same thing...
< sumedhghaisas>
I would like to follow the feature branch style... I think thats more elegant.. what you think??
< marcosirc>
Yes. Ok, for me. Many features branches in my own forked repo, and many pull requests during the summer.
mentekid has joined #mlpack
< sumedhghaisas>
that will also give me time to go through the code while you work on the next feature...
< rcurtin>
sumedhghaisas: I realized that people had no idea who I was, so I decided to sync github username with irc nick :)
< rcurtin>
marcosirc: I agree, many PRs is better, it allows us to get your code into a release quicker
< marcosirc>
Ok. Yes, I agree!
< sumedhghaisas>
@rcurtin haha... I always wanted to ask.. pardon my ignorance... what does it mean??? naywhayare??
< sumedhghaisas>
@marcosirc we can decide as the time passes when to create a new branch so there is no confusion
< sumedhghaisas>
that way I can pull the specific feature from your repo if I want ...
< marcosirc>
Ok.
< rcurtin>
sumedhghaisas: it was some thing I came up with when I was a kid
< rcurtin>
I was telling a friend of mine that my name was "nayr" (ryan backwards)
< rcurtin>
and he said he knew someone named naywhayare
< rcurtin>
I have no idea if he actually did, but I adopted it as an IM handle :)
mentekid has quit [Ping timeout: 260 seconds]
govg has quit [Ping timeout: 260 seconds]
< sumedhghaisas>
@rcurtin ohh my god...
< sumedhghaisas>
you are kidding me right??
< nilay>
zoq: do you also host mlpack irc server?
< nilay>
sorry better question would be, does one channel also connected by more than one servers.. or it does not depend on channel...
< zoq>
nilay: yeah, the irc network is a undirected graph, so my entry point could be different from yours
< nilay>
zoq: so did you also see others getting split?
< zoq>
nilay: sometimes, yes
nilay has quit [Ping timeout: 250 seconds]
nilay has joined #mlpack
< zoq>
nilay: I've sent you the data by mail.
< nilay>
zoq: ok
marcosirc has quit [Quit: WeeChat 1.4]
nilay has quit [Ping timeout: 250 seconds]
< rcurtin>
sumedhghaisas: nope, no joke
< rcurtin>
I think I was probably 8 or 9 years old? I can't remember
nilay has joined #mlpack
sumedhghaisas has quit [Ping timeout: 252 seconds]