Mailing-List: contact dev-help@mahout.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@mahout.apache.org
Received-SPF: pass (athena.apache.org: domain of adeneche@gmail.com designates
 209.85.216.170 as permitted sender)
DomainKey-Signature: a=rsa-sha1; c=nofws;
        d=gmail.com; s=gamma;
        h=mime-version:in-reply-to:references:date:message-id:subject:from:to
         :content-type:content-transfer-encoding;
        b=uPQT/zGRx1NBKY5+IatzPorq/LvJLRz50gnyfIFDrvPhgq+fv4CS6TuuR6u8s2Mw+s
         g5+JL8z3GqwNW/bPXzVqXYkVqA8CQcDeWjkOmBjDKy9mHjHXz/Iyw1aEMPVtON9vBxbP
         8za3aDqqxB7cCqBfwj88zLSy5Mrn942ctCYxU=
MIME-Version: 1.0
In-Reply-To: <AANLkTin0VDVqNUWZhjHFZBgGd1cERZDLMDCDPQqkWoof@mail.gmail.com>
References: <AANLkTimzFTXZefg02G84a8kOj=zwkCMvPD1DVS302dvh@mail.gmail.com>
	<AANLkTin0VDVqNUWZhjHFZBgGd1cERZDLMDCDPQqkWoof@mail.gmail.com>
Date: Thu, 7 Oct 2010 05:13:01 +0100
Message-ID: <AANLkTi=_aFg64N1z5_86sGTgoe7PUDXaXjspsMiWntxF@mail.gmail.com>
Subject: Re: default tree builder
From: deneche abdelhakim <adeneche@gmail.com>
To: dev@mahout.apache.org
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

> Does this refer to the random forest stuff?

Yes, and the DefaultTreeBuilder is used by all implementations
(sequential, InMem and Partial).

> Andrey has a question about the Random Forest code.  (hurray for him for
> being the first outsider to beat on it)

Hurray =3DD

I will make the fix and create a patch as soon as possible.

I wonder if Andrey good give us the data that lead to this Bug. Just
to make sure it's not another hidden bug that's causing the infinite
recursion.

On Wed, Oct 6, 2010 at 10:22 PM, Ted Dunning <tdunning@apache.org> wrote:
> Andrey has a question about the Random Forest code. =A0(hurray for him fo=
r
> being the first outsider to beat on it)
>
> This looks like a simple and fairly obvious fix, but I can't afford enoug=
h
> attention to verify.
>
> Deneche?
>
> ---------- Forwarded message ----------
> From: Andrey Gusev <andrey.gusev@gmail.com>
> Date: Wed, Oct 6, 2010 at 1:41 PM
> Subject: default tree builder
> To: Ted Dunning <tdunning@apache.org>
>
>
> Hi Ted,
>
> Unrelated to KCCA discussion. I have some pretty positive results with
> bagging of DefaultTreeBuilder-id3 like implementation. However, there is
> seems to be an issue with building possible running into infinite recursi=
on,
> i.e. stack overflow. Basically when you have few features, it is possible
> that all results left to split can not be split according to any attribut=
e
> so in my cases line 107 of DefaultTreeBuilder keeps being called with
> identical set. More precisely loSubset is empty and hiSubset contain few
> instances which can not be split. I modified this into LimitDepthTreeBuil=
der
> with something like:
>
>
> =A0 =A0public Node build(Random rng, Data data) {
> =A0 =A0 =A0 =A0return inner_build(rng, data, 0);
> =A0 =A0}
>
> =A0 =A0public Node inner_build(Random rng, Data data, int depth) {
>
> =A0 =A0 =A0 =A0if (selected =3D=3D null) {
> =A0 =A0 =A0 =A0 =A0 =A0selected =3D new boolean[data.getDataset().nbAttri=
butes()];
> =A0 =A0 =A0 =A0}
>
> =A0 =A0 =A0 =A0if (data.isEmpty()) {
> =A0 =A0 =A0 =A0 =A0 =A0return new Leaf(-1);
> =A0 =A0 =A0 =A0}
> =A0 =A0 =A0 =A0if (isIdentical(data)) {
> =A0 =A0 =A0 =A0 =A0 =A0return new Leaf(data.majorityLabel(rng));
> =A0 =A0 =A0 =A0}
> =A0 =A0 =A0 =A0if (data.identicalLabel()) {
> =A0 =A0 =A0 =A0 =A0 =A0return new Leaf(data.get(0).label);
> =A0 =A0 =A0 =A0}
> =A0 =A0 =A0 =A0// SFDC change to prevent stack overflow
> =A0 =A0 =A0 =A0if (depth > MAX_DEPTH) {
> =A0 =A0 =A0 =A0 =A0 =A0return new Leaf(data.majorityLabel(rng));
> =A0 =A0 =A0 =A0}
> ...
>
> }
>
> I know mahout-0.4 is pretty close to freeze (or past it). But this is sim=
ple
> enough change and with high enough MAX_DEPTH (say 100) should not have mu=
ch
> functional impact unless there is actually infinite recursion. Or it coul=
d
> default to not use it but have a setter for that. Let me know what you
> think.
>
> Thanks,
>
> Andrey
>