PLearn 0.1
Public Member Functions | Static Public Member Functions | Public Attributes | Static Public Attributes | Protected Member Functions | Static Protected Member Functions | Protected Attributes | Private Types | Private Member Functions | Private Attributes
PLearn::KNNVMatrix Class Reference

#include <KNNVMatrix.h>

Inheritance diagram for PLearn::KNNVMatrix:
Inheritance graph
[legend]
Collaboration diagram for PLearn::KNNVMatrix:
Collaboration graph
[legend]

List of all members.

Public Member Functions

 KNNVMatrix ()
virtual void build ()
 simply calls inherited::build() then build_()
virtual void makeDeepCopyFromShallowCopy (CopiesMap &copies)
 Transforms a shallow copy into a deep copy.
virtual string classname () const
virtual OptionListgetOptionList () const
virtual OptionMapgetOptionMap () const
virtual RemoteMethodMapgetRemoteMethodMap () const
virtual KNNVMatrixdeepCopy (CopiesMap &copies) const

Static Public Member Functions

static string _classname_ ()
 Declares name and deepCopy methods.
static OptionList_getOptionList_ ()
static RemoteMethodMap_getRemoteMethodMap_ ()
static Object_new_instance_for_typemap_ ()
static bool _isa_ (const Object *o)
static void _static_initialize_ ()
static const PPathdeclaringFile ()

Public Attributes

VMat k_nn_mat
Ker kernel_pij
int knn
bool report_progress

Static Public Attributes

static StaticInitializer _static_initializer_

Protected Member Functions

int getSourceIndexOf (int i, int &i_ref, int &i_n) const
 Return the index in the source matrix of the sample number i in this matrix.
int getTag (int p) const
 Return the tag of the sample number p in a bag: p == 0 => 1 p == knn-1 => 2 otherwise => 0 (If knn == 1, always return 3).
virtual void getNewRow (int i, const Vec &v) const
 Needed because it's a SourceVMatrix.

Static Protected Member Functions

static void declareOptions (OptionList &ol)
 Declares this class' options.

Protected Attributes

Mat nn
 Store the nearest neighbours of each point.
Mat pij
 Store the pij weights, if a kernel_pij is provided.

Private Types

typedef SourceVMatrix inherited

Private Member Functions

void build_ ()
 This does the actual building.

Private Attributes

Vec source_row
 Used to store a row of the source VMatrix.

Detailed Description

Definition at line 53 of file KNNVMatrix.h.


Member Typedef Documentation

Reimplemented from PLearn::SourceVMatrix.

Definition at line 58 of file KNNVMatrix.h.


Constructor & Destructor Documentation

PLearn::KNNVMatrix::KNNVMatrix ( )

Definition at line 55 of file KNNVMatrix.cc.

    : knn(6),
      report_progress(1)
{}

Member Function Documentation

string PLearn::KNNVMatrix::_classname_ ( ) [static]

Declares name and deepCopy methods.

Reimplemented from PLearn::SourceVMatrix.

Definition at line 71 of file KNNVMatrix.cc.

OptionList & PLearn::KNNVMatrix::_getOptionList_ ( ) [static]

Reimplemented from PLearn::SourceVMatrix.

Definition at line 71 of file KNNVMatrix.cc.

RemoteMethodMap & PLearn::KNNVMatrix::_getRemoteMethodMap_ ( ) [static]

Reimplemented from PLearn::SourceVMatrix.

Definition at line 71 of file KNNVMatrix.cc.

bool PLearn::KNNVMatrix::_isa_ ( const Object o) [static]

Reimplemented from PLearn::SourceVMatrix.

Definition at line 71 of file KNNVMatrix.cc.

Object * PLearn::KNNVMatrix::_new_instance_for_typemap_ ( ) [static]

Reimplemented from PLearn::SourceVMatrix.

Definition at line 71 of file KNNVMatrix.cc.

StaticInitializer KNNVMatrix::_static_initializer_ & PLearn::KNNVMatrix::_static_initialize_ ( ) [static]

