Re: [Caml-list] stack overflow

[Markus Mottl <markus@oefai.at>]

On Wed, 09 Apr 2003, Yang Shouxun wrote:
> Yes, the decision tree building function is not tail recursive. I heared 
> people saying C4.5 (in C) also has stack overflow problem when the training 
> dataset becomes very large.

I can't imagine that this is the problem: either the data is
well-distributed, in which case the stack size will grow roughly
logarithmically with the size of the data due to partitioning. And if not,
the maximum depth of the tree is limited by the number of available input
variables anyway. You'd need many, many thousands of those before this
becomes a problem, which even large, industrial datasets that I know do
not exceed.

> I don't know how to write a tail recursive version to build trees.
> If there are not that many continuous attributes and the dataset is
> not so large, the tree stops growing before stack overflow.

The trick is to use continuation passing style (CPS): you pass a function
closure (continuation) containing everything that's needed in subsequent
computations.  Instead of returning a result, the sub-function calls the
continuation with the result, which makes the functions tail-recursive.

But anyway, I think there must be some fishy operation going on. Why not
use the debugger to find out? Or even better: send a link to the code :-)

> Can one know the maximal number of calls before it overflow the stack?

It depends: byte-code uses its own stack, which you can query using the
Gc-module. Otherwise, for native-code, call the ulimit-program (Unix),
which displays resource limits including stack usage or interface to
the system call "getrlimit".

In any case, it would be interesting to see your code. Are you going to
release it under some free license?

Regards,
Markus Mottl

-- 
Markus Mottl          http://www.oefai.at/~markus          markus@oefai.at

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners