PLearn 0.1
|
#include <GeodesicDistanceKernel.h>
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 OptionList & | getOptionList () const |
virtual OptionMap & | getOptionMap () const |
virtual RemoteMethodMap & | getRemoteMethodMap () const |
virtual GeodesicDistanceKernel * | deepCopy (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 PPath & | declaringFile () |
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 |
Definition at line 52 of file GeodesicDistanceKernel.h.
typedef Kernel PLearn::GeodesicDistanceKernel::inherited [private] |
Reimplemented from PLearn::Kernel.
Definition at line 57 of file GeodesicDistanceKernel.h.
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_(); }
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.
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_().
{ inherited::build(); build_(); }
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().
{ }
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)); }
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; }
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); }
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.
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; } }
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); } }
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); }
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); } }
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); } }
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] |
Transforms a shallow copy into a deep copy.
Reimplemented from PLearn::Kernel.
Definition at line 231 of file GeodesicDistanceKernel.cc.
References PLearn::deepCopyField(), dist_xi_x_sorted, dist_xi_x_sorted1, dist_xi_x_sorted2, distance_kernel, geo_distances, and PLearn::Kernel::makeDeepCopyFromShallowCopy().
{ inherited::makeDeepCopyFromShallowCopy(copies); deepCopyField(dist_xi_x_sorted1, copies); deepCopyField(dist_xi_x_sorted2, copies); deepCopyField(dist_xi_x_sorted, copies); deepCopyField(distance_kernel, copies); deepCopyField(geo_distances, copies); }
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); } }
Reimplemented from PLearn::Kernel.
Definition at line 124 of file GeodesicDistanceKernel.h.
Mat PLearn::GeodesicDistanceKernel::dist_xi_x_sorted [mutable, private] |
Definition at line 60 of file GeodesicDistanceKernel.h.
Referenced by evaluate_i_x_again(), and makeDeepCopyFromShallowCopy().
Mat PLearn::GeodesicDistanceKernel::dist_xi_x_sorted1 [mutable, private] |
Used to store data and save memory allocation.
Definition at line 60 of file GeodesicDistanceKernel.h.
Referenced by evaluate(), and makeDeepCopyFromShallowCopy().
Mat PLearn::GeodesicDistanceKernel::dist_xi_x_sorted2 [mutable, private] |
Definition at line 60 of file GeodesicDistanceKernel.h.
Referenced by evaluate(), and makeDeepCopyFromShallowCopy().
Definition at line 74 of file GeodesicDistanceKernel.h.
Referenced by declareOptions(), evaluate(), evaluate_i_x_again(), GeodesicDistanceKernel(), makeDeepCopyFromShallowCopy(), and setDataForKernelMatrix().
Definition at line 79 of file GeodesicDistanceKernel.h.
Referenced by computeNearestGeodesicNeighbour(), declareOptions(), evaluate(), evaluate_i_j(), makeDeepCopyFromShallowCopy(), and setDataForKernelMatrix().
Definition at line 75 of file GeodesicDistanceKernel.h.
Referenced by declareOptions(), and setDataForKernelMatrix().
Definition at line 76 of file GeodesicDistanceKernel.h.
Referenced by computeNearestGeodesicNeighbour(), declareOptions(), evaluate(), evaluate_i_x_again(), and setDataForKernelMatrix().
Definition at line 77 of file GeodesicDistanceKernel.h.
Referenced by declareOptions(), evaluate(), evaluate_i_j(), evaluate_i_x_again(), and evaluate_i_x_from_distances().
Definition at line 78 of file GeodesicDistanceKernel.h.
Referenced by declareOptions(), and setDataForKernelMatrix().