naywhayare 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/
sumedh_ has joined #mlpack
sumedhghaisas has quit [Ping timeout: 265 seconds]
< sumedh_>
naywhayare: Hey ryan, have time??
< naywhayare>
sumedh_: sure, go ahead
< sumedh_>
Ohh sorry I solved it... There was some error in CMake file I was trying to create...
< sumedh_>
By the way I ran svn commit yesterday...
< sumedh_>
It showed me lines like sending files and all...
< sumedh_>
I have to run svn up to update the files online right??
< naywhayare>
your commit went through fine
< naywhayare>
you should be doing svn up regularly anyway, because we have a lot of people committing to the repo
< sumedh_>
I think I have made a mistake in amf.hpp :(
< sumedh_>
not a big one...
< sumedh_>
did my commit build okay??
< jenkins-mlpack>
Starting build #1939 for job mlpack - svn checkin test (previous build: SUCCESS)
< naywhayare>
for some reason jenkins didn't start the job
< jenkins-mlpack>
sumedhghaisas: * fixed include error
Anand_ has quit [Ping timeout: 246 seconds]
Anand_ has joined #mlpack
Anand_ has quit [Ping timeout: 246 seconds]
andrewmw94 has joined #mlpack
oldbeardo has joined #mlpack
oldbeardo has quit [Ping timeout: 246 seconds]
oldbeardo has joined #mlpack
< oldbeardo>
naywhayare: I tried what you suggested, but it doesn't work out
< oldbeardo>
that's because most columns contain just one rating, and their relative cosines become almost 1
< oldbeardo>
however, I tried out another dataset present in the trunk, namely 'test_data_3_1000.csv'
< oldbeardo>
it works okay for that, and converges in just two iterations, it may be a good choice for the test
oldbeardo has quit [Quit: Page closed]
sumedh_ has joined #mlpack
Anand_ has joined #mlpack
oldbeardo has joined #mlpack
< naywhayare>
oldbeardo: ok, using test_data_3_1000.csv is just fine
oldbeardo_ has joined #mlpack
< oldbeardo_>
naywhayare: sorry about that
< naywhayare>
oldbeardo_: no problem, did you get the message I sent?
< oldbeardo_>
naywhayare: yes, I will make that test for QUIC-SVD, what about trees?
< oldbeardo_>
CosineTree I mean
< naywhayare>
I've been thinking about it but I don't have a complete solution yet
< oldbeardo_>
okay, even the decreasing error thing won't work
< oldbeardo_>
because it does not decrease strictly
oldbeardo has quit [Ping timeout: 246 seconds]
< naywhayare>
alright; I will keep that in mind
< oldbeardo_>
well, the actual error does, but the estimate does not
< naywhayare>
ok. fortunately, for testing, we can compare with the actual error
< oldbeardo_>
right, if the matrix is small enough
< oldbeardo_>
naywhayare: you were also going to think about merging the two classes, any luck with that?
< naywhayare>
I haven't had time to approach that yet
< oldbeardo_>
okay
oldbeardo_ has quit [Quit: Page closed]
govg has joined #mlpack
govg has quit [Ping timeout: 245 seconds]
govg has joined #mlpack
govg has quit [Changing host]
govg has joined #mlpack
< Anand_>
Marcus : I have added the metrics to scikit. I need your help in changing the RunMethod function as you did in mlpack
< Anand_>
I have added the RunMetrics function
< Anand_>
Also modified RunMethod a bit but it won't work. It needs to be changed
govg has quit [Ping timeout: 260 seconds]
Anand_ has quit [Ping timeout: 246 seconds]
< marcus_zoq>
Anand: Hello, okay, the current version is on github?
oldbeardo has joined #mlpack
< oldbeardo>
naywhayare: hey, just saw your mail, these tests seem quite comprehensive to me!
< oldbeardo>
anyway, I will start working on this and get back in 2-3 days
< naywhayare>
okay, thanks. let me know if you need any help
< oldbeardo>
well, I can think of one question right now
< oldbeardo>
my MGS uses the basis vectors already stored in the class object, how can I test it?
sumedh_ has quit [Ping timeout: 260 seconds]
< naywhayare>
oldbeardo: yeah, I wasn't sure about that. I think maybe moving MGS to a standalone function may be a good solution
< oldbeardo>
naywhayare: you mean somewhere in core math?
< naywhayare>
yeah, maybe in lin_alg.hpp
< naywhayare>
seems like a good fit to me
< oldbeardo>
it would be, but only if there is way to remove columns from a matrix in armadillo
< oldbeardo>
because the CosineTree construction involves removing basis vectors as well
< oldbeardo>
and from the results of my Google search I don't think there is a way to do that
< oldbeardo>
okay, sorry, that was really stupid
< oldbeardo>
we can always overload
< naywhayare>
sorry, I stepped out
< naywhayare>
there is shed_rows(), shed_cols()
< oldbeardo>
oh great, that solves it then
< oldbeardo>
oh no, it does not
< oldbeardo>
naywhayare: how do I keep an account of which column to remove
< oldbeardo>
since removing one column will affect the indices of other basis vectors
< naywhayare>
I don't see what the issue is
< naywhayare>
if you move ModifiedGramSchmidt() to lin_alg.hpp and add a parameter for the existing basis, then you just call ModifiedGramSchmidt(basis, node->Centroid(), newBasisVector) in CosineTree::AddToBasis()
< oldbeardo>
no, that's not where the problem is
sumedh_ has joined #mlpack
< oldbeardo>
look at the CosineTree condition, there is an if condition
< oldbeardo>
*CosineTree constructor
< naywhayare>
oh, ok, I see what the problem is
< naywhayare>
because the basis is constantly growing and shrinking in size, I think you're better off holding a std::vector<arma::vec&>
< naywhayare>
to represent the basis vectors
< naywhayare>
instead of an arma::mat that's constantly changing size
< naywhayare>
this way adding and removing elements doesn't cost an entire resize of the basis matrix but instead just removing a reference from the std::vector
< oldbeardo>
right, but should that be the default data structure we expect in MGS?
< naywhayare>
in this case, I think yes
< naywhayare>
so maybe it's inappropriate to put it in lin_alg.hpp, but it at least doesn't need to be part of CosineTree
< naywhayare>
and as a result it can be tested separately
< oldbeardo>
so where do we put it?
< naywhayare>
I dunno, pick somewhere :) cosine_tree_util.hpp ?
< naywhayare>
we could put it in lin_alg if you want, but you're right that std::vector<arma::vec&> is a weird thing to accept for the basis matrix and is very specific to CosineTree
< oldbeardo>
wait, before that, won't we face the same problem in std::vector<arma::vec&>
< oldbeardo>
and if we are looking at a particular solution, I think the existing does the job
< naywhayare>
no, because you don't need the considerBasis object anymore
< oldbeardo>
no, I mean the referencing
< oldbeardo>
how do we know which element to remove?
< oldbeardo>
the same if condition problem
< naywhayare>
isn't the element to be removed always going to be the first basis vector?
< naywhayare>
no, hang on, I don't think that's necessarily true because of the priority queue structure
< oldbeardo>
yup, exactly
< naywhayare>
I think we can make some modifications to guarantee that the element to be removed is the first basis vector
sumedh_ has quit [Ping timeout: 260 seconds]
< naywhayare>
actually, maybe we can do this entirely differently
< naywhayare>
you could modify CosineNode so that it also stored its associated orthonormalized basis vector
< naywhayare>
then, when you call ModifiedGramSchmidt(), pass the entire CosineNodeQueue
< naywhayare>
and loop over the queue, obtaining the orthonormalized basis vector for each entry in it
< oldbeardo>
well, we could, but what advantage would it give over the existing implementation?
< naywhayare>
speed
< naywhayare>
the current implementation uses join_rows()
< naywhayare>
each call to join_rows() costs an allocation and copy equal to the size of the entire basis matrix
< naywhayare>
for large dimensions or large numbers of basis vectors, this can get quite costly
< oldbeardo>
ahh, I didn't know it copied the whole thing
< naywhayare>
yeah, unfortunately there's no other way to do it because there's never a guarantee that you can resize a block of memory to be arbitrarily larger
< naywhayare>
removing the considerBasis object should provide some additional speedup
< oldbeardo>
right, but that's how std::vector works right?
< oldbeardo>
by resizing that is
< naywhayare>
right
< naywhayare>
but holding a std::vector<arma::vec&> means that the total cost doesn't depend on the dimensionality -- just the number of bases
< naywhayare>
*the number of basis vectors
< naywhayare>
because the vector only holds references, not the vectors themselves
< naywhayare>
whereas an arma::mat has to guarantee that all of the vectors it holds are located contiguously in memory
< oldbeardo>
got it
< naywhayare>
we can't avoid some dependence on the number of basis vectors, though
< naywhayare>
an insertion into the priority queue will have cost related to the number of basis vectors
< naywhayare>
so there's no way around that. but the idea of storing an orthonormalized basis vector in a cosine node means that we only have to manage one priority queue
< naywhayare>
although storing that vector in the cosine node has some additional memory cost, it shouldn't be significant since it's only one vector per node
< oldbeardo>
it does not add any cost, since we are storing that vector anyway
< naywhayare>
ah, you're right
< oldbeardo>
thanks Ryan, I will try to complete this soon
< naywhayare>
sure. I'm sorry I misunderstood the problem with my initial ideas and it took so long to come up with something better
< oldbeardo>
one more thing, if we are going with this, I think it will be a good idea to retain MGS as a part of the CosineTree class
< oldbeardo>
which will again make it diificult to test, wow, this is crazy
< naywhayare>
what advantage do you get by retaining it as part of the class?
< naywhayare>
you still need to pass the CosineNodeQueue because that's not a member of the CosineTree class
< naywhayare>
so the arguments end up the same. you can leave it in the CosineTree class, that's just fine; but I don't see how that'll be more difficult to test
< naywhayare>
since you should be able to just make some fake CosineNodeQueue that holds lots of fake CosineNode objects that hold random basis vectors, then pass that to the MGS function
< oldbeardo>
yeah, that can be done
< oldbeardo>
just for correction, CosineNodeQueue is a part of the CosineTree class
< naywhayare>
yeah, you are right, so it'd be easier to hold MGS in the CosineTree class; but the actual queue used for building isn't a member variable, so you'll need to pass it
< oldbeardo>
right, that solves it then
< oldbeardo>
thanks again, I'll see you tomorrow
< naywhayare>
sure, talk to you later
oldbeardo has quit [Quit: Page closed]
< naywhayare>
andrewmw94: so I went reading about ending sentences with prepositions, and wow, this is a much deeper subject than I thought
< naywhayare>
I think I'll stick to C++ and avoid english...
< andrewmw94>
haha
< andrewmw94>
As Churchill said: "This is the sort of nonsense, up with which I shall not put."
< naywhayare>
hah
< andrewmw94>
I think I'm going to need to add some constructors for making empty nodes for use in the split. I don't think we want them to be public, since the user shouldn't need them. I see a few possible solutions: I could just use the current constructor but pass an empty matrix. I could make the new ones, and add the SplitType class to the RectangleTree class so it can use the private constructors, or we could have a namespace for me to
< naywhayare>
message clipped after "have a namespace for me to "
< naywhayare>
(aside: http://tools.ietf.org/html/rfc2812 -- section 2.3: messages shall not exceed 512 characters in length; I'm surprised your client doesn't auto-wrap to multiple messages, but I don't think mine (irssi) does either)
< andrewmw94>
I think I'm going to need to add some constructors for making empty nodes for use in the split. I don't think we want them to be public, since the user shouldn't need them. I see a few possible solutions: I could just use the current constructor but pass an empty matrix.
< andrewmw94>
I could make the new ones, and add the SplitType class to the RectangleTree class so it can use the private constructors, or we could have a namespace for me to use and a seperate one to hide these constructors from the end user? Any thoughts on which solution is best?
< naywhayare>
do you think there is a particularly compelling reason to hide that constructor from the user?
< naywhayare>
or, do we have some way to sidestep the problem so that you never need to make an empty node?
< andrewmw94>
I think making an empty node is going to be necessary since the tree grows upwars so to speak. I don't really see any reason it NEEDS to be hidden from the user, but I might find it confusing to have constructors that I'm not supposed to use.
< andrewmw94>
I don't know if that's common in C++. In java, you can get arround this by not specifying public of private, and then it's only accessible from the same package
< naywhayare>
fascinating, I didn't know that about java
< naywhayare>
so the situation where this occurs is when all of the levels overflow and you need to add a new root?
< naywhayare>
or does this happen when any level overflows?
< andrewmw94>
when the root overflows
< andrewmw94>
that's another question I had, the root can change, so the constructor won't necessarily return a pointer to the root node. Should I add another argument--a pointer that can be set to the root node--or is there a way to have the constructor return an address other than it's own?
< naywhayare>
hm, I don't think we can overload the constructor's return value (or really the return value of the new operator) and even if we can that's pretty hacky
< naywhayare>
right now I'm trying to think of if there is a way that we can avoid creating a node above the current node, and instead do some modifications to the current node and work with its children
< naywhayare>
i.e. instead of making node A have parent newNode, make node A the parent of newNode (where newNode = A), and then modify the bounds of node A
< andrewmw94>
but doesn't that mean we will have a lot of extra copying?
< andrewmw94>
it might not matter since points are only inserted once though
< naywhayare>
you're right; let me think about that for a second
< naywhayare>
copy cost will be sizeof(RectangleTree) + children.size()
< naywhayare>
if that strategy is only used for the root node, then the maximum number of copies is equal to the final depth of the tree
< andrewmw94>
I think it will have to be used for all nodes
< naywhayare>
for other nodes you can modify parent->children[i]
< naywhayare>
where parent->children[i] is the node that you're replacing with a new node
< naywhayare>
I'm trying to understand the problem better to come up with a better solution
< andrewmw94>
yeah.
< naywhayare>
right now, the RTreeSplit class (and the other split policies) appear to propagate changes up the tree
< andrewmw94>
yeah. That's how they have it in the paper.
< naywhayare>
I think we might have an easier time if, instead, the RTreeSplit policy class simply turns an overfilled node into two nodes (regardless of whether or not it's a leaf)
< naywhayare>
and we let the constructor do the propagation
< naywhayare>
hmm... hang on. let me think about how this might change the way RTreeSplit is designed
< andrewmw94>
would that have to be done at the end though? Because some of the algorithms might get to slow if we first split nodes and then try to build the tree
< naywhayare>
yeah, I was assuming the splitting is done after the point is added
< naywhayare>
I was following the idea of RectangleTree::InsertPoint(), rectangle_tree_impl.hpp:94
< naywhayare>
ok, I think an idea has congealed a little better
< naywhayare>
the idea is, remove the call to splitNode() from line 94. a leaf node doesn't check if it needs to be split
< naywhayare>
instead, its parent checks if it needs to be split, after line 109, by adding something like
< naywhayare>
SplitNode(children[bestIndex])
< naywhayare>
because children[bestIndex] is the only child that could possibly need to be split
< andrewmw94>
what would we do for the first node that doesn't have a parent?
< naywhayare>
if SplitNode() does split children[bestIndex], we find some way to add its new child to the children vector, then we return (not if we're the root -- I'll get to that momentarily; for now, assume we're not the root)
< naywhayare>
ok, then let's jump ahead to the root case :)
< naywhayare>
but I think to do that we sort of need to define a new SplitNode() API
< naywhayare>
you can revise this if you like, but basically let's suppose we have SplitNode(a, b), where a is the node to be split; if a needs to be split, the function returns true and { a, b } are the new two nodes; otherwise, a doesn't change and b can be ignored
< naywhayare>
so if we're the root node, we can call SplitNode(*this, b); if the function returned true, then we have to make a copy of *this, do children.clear(), then children.push_back(copy of *this), children.push_back(b)
< naywhayare>
probably have to update the bound and other miscellany too, but I think that can be done quickly
< naywhayare>
do you think this approach makes sense?
< andrewmw94>
I suspect it's faster to have a pointer passed whenever we do something that could change the root, and have the pointer updated to the new root if necessary
< naywhayare>
well but the thing is that the memory address of the root can't ever change; otherwise, when we type 'RectangleTree* r = new RectangleTree(dataset);', we end up with r pointing to somewhere in the middle of the tree
< naywhayare>
the location in memory that corresponds to the root is set as soon as the constructor is called, unfortunately
< naywhayare>
(this makes more sense when a pointer isn't used during construction: 'RectangleTree r(dataset);')
< andrewmw94>
yeah. But I'm concerned with swapping nodes arround. I suspect that we would have to copy all of the child points. I currently have each leaf node storing it's child points, so there's no "centeral" matrix for storing those
< naywhayare>
right, I remember that
< naywhayare>
crap, my ride is here, so I have to go
< naywhayare>
but I think that because you're storing a reference or pointer to the dataset, it doesn't need to be a deep copy of all the elements in the matrix
< andrewmw94>
if we had something like class RTree{ RTreeNode* root};
< andrewmw94>
oh. See you later
< naywhayare>
I'll spend some time thinking about this and hopefully have a better solution later tonight or tomorrow