CCARTree::CARTtrain crashes on certain data input

[rayrapetyan]

Tested on 6.1.3 branch. With attached data process crashes on:
SGVector<index_t> subsetr(num_vecs-count_left);
trying to allocate -1401 bytes of memory.

There is some logical error before this point which I'm not able to determine.

Note:

• if you remove random lines from input (e.g. last line), it works fine.
• if you set feature types (ft[i]) to "false", it works fine.

#include <shogun/base/init.h>
#include <shogun/io/CSVFile.h>
#include <shogun/multiclass/tree/CARTree.h>
#include <shogun/features/DenseFeatures.h>

using namespace shogun;

int main() {
    init_shogun();

    SGMatrix<float64_t> data(3,25);
    data(0,0)=3501680094;data(1,0)=2819730067;data(2,0)=3768683836;
    data(0,1)=3501680094;data(1,1)=2819730067;data(2,1)=4062061028;
    data(0,2)=3501680094;data(1,2)=2819730067;data(2,2)=1499743118;
    data(0,3)=2641972770;data(1,3)=1338919042;data(2,3)=1155967739;
    data(0,4)=2641972770;data(1,4)=2819730067;data(2,4)=184922492;
    data(0,5)=2641972770;data(1,5)=1338919042;data(2,5)=1329826561;
    data(0,6)=3501680094;data(1,6)=1338919042;data(2,6)=369303686;
    data(0,7)=2641972770;data(1,7)=1338919042;data(2,7)=1329826561;
    data(0,8)=3501680094;data(1,8)=2819730067;data(2,8)=425996979;
    data(0,9)=2641972770;data(1,9)=2819730067;data(2,9)=227098284;
    data(0,10)=3501680094;data(1,10)=2819730067;data(2,10)=3346889787;
    data(0,11)=3501680094;data(1,11)=1338919042;data(2,11)=2325536312;
    data(0,12)=3501680094;data(1,12)=1338919042;data(2,12)=2539194562;
    data(0,13)=3501680094;data(1,13)=1338919042;data(2,13)=2539194562;
    data(0,14)=3501680094;data(1,14)=2819730067;data(2,14)=1529782598;
    data(0,15)=3501680094;data(1,15)=1338919042;data(2,15)=227098284;
    data(0,16)=3107643541;data(1,16)=1627665381;data(2,16)=1785801560;
    data(0,17)=2641972770;data(1,17)=1338919042;data(2,17)=1155967739;
    data(0,18)=781601688;data(1,18)=2819730067;data(2,18)=3708802819;
    data(0,19)=781601688;data(1,19)=1107772512;data(2,19)=2991931201;
    data(0,20)=781601688;data(1,20)=3764025486;data(2,20)=156530866;
    data(0,21)=781601688;data(1,21)=2819730067;data(2,21)=187479954;
    data(0,22)=781601688;data(1,22)=2819730067;data(2,22)=4194153830;
    data(0,23)=781601688;data(1,23)=2819730067;data(2,23)=976264558;
    data(0,24)=2641972770;data(1,24)=1338919042;data(2,24)=2440844662;

    SGVector<float64_t> labels(25);
    for (auto i = 0; i < 18; ++i) {
        labels[i] = 0;
    }
    for (auto i = 18; i < 25; ++i) {
        labels[i] = 1;
    }

    CDenseFeatures<float64_t> train_feat(data);
    CMulticlassLabels train_labels(labels);

    auto vectors = train_feat.get_num_features();
    SGVector<bool> ft=SGVector<bool>(vectors);
    for (auto i = 0; i < vectors; ++i) {
        ft[i] = true;
    }

    CCARTree* c=new CCARTree(ft, PT_MULTICLASS, 5, false);
    c->set_labels(&train_labels);
    c->train(&train_feat);

    return 0;
}

[vigsterkr]

@rayrapetyan ok i can reproduce this error on linux... interesting enough the same is not true on OSX :( i'll get back to you ASAP when i figured out what's going wrong.

[rayrapetyan]

Thanks! Mine was FreeBSD. It could be on OSX allocator just returns max avail memory instead of a crash or something like that... I've also noticed that on another data sets training can take incredibly high amount of time (e.g. about 4 seconds for < 100 rows of data, or hours for few thousands of rows). It could be the same issue as described here. Let's see.

[vigsterkr]

@rayrapetyan i've already found out what's the root cause of the error.... there's a buffer overflow, so whatever osx returns is garbage, or it should be. currently i'm figuring out where's the logic error with the buffer overflow.

[vigsterkr]

@rayrapetyan note that row = feature in case of shogun, i.e. that's it column oriented (each column is an example)

[rayrapetyan]

Yeah, I've struggled with that already. But in my example there are 3 "vectors of features" with 25 features in each. I've double-checked cycle:

for (auto i = 0; i < vectors; ++i) {
        ft[i] = true;
}

It fills 3 values as it should, so no overflow there...

[vigsterkr]

@rayrapetyan ah yeah, no the overflow is in CARTree itself. your code is fine.

[vigsterkr]

@rayrapetyan btw regarding the runtime: do you have categoricals? i.e. where you set ft[i] = true;? because if so, then its slow because of this: https://github.com/shogun-toolbox/shogun/blob/develop/src/shogun/multiclass/tree/CARTree.cpp#L683

in case your problem is a binary classification or regression, today i'll push a patch that'll speed-up things significantly... if it's multiclass i am afraid that you'll have to wait longer for a speedup heuristics.