Reimplemented from PLearn::SourceVMatrix.

Definition at line 71 of file KNNVMatrix.cc.

void PLearn::KNNVMatrix::build ( ) [virtual]

simply calls inherited::build() then build_()

Reimplemented from PLearn::SourceVMatrix.

Definition at line 103 of file KNNVMatrix.cc.

References PLearn::SourceVMatrix::build(), and build_().

Here is the call graph for this function:

void PLearn::KNNVMatrix::build_ ( ) [private]

This does the actual building.

Reimplemented from PLearn::SourceVMatrix.

Definition at line 112 of file KNNVMatrix.cc.

References PLearn::Kernel::build(), PLearn::Kernel::computeGramMatrix(), PLearn::Kernel::computeNeighbourMatrixFromDistanceMatrix(), PLearn::VMat::getSubRow(), i, PLearn::VMatrix::inputsize_, PLearn::PP< T >::isNull(), j, k_nn_mat, kernel_pij, knn, PLearn::VMatrix::length(), PLearn::VMat::length(), PLearn::VMatrix::length_, n, nn, pij, PLERROR, PLWARNING, PLearn::Kernel::report_progress, report_progress, PLearn::TMat< T >::resize(), PLearn::TMat< T >::row(), PLearn::DistanceKernel::setDataForKernelMatrix(), PLearn::SourceVMatrix::setMetaInfoFromSource(), PLearn::SourceVMatrix::source, PLearn::sum(), PLearn::VMatrix::targetsize_, PLearn::VMatrix::updateMtime(), PLearn::VMat::width(), and PLearn::VMatrix::width_.

