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

#include <GeodesicDistanceKernel.h>

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

List of all members.

Public Member Functions

 GeodesicDistanceKernel ()
 Default constructor.
 GeodesicDistanceKernel (Ker the_distance_kernel, int the_knn=10, const PPath &the_geodesic_file="", bool the_pow_distance=false, const string &the_method="floyd", bool call_build_=true)
 Convenient constructor.
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 GeodesicDistanceKerneldeepCopy (CopiesMap &copies) const
int computeNearestGeodesicNeighbour (int i, const Mat &distances_xi_x_sorted, real *dist_i=0) const
 Return the index j of the data point which satisfies: 1.
real computeShortestDistance (int i, const Mat &distances_xi_x_sorted) const
 Return the shortest (geodesic) distance to i from a point x whose (non-geodesic) distance to its knn nearest neighbors in the training set is given by the matrix 'distances_xi_x_sorted', whose first column should contain the sorted distances, and whose second column should contain the corresponding indices.
virtual real evaluate (const Vec &x1, const Vec &x2) const
 Compute K(x1,x2).
virtual real evaluate_i_j (int i, int j) const
 returns evaluate(data(i),data(j))
virtual real evaluate_i_x (int i, const Vec &x, real squared_norm_of_x=-1) const
 Return evaluate(data(i),x).
virtual real evaluate_i_x_again (int i, const Vec &x, real squared_norm_of_x=-1, bool first_time=false) const
 Return evaluate(data(i),x), where x is the same as in the precedent call to this same function (except if 'first_time' is true).
virtual real evaluate_i_x_from_distances (int i, const Mat &distances_xi_x_sorted) const
 Evaluate K(x_i,x) where x is not given explicitly, but only by the (sorted and non-geodesic) distances to all training points.
virtual void setDataForKernelMatrix (VMat the_data)
 Overridden to precompute inter-points geodesic distance.

Static Public Member Functions

static string _classname_ ()
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

Ker distance_kernel
PPath geodesic_file
int knn
bool pow_distance
string shortest_algo
VMat geo_distances

Static Public Attributes

static StaticInitializer _static_initializer_

Static Protected Member Functions

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

Private Types

typedef Kernel inherited

Private Member Functions

void build_ ()
 This does the actual building.

Private Attributes

Mat dist_xi_x_sorted1
 Used to store data and save memory allocation.
Mat dist_xi_x_sorted2
Mat dist_xi_x_sorted

Detailed Description

Definition at line 52 of file GeodesicDistanceKernel.h.


Member Typedef Documentation

Reimplemented from PLearn::Kernel.

Definition at line 57 of file GeodesicDistanceKernel.h.


Constructor & Destructor Documentation

PLearn::GeodesicDistanceKernel::GeodesicDistanceKernel ( )

Default constructor.

Definition at line 54 of file GeodesicDistanceKernel.cc.

References distance_kernel.

    : geodesic_file(""),
      knn(10),
      pow_distance(false),
      shortest_algo("floyd")
{
    distance_kernel = new DistanceKernel(2);
}
PLearn::GeodesicDistanceKernel::GeodesicDistanceKernel ( Ker  the_distance_kernel,
int  the_knn = 10,
const PPath the_geodesic_file = "",
bool  the_pow_distance = false,
const string &  the_method = "floyd",
bool  call_build_ = true 
)

Convenient constructor.

Definition at line 63 of file GeodesicDistanceKernel.cc.

References build_(), and distance_kernel.

                         :
    inherited(true, call_build_),
    geodesic_file(the_geodesic_file),
    knn(the_knn),
    pow_distance(the_pow_distance),
    shortest_algo(the_method)
{
    distance_kernel = the_distance_kernel;
    if (call_build_)
        build_();
}

Here is the call graph for this function:


Member Function Documentation

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

Reimplemented from PLearn::Kernel.

Definition at line 82 of file GeodesicDistanceKernel.cc.

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

Reimplemented from PLearn::Kernel.

Definition at line 82 of file GeodesicDistanceKernel.cc.

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

Reimplemented from PLearn::Kernel.

Definition at line 82 of file GeodesicDistanceKernel.cc.

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

Reimplemented from PLearn::Kernel.

Definition at line 82 of file GeodesicDistanceKernel.cc.

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

Reimplemented from PLearn::Object.

Definition at line 82 of file GeodesicDistanceKernel.cc.

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

Reimplemented from PLearn::Kernel.

Definition at line 82 of file GeodesicDistanceKernel.cc.

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

Simply calls inherited::build() then build_().

Reimplemented from PLearn::Kernel.

Definition at line 120 of file GeodesicDistanceKernel.cc.

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

Here is the call graph for this function:

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

This does the actual building.

Reimplemented from PLearn::Kernel.

Definition at line 129 of file GeodesicDistanceKernel.cc.

Referenced by build(), and GeodesicDistanceKernel().

{
}

Here is the caller graph for this function:

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

Reimplemented from PLearn::Object.

Definition at line 82 of file GeodesicDistanceKernel.cc.

int PLearn::GeodesicDistanceKernel::computeNearestGeodesicNeighbour ( int  i,
const Mat distances_xi_x_sorted,
real dist_i = 0 
) const

Return the index j of the data point which satisfies: 1.

j is among the knn nearest neighbors of the point x from which was computed 'distances_xi_x_sorted' 2. it is such that dist(x,j) + geodesic_dist(j,x_i) is minimum If provided, the 'dist_i' parameter is filled with the geodesic distance from x to x_i.

Definition at line 136 of file GeodesicDistanceKernel.cc.

References PLearn::dist(), geo_distances, j, knn, and PLearn::min().

Referenced by computeShortestDistance().

                                                                                                                       {
    real min = distances_xi_x_sorted(0,0) + geo_distances->get(i, int(distances_xi_x_sorted(0,1)));
    real dist;
    int indice = 0;
    for (int j = 1; j < knn; j++) {
        dist = distances_xi_x_sorted(j,0) + geo_distances->get(i, int(distances_xi_x_sorted(j,1)));
        if (dist < min) {
            min = dist;
            indice = j;
        }
    }
    if (dist_i)
        *dist_i = min;
    return int(distances_xi_x_sorted(indice,1));
}

Here is the call graph for this function:

Here is the caller graph for this function:

real PLearn::GeodesicDistanceKernel::computeShortestDistance ( int  i,
const Mat distances_xi_x_sorted 
) const

Return the shortest (geodesic) distance to i from a point x whose (non-geodesic) distance to its knn nearest neighbors in the training set is given by the matrix 'distances_xi_x_sorted', whose first column should contain the sorted distances, and whose second column should contain the corresponding indices.

Definition at line 155 of file GeodesicDistanceKernel.cc.

References computeNearestGeodesicNeighbour().

Referenced by evaluate_i_x_again(), and evaluate_i_x_from_distances().

                                                                                                  {
    static real result;
    computeNearestGeodesicNeighbour(i, distances_xi_x_sorted, &result);
    return result;
}

Here is the call graph for this function:

Here is the caller graph for this function:

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

Declares this class' options.

Reimplemented from PLearn::Kernel.

Definition at line 87 of file GeodesicDistanceKernel.cc.

References PLearn::OptionBase::buildoption, PLearn::declareOption(), PLearn::Kernel::declareOptions(), distance_kernel, geo_distances, geodesic_file, knn, PLearn::OptionBase::learntoption, pow_distance, and shortest_algo.

{
    // Build options.

    declareOption(ol, "knn", &GeodesicDistanceKernel::knn, OptionBase::buildoption,
                  "The number of nearest neighbors considered.");

    declareOption(ol, "distance_kernel", &GeodesicDistanceKernel::distance_kernel, OptionBase::buildoption,
                  "The kernel giving the distance between two points.");

    declareOption(ol, "pow_distance", &GeodesicDistanceKernel::pow_distance, OptionBase::buildoption,
                  "If set to 1, then it will compute the squared geodesic distance.");

    declareOption(ol, "geodesic_file", &GeodesicDistanceKernel::geodesic_file, OptionBase::buildoption,
                  "If provided, the geodesic distances will be saved in this file in binary format.");

    declareOption(ol, "shortest_algo", &GeodesicDistanceKernel::shortest_algo, OptionBase::buildoption,
                  "The algorithm used to compute the geodesic distances:\n"
                  " - floyd     : Floyd's algorithm\n"
                  " - dijkstra  : Dijkstra's algorithm");

    // Learnt options.

    declareOption(ol, "geo_distances", &GeodesicDistanceKernel::geo_distances, OptionBase::learntoption,
                  "The geodesic distances between training points.");

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

Here is the call graph for this function:

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

Reimplemented from PLearn::Kernel.

Definition at line 124 of file GeodesicDistanceKernel.h.

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

Reimplemented from PLearn::Kernel.

Definition at line 82 of file GeodesicDistanceKernel.cc.

real PLearn::GeodesicDistanceKernel::evaluate ( const Vec x1,
const Vec x2 
) const [virtual]

Compute K(x1,x2).

Implements PLearn::Kernel.

Definition at line 164 of file GeodesicDistanceKernel.cc.

References PLearn::dist(), dist_xi_x_sorted1, dist_xi_x_sorted2, distance_kernel, geo_distances, j, knn, PLearn::min(), pow_distance, and PLearn::square().

                                                                        {
    distance_kernel->computeNearestNeighbors(x1, dist_xi_x_sorted1, knn);
    distance_kernel->computeNearestNeighbors(x2, dist_xi_x_sorted2, knn);
    real min = REAL_MAX;
    real dist;
    for (int j = 0; j < knn; j++) {
        for (int k = 0; k < knn; k++) {
            dist = dist_xi_x_sorted1(j,0) + dist_xi_x_sorted2(k,0)
                + geo_distances->get(int(dist_xi_x_sorted1(j,1)), int(dist_xi_x_sorted2(k,1)));
            if (dist < min) {
                min = dist;
            }
        }
    }
    if (pow_distance) {
        return square(min);
    } else {
        return min;
    }
}

Here is the call graph for this function:

real PLearn::GeodesicDistanceKernel::evaluate_i_j ( int  i,
int  j 
) const [virtual]

returns evaluate(data(i),data(j))

Reimplemented from PLearn::Kernel.

Definition at line 188 of file GeodesicDistanceKernel.cc.

References geo_distances, pow_distance, and PLearn::square().

                                                            {
    if (pow_distance) {
        return square(geo_distances->get(i,j));
    } else {
        return geo_distances->get(i,j);
    }
}

Here is the call graph for this function:

real PLearn::GeodesicDistanceKernel::evaluate_i_x ( int  i,
const Vec x,
real  squared_norm_of_x = -1 
) const [virtual]

Return evaluate(data(i),x).

[squared_norm_of_x is just a hint that may allow to speed up computation if it is already known, but it's optional]

Reimplemented from PLearn::Kernel.

Definition at line 199 of file GeodesicDistanceKernel.cc.

References evaluate_i_x_again().

                                                                                           {
    return evaluate_i_x_again(i, x, squared_norm_of_x, true);
}

Here is the call graph for this function:

real PLearn::GeodesicDistanceKernel::evaluate_i_x_again ( int  i,
const Vec x,
real  squared_norm_of_x = -1,
bool  first_time = false 
) const [virtual]

Return evaluate(data(i),x), where x is the same as in the precedent call to this same function (except if 'first_time' is true).

This can be used to speed up successive computations of K(x_i, x) (default version just calls evaluate_i_x).

Reimplemented from PLearn::Kernel.

Definition at line 217 of file GeodesicDistanceKernel.cc.

References computeShortestDistance(), dist_xi_x_sorted, distance_kernel, knn, pow_distance, and PLearn::square().

Referenced by evaluate_i_x().

                                                                                                                  {
    if (first_time) {
        distance_kernel->computeNearestNeighbors(x, dist_xi_x_sorted, knn);
    }
    if (pow_distance) {
        return square(computeShortestDistance(i, dist_xi_x_sorted));
    } else {
        return computeShortestDistance(i, dist_xi_x_sorted);
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

real PLearn::GeodesicDistanceKernel::evaluate_i_x_from_distances ( int  i,
const Mat distances_xi_x_sorted 
) const [virtual]

Evaluate K(x_i,x) where x is not given explicitly, but only by the (sorted and non-geodesic) distances to all training points.

Definition at line 206 of file GeodesicDistanceKernel.cc.

References computeShortestDistance(), pow_distance, and PLearn::square().

                                                                                                      {
    if (pow_distance) {
        return square(computeShortestDistance(i, distances_xi_x_sorted));
    } else {
        return computeShortestDistance(i, distances_xi_x_sorted);
    }
}

Here is the call graph for this function:

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

Reimplemented from PLearn::Object.

Definition at line 82 of file GeodesicDistanceKernel.cc.

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

Reimplemented from PLearn::Object.

Definition at line 82 of file GeodesicDistanceKernel.cc.

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

Reimplemented from PLearn::Object.

Definition at line 82 of file GeodesicDistanceKernel.cc.

void PLearn::GeodesicDistanceKernel::makeDeepCopyFromShallowCopy ( CopiesMap copies) [virtual]
void PLearn::GeodesicDistanceKernel::setDataForKernelMatrix ( VMat  the_data) [virtual]

Overridden to precompute inter-points geodesic distance.

Reimplemented from PLearn::Kernel.

Definition at line 244 of file GeodesicDistanceKernel.cc.

References PLearn::TVec< T >::append(), PLearn::Kernel::computeKNNeighbourMatrixFromDistanceMatrix(), d, PLearn::dist(), distance_kernel, PLearn::TVec< T >::fill(), PLearn::TMat< T >::fill(), geo_distances, geodesic_file, i, PLearn::PPath::isEmpty(), j, knn, PLearn::TVec< T >::length(), PLearn::VMat::length(), m, PLearn::min(), n, PLearn::Kernel::n_examples, PLERROR, PLearn::Kernel::report_progress, PLearn::Kernel::setDataForKernelMatrix(), shortest_algo, and PLearn::VMat::width().

                                                                 {
    inherited::setDataForKernelMatrix(the_data);
    distance_kernel->setDataForKernelMatrix(the_data);
    int n = n_examples;
    // Check whether we have already compute the geodesic distances.
    if (geo_distances && geo_distances->length() == n && geo_distances->width() == n) {
        return;
    }
    // Compute pair distances.
    Mat distances(n,n);
    distance_kernel->computeGramMatrix(distances);
    // Compute knn - nearest neighbors.
    TMat<int> neighborhoods =
        Kernel::computeKNNeighbourMatrixFromDistanceMatrix(
            distances, knn, true, report_progress != 0);
    // Compute geodesic distance by Floyd or Dijkstra's algorithm.
    Mat geodesic(n,n);
    real big_value = REAL_MAX / 3.0; // To make sure no overflow.
    PP<ProgressBar> pb;
    if (report_progress)
        pb = new ProgressBar("Computing geodesic distances", n);
    if (shortest_algo == "floyd") {
        // First initialize the geodesic distances matrix.
        geodesic.fill(big_value);
        int neighbor;
        real d;
        for (int i = 0; i < n; i++) {
            geodesic(i,i) = 0;
            for (int j = 1; j < knn; j++) {
                neighbor = neighborhoods(i,j);
                d = distances(i, neighbor);
                geodesic(i, neighbor) = d;
                geodesic(neighbor, i) = d;
            }
        }
        // And iterate to find geodesic distances.
        real dist;
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    dist = geodesic(i,k) + geodesic(k,j);
                    if (geodesic(i,j) > dist) {
                        geodesic(i,j) = dist;
                    }
                }
            }
            if (report_progress)
                pb->update(k + 1);
        }
    } else if (shortest_algo == "dijkstra") {
        // First build a symmetric neighborhoods matrix
        // (j is a neighbor of i if it was already a neighbor, or if i was a
        // neighbor of j).
        TVec< TVec<int> > sym_neighborhoods(n);
        int neighb, i;
        for (i = 0; i < n; i++) {
            for (int j = 1; j < knn; j++) {
                neighb = neighborhoods(i, j);
                sym_neighborhoods[i].append(neighb);
                sym_neighborhoods[neighb].append(i);
            }
        }
        Vec d;
        TVec<bool> T(n);
        int t, min, j, m, k;
        real dist;
        for (k = 0; k < n; k++) {
            d = geodesic(k);
            d.fill(big_value);
            d[k] = 0;
            T.fill(true);
            for (i = 0; i < n; i++) {
                min = 0;
                while (!T[min])
                    min++;
                for (m = min + 1; m < n; m++) {
                    if (T[m] && d[m] < d[min]) {
                        min = m;
                    }
                }
                for (j = 0; j < sym_neighborhoods[min].length(); j++) {
                    t = sym_neighborhoods[min][j];
                    if (T[t]) {
                        dist = d[min] + distances(min, t);
                        if (d[t] > dist) {
                            d[t] = dist;
                        }
                    }
                }
                T[min] = false;
            }
            if (report_progress)
                pb->update(k+1);
        }
    } else {
        PLERROR("In GeodesicDistanceKernel::setDataForKernelMatrix - Unknown "
                "value for 'shortest_algo': %s",
                shortest_algo.c_str());
    }
    // Save the result in geo_distances.
    if (geodesic_file.isEmpty()) {
        geo_distances = VMat(geodesic);
    } else {
        // Use a FileVMatrix to save on disk.
        geo_distances = new FileVMatrix(geodesic_file, n, n);
        geo_distances->putMat(0, 0, geodesic);
    }
}

Here is the call graph for this function:


Member Data Documentation

Reimplemented from PLearn::Kernel.

Definition at line 124 of file GeodesicDistanceKernel.h.

Definition at line 60 of file GeodesicDistanceKernel.h.

Referenced by evaluate_i_x_again(), and makeDeepCopyFromShallowCopy().

Used to store data and save memory allocation.

Definition at line 60 of file GeodesicDistanceKernel.h.

Referenced by evaluate(), and makeDeepCopyFromShallowCopy().

Definition at line 60 of file GeodesicDistanceKernel.h.

Referenced by evaluate(), and makeDeepCopyFromShallowCopy().

Definition at line 75 of file GeodesicDistanceKernel.h.

Referenced by declareOptions(), and setDataForKernelMatrix().

Definition at line 78 of file GeodesicDistanceKernel.h.

Referenced by declareOptions(), and setDataForKernelMatrix().


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