Referenced by build().

                        {
    updateMtime(source);
    updateMtime(k_nn_mat);
    if (source) {
        int n = source->length();
        bool recompute_nn = true;
        if (k_nn_mat) {
            if (k_nn_mat->length() > 0) {
                // We are given precomputed k nearest neighbours, what a good news.
                if (k_nn_mat->length() == source->length()) {
                    if (k_nn_mat->width() < knn) {
                        PLWARNING("In KNNVMatrix::build_ - Not enough neighbours in the given k_nn_mat, will recompute nearest neighbours");
                    } else {
                        // Looks like this is the right thing.
                        recompute_nn = false;
                        nn.resize(n, knn);
                        for (int i = 0; i < n; i++) {
                            k_nn_mat->getSubRow(i, 0, nn(i));
                        }
                    }
                } else {
                    // Lengths differ: maybe the source VMat is a subset of the matrix
                    // whose nearest neighbours have been computed.
                    // Let's try a SelectRowsVMatrix.
                    PP<SelectRowsVMatrix> smat = dynamic_cast<SelectRowsVMatrix*>((VMatrix*) source);
                    if (!smat.isNull() && smat->source->length() == k_nn_mat->length()) {
                        // Bingo !
                        // Safety warning just in case it is not what we want.
                        PLWARNING("In KNNVMatrix::build_ - Will consider the given k_nn_mat has been computed on source's distr VMat");
                        recompute_nn = false;
                        // Now we need to retrieve the nearest neighbours within the SelectRowsVMatrix.
                        nn.resize(n, knn);
                        Vec store_nn(k_nn_mat->width());
                        for (int i = 0; i < n; i++) {
                            nn(i,0) = i;  // The nearest neighbour is always itself.
                            k_nn_mat->getRow(smat->indices[i], store_nn);
                            int k = 1;
                            for (int j = 1; j < knn; j++) {
                                bool ok = false;
                                while (!ok && k < store_nn.length()) {
                                    int q = smat->indices.find(int(store_nn[k]));
                                    if (q >= 0) {
                                        // The k-th nearest neighbour in smat->distr is in smat.
                                        ok = true;
                                        nn(i,j) = q;
                                    }
                                    k++;
                                }
                                if (k == store_nn.length()) {
                                    // We didn't find the j-th nearest neighbour.
                                    PLERROR("In KNNVMatrix::build_ - Not enough neighbours in the SelectRowsVMatrix");
                                }
                            }
                        }
                    } else {
                        // Maybe it's a SubVMatrix of the matrix whose nearest neighbours have been computed.
                        PP<SubVMatrix> smat_sub = dynamic_cast<SubVMatrix*>((VMatrix*) source);
                        if (    !smat_sub.isNull()
                                &&  smat_sub->source->length() == k_nn_mat->length()
                                &&  smat_sub->width() == smat_sub->source->width()) {
                            // Bingo !
                            // Safety warning just in case it is not what we want.
                            PLWARNING("In KNNVMatrix::build_ - Will consider the given k_nn_mat has been computed on source's parent VMat");
                            recompute_nn = false;
                            nn.resize(n, knn);
                            Vec store_nn(k_nn_mat->width());
                            for (int i = 0; i < n; i++) {
                                nn(i,0) = i;  // The nearest neighbour is always itself.
                                k_nn_mat->getRow(i + smat_sub->istart, store_nn);
                                int k = 1;
                                for (int j = 1; j < knn; j++) {
                                    bool ok = false;
                                    while (!ok && k < store_nn.length()) {
                                        int q = int(store_nn[k]) - smat_sub->istart;
                                        if (q >= 0 && q < smat_sub->length()) {
                                            // The k-th nearest neighbour in
                                            // smat_sub->source is in smat_sub.
                                            ok = true;
                                            nn(i,j) = q - smat_sub->istart;
                                        }
                                        k++;
                                    }
                                    if (k == store_nn.length()) {
                                        // We didn't find the j-th nearest neighbour.
                                        PLERROR("In KNNVMatrix::build_ - Not enough neighbours in the SubVMatrix");
                                    }

                                }
                            }
                        } else {
                            // What the hell is this ?
                            PLWARNING("In KNNVMatrix::build_ - Don't know what to do with k_nn_mat, will recompute the nearest neighbours");
                        }
                    }
                }
            }
        }

        if (recompute_nn) {
            // First make sure we can store the result if needed.
            if (k_nn_mat) {
                if (k_nn_mat->length() > 0) {
                    PLERROR("In KNNVMatrix::build_ - The given k_nn_mat already has data, free it first");
                }
            }
            // Compute the pairwise distances.
            DistanceKernel dk(2);
            if (report_progress) {
                dk.report_progress = true;
                dk.build();
            }
            dk.setDataForKernelMatrix(source);
            Mat distances(n,n);
            dk.computeGramMatrix(distances);
            // Deduce the nearest neighbours.
            nn = dk.computeNeighbourMatrixFromDistanceMatrix(distances);
            // Only keep the (knn) nearest ones.
            // TODO Free the memory used by the other neighbours.
            // TODO Make the matrix be a TMat<int> instead of a Mat.
            nn.resize(n, knn);
            // Store the result.
            if (k_nn_mat) {
                for (int i = 0; i < n; i++) {
                    k_nn_mat->appendRow(nn(i));
                }
            }
        }

        // Initialize correctly the various fields.
        targetsize_ = source->targetsize() + 1;
        length_ = n * knn;
        width_ = source->width() + 1;
        setMetaInfoFromSource();

        // Compute the p_ij if needed.
        if (kernel_pij) {
            // TODO REPORT PROGRESS IF NEEDED.
            inputsize_++;
            width_++;
            kernel_pij->setDataForKernelMatrix(source);
            int l = source->length();
            pij.resize(l, knn-1);
            for (int i = 0; i < l; i++) {
                real sum = 0;
                real k_ij;
                for (int j = 1; j < knn; j++) {
                    // We omit the first nearest neighbour, which is the point itself.
                    k_ij = kernel_pij->evaluate_i_j(i, int(nn(i,j)));
                    pij(i,j-1) = k_ij;
                    sum += k_ij;
                }
                pij.row(i) /= sum;
            }
        }
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

string PLearn::KNNVMatrix::classname ( ) const [virtual]

Reimplemented from PLearn::SourceVMatrix.

Definition at line 71 of file KNNVMatrix.cc.

void PLearn::KNNVMatrix::declareOptions ( OptionList ol) [static, protected]

Declares this class' options.

Reimplemented from PLearn::SourceVMatrix.

Definition at line 76 of file KNNVMatrix.cc.

References PLearn::OptionBase::buildoption, PLearn::declareOption(), PLearn::SourceVMatrix::declareOptions(), k_nn_mat, kernel_pij, knn, and report_progress.

{
    declareOption(ol, "k_nn_mat", &KNNVMatrix::k_nn_mat, OptionBase::buildoption,
                  "TODO comment");

    declareOption(ol, "knn", &KNNVMatrix::knn, OptionBase::buildoption,
                  "The number of nearest neighbours to consider (including the point itself).");

    declareOption(ol, "kernel_pij", &KNNVMatrix::kernel_pij, OptionBase::buildoption,
                  "An optional kernel used to compute the pij weights (see help).");

    declareOption(ol, "report_progress", &KNNVMatrix::report_progress, OptionBase::buildoption,
                  "TODO comment");

// Kinda useless to declare it as an option if we recompute it in build().
// TODO See how to be more efficient.
//  declareOption(ol, "nn", &KNNVMatrix::nn, OptionBase::learntoption,
//      "The matrix containing the index of the knn nearest neighbours of\n"
//      "each data point.");

    // Now call the parent class' declareOptions
    inherited::declareOptions(ol);
}

Here is the call graph for this function:

static const PPath& PLearn::KNNVMatrix::declaringFile ( ) [inline, static]

Reimplemented from PLearn::SourceVMatrix.

Definition at line 136 of file KNNVMatrix.h.

:

KNNVMatrix * PLearn::KNNVMatrix::deepCopy ( CopiesMap copies) const [virtual]

Reimplemented from PLearn::SourceVMatrix.

Definition at line 71 of file KNNVMatrix.cc.

void PLearn::KNNVMatrix::getNewRow ( int  i,
const Vec v 
) const [protected, virtual]

Needed because it's a SourceVMatrix.

Reimplemented from PLearn::SourceVMatrix.

Definition at line 308 of file KNNVMatrix.cc.

References getSourceIndexOf(), getTag(), PLearn::VMatrix::inputsize(), kernel_pij, pij, PLearn::TVec< T >::resize(), PLearn::SourceVMatrix::source, source_row, PLearn::TVec< T >::subVec(), PLearn::VMatrix::targetsize(), PLearn::VMatrix::weightsize(), and PLearn::VMat::width().

                                                    {
    source_row.resize(source->width());
    int i_n;
    int i_ref;
    int real_i = getSourceIndexOf(i, i_ref, i_n);
    source->getRow(real_i, source_row);
    if (kernel_pij) {
        v.subVec(0, source->inputsize()) << source_row.subVec(0, source->inputsize());
        if (i_n > 0) {
            v[source->inputsize()] = pij(i_ref, i_n - 1);
        } else {
            v[source->inputsize()] = -1;
        }
    } else {
        v.subVec(0, source->inputsize() + source->targetsize())
            << source_row.subVec(0, source->inputsize() + source->targetsize());
    }
    v.subVec(inputsize(), source->targetsize())
        << source_row.subVec(source->inputsize(), source->targetsize());
    v[inputsize() + source->targetsize()] = getTag(i_n);
    if (weightsize() > 0) {
        v.subVec(inputsize() + targetsize(), weightsize())
            << source_row.subVec(source->inputsize() + source->targetsize(), source->weightsize());
    }
}

Here is the call graph for this function:

OptionList & PLearn::KNNVMatrix::getOptionList ( ) const [virtual]

Reimplemented from PLearn::SourceVMatrix.

Definition at line 71 of file KNNVMatrix.cc.

OptionMap & PLearn::KNNVMatrix::getOptionMap ( ) const [virtual]

Reimplemented from PLearn::SourceVMatrix.

Definition at line 71 of file KNNVMatrix.cc.

RemoteMethodMap & PLearn::KNNVMatrix::getRemoteMethodMap ( ) const [virtual]

Reimplemented from PLearn::SourceVMatrix.

Definition at line 71 of file KNNVMatrix.cc.

int PLearn::KNNVMatrix::getSourceIndexOf ( int  i,
int i_ref,
int i_n 
) const [inline, protected]

Return the index in the source matrix of the sample number i in this matrix.

Also return in i_n the neighbour rank, and in i_ref the reference point.

Definition at line 298 of file KNNVMatrix.cc.

References knn, and nn.

Referenced by getNewRow().

                                                                  {
    i_ref = i / knn;
    i_n = i % knn;
    int i_neighbour_source = int(nn(i_ref, i_n));
    return i_neighbour_source;
}

Here is the caller graph for this function:

int PLearn::KNNVMatrix::getTag ( int  p) const [inline, protected]

Return the tag of the sample number p in a bag: p == 0 => 1 p == knn-1 => 2 otherwise => 0 (If knn == 1, always return 3).

Definition at line 337 of file KNNVMatrix.cc.

References knn.

Referenced by getNewRow().

                                  {
    // TODO Better use the constants defined in SumOverBagsVariable.h.
    if (knn == 1) return 3;
    if (p == 0) return 1;
    if (p == knn - 1) return 2;
    return 0;
}

Here is the caller graph for this function:

void PLearn::KNNVMatrix::makeDeepCopyFromShallowCopy ( CopiesMap copies) [virtual]

Transforms a shallow copy into a deep copy.

Reimplemented from PLearn::SourceVMatrix.

Definition at line 272 of file KNNVMatrix.cc.

References PLearn::deepCopyField(), kernel_pij, PLearn::SourceVMatrix::makeDeepCopyFromShallowCopy(), nn, pij, PLWARNING, and source_row.

{
    inherited::makeDeepCopyFromShallowCopy(copies);

    // ### Call deepCopyField on all "pointer-like" fields
    // ### that you wish to be deepCopied rather than
    // ### shallow-copied.
    // ### ex:
    // deepCopyField(trainvec, copies);

    deepCopyField(source_row, copies);
    deepCopyField(nn, copies);
    deepCopyField(pij, copies);
    // Currently commented out because some of the VMats used for k_nn_mat
    // may not implement deep copy correctly.
    // TODO Put back when other VMats are fine.
//  deepCopyField(k_nn_mat, copies);
    deepCopyField(kernel_pij, copies);

    PLWARNING("In KNNVMatrix::makeDeepCopyFromShallowCopy - k_nn_mat will not be deep copied");
    //  PLERROR("KNNVMatrix::makeDeepCopyFromShallowCopy not fully (correctly) implemented yet!");
}

Here is the call graph for this function:


Member Data Documentation

Reimplemented from PLearn::SourceVMatrix.

Definition at line 136 of file KNNVMatrix.h.

Definition at line 82 of file KNNVMatrix.h.

Referenced by build_(), and declareOptions().

Definition at line 83 of file KNNVMatrix.h.

Referenced by build_(), declareOptions(), getNewRow(), and makeDeepCopyFromShallowCopy().

Definition at line 84 of file KNNVMatrix.h.

Referenced by build_(), declareOptions(), getSourceIndexOf(), and getTag().

Store the nearest neighbours of each point.

Definition at line 71 of file KNNVMatrix.h.

Referenced by build_(), getSourceIndexOf(), and makeDeepCopyFromShallowCopy().

Store the pij weights, if a kernel_pij is provided.

Definition at line 74 of file KNNVMatrix.h.

Referenced by build_(), getNewRow(), and makeDeepCopyFromShallowCopy().

Definition at line 85 of file KNNVMatrix.h.

Referenced by build_(), and declareOptions().

Vec PLearn::KNNVMatrix::source_row [mutable, private]

Used to store a row of the source VMatrix.

Definition at line 61 of file KNNVMatrix.h.

Referenced by getNewRow(), and makeDeepCopyFromShallowCopy().


The documentation for this class was generated from the following files:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines