PLearn 0.1
|
Kernel for Dynamic Time Warping see sect.4.7 of Rabiner, L. More...
#include <DTWKernel.h>
Public Types | |
typedef pair< pair< int, int > , real > | LocalStep |
LocalStep specifies an (x,y) offset and associated cost (weight) | |
typedef TVec< LocalStep > | LocalPath |
LocalPath is a series of LocalSteps taken in one iteration. | |
Public Member Functions | |
DTWKernel () | |
Default constructor. | |
void | dtw (const Vec &x1, const Vec &x2) const |
Compute all distances and paths (to mutalbe vars) | |
tuple< Mat, Mat, TMat< pair < int, int > > > | remote_dtw (const Vec &x1, const Vec &x2) const |
virtual real | evaluate (const Vec &x1, const Vec &x2) const |
Compute K(x1,x2). | |
virtual string | classname () const |
virtual OptionList & | getOptionList () const |
virtual OptionMap & | getOptionMap () const |
virtual RemoteMethodMap & | getRemoteMethodMap () const |
virtual DTWKernel * | deepCopy (CopiesMap &copies) const |
virtual void | build () |
Post-constructor. | |
virtual void | makeDeepCopyFromShallowCopy (CopiesMap &copies) |
Transforms a shallow copy into a deep copy. | |
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 | |
int | subvec_length |
length of each sub-vec within an example | |
TVec< LocalPath > | local_paths |
allowed local paths (incl. associated costs) | |
string | distance_type |
name of the 'distance' function to use when comparing features (sub-vecs) | |
int | max_time_deviation |
Maximum allowed difference between i and j. | |
Static Public Attributes | |
static StaticInitializer | _static_initializer_ |
Static Protected Member Functions | |
static void | declareOptions (OptionList &ol) |
Declares the class options. | |
static void | declareMethods (RemoteMethodMap &rmm) |
Declare the methods that are remote-callable. | |
Private Types | |
typedef Kernel | inherited |
Private Member Functions | |
void | build_ () |
This does the actual building. | |
Private Attributes | |
Mat | dpoint |
point-to-point distances (pre-alloc'd) | |
Mat | dpath |
path length from (0,0) to (i,j) (pre-alloc'd) | |
TMat< pair< int, int > > | bptrs |
back-pointers of optimal paths (pre-alloc'd) | |
TMat< int > | jbounds |
bounds on j for each i | |
real(* | dist_fn )(const Vec &, const Vec &) |
actual pointer to distance function | |
real | slope_ij_min |
global path constraints calc. | |
real | slope_ji_min |
Kernel for Dynamic Time Warping see sect.4.7 of Rabiner, L.
and Juang, B. 1993 'Fundamentals of Speech Recognition'. Prentice-Hall, Inc.
WARNING: THIS CLASS IS *NOT* THREAD-SAFE (has mutable pre-allocated data members)
Definition at line 55 of file DTWKernel.h.
typedef Kernel PLearn::DTWKernel::inherited [private] |
Reimplemented from PLearn::Kernel.
Definition at line 57 of file DTWKernel.h.
typedef TVec<LocalStep> PLearn::DTWKernel::LocalPath |
LocalPath is a series of LocalSteps taken in one iteration.
Definition at line 69 of file DTWKernel.h.
typedef pair<pair<int, int>, real> PLearn::DTWKernel::LocalStep |
LocalStep specifies an (x,y) offset and associated cost (weight)
Definition at line 66 of file DTWKernel.h.
PLearn::DTWKernel::DTWKernel | ( | ) |
Default constructor.
Definition at line 55 of file DTWKernel.cc.
References local_paths, and PLearn::TVec< T >::push_back().
:subvec_length(-1), local_paths(), distance_type("L2"), max_time_deviation(-1) { /* * default local paths: * (0,1) or (1,0) cost 1. * (1,1) costs 2. */ local_paths.push_back(TVec<LocalStep>(1,make_pair(make_pair(0,1),1.))); local_paths.push_back(TVec<LocalStep>(1,make_pair(make_pair(1,0),1.))); local_paths.push_back(TVec<LocalStep>(1,make_pair(make_pair(1,1),2.))); }
string PLearn::DTWKernel::_classname_ | ( | ) | [static] |
Reimplemented from PLearn::Kernel.
Definition at line 50 of file DTWKernel.cc.
OptionList & PLearn::DTWKernel::_getOptionList_ | ( | ) | [static] |
Reimplemented from PLearn::Kernel.
Definition at line 50 of file DTWKernel.cc.
RemoteMethodMap & PLearn::DTWKernel::_getRemoteMethodMap_ | ( | ) | [static] |
Reimplemented from PLearn::Kernel.
Definition at line 50 of file DTWKernel.cc.
Reimplemented from PLearn::Kernel.
Definition at line 50 of file DTWKernel.cc.
Object * PLearn::DTWKernel::_new_instance_for_typemap_ | ( | ) | [static] |
Reimplemented from PLearn::Object.
Definition at line 50 of file DTWKernel.cc.
StaticInitializer DTWKernel::_static_initializer_ & PLearn::DTWKernel::_static_initialize_ | ( | ) | [static] |
Reimplemented from PLearn::Kernel.
Definition at line 50 of file DTWKernel.cc.
void PLearn::DTWKernel::build | ( | ) | [virtual] |
Post-constructor.
The normal implementation should call simply inherited::build(), then this class's build_(). This method should be callable again at later times, after modifying some option fields to change the "architecture" of the object.
Reimplemented from PLearn::Kernel.
Definition at line 122 of file DTWKernel.cc.
References PLearn::Kernel::build(), and build_().
{ // ### Nothing to add here, simply calls build_ inherited::build(); build_(); }
void PLearn::DTWKernel::build_ | ( | ) | [private] |
This does the actual building.
Reimplemented from PLearn::Kernel.
Definition at line 132 of file DTWKernel.cc.
References PLearn::TVec< T >::begin(), dist_fn, distance_type, PLearn::TVec< T >::end(), PLearn::TVec< T >::first(), i, j, PLearn::L1distance(), PLearn::L2distance(), local_paths, PLERROR, PLearn::powdistance(), slope_ij_min, slope_ji_min, and subvec_length.
Referenced by build().
{ if(subvec_length <= 0) PLERROR("In DTWKernel::build_() : " "subvec_length must be specified before build " "(%d is not a valid value).", subvec_length); //distance function if(distance_type == "L2") dist_fn= L2distance; else if(distance_type == "L1") dist_fn= L1distance; else if(distance_type == "pow2") dist_fn= powdistance; else PLERROR("In DTWKernel::build_() : " "distance_type should be one of: " "'L2', 'L1' or 'pow2' " "('%s' is not a valid value).", distance_type.c_str()); //calc. valid region from local_paths (min/max slope) TVec<LocalPath>::iterator it; TVec<LocalPath>::iterator itbeg= local_paths.begin(); TVec<LocalPath>::iterator itend= local_paths.end(); TVec<LocalStep>::iterator jt; TVec<LocalStep>::iterator jtend; bool first= true; for(it= itbeg; it != itend; ++it) { int i= 0, j= 0; jtend= it->end(); for(jt= it->begin(); jt != jtend; ++jt) { i+= jt->first.first; j+= jt->first.second; } real rij= i; rij/= j; if(rij < slope_ij_min || first) slope_ij_min= rij; real rji= j; rji/= i; if(rji < slope_ji_min || first) slope_ji_min= rji; first= false; } }
string PLearn::DTWKernel::classname | ( | ) | const [virtual] |
Reimplemented from PLearn::Object.
Definition at line 50 of file DTWKernel.cc.
void PLearn::DTWKernel::declareMethods | ( | RemoteMethodMap & | rmm | ) | [static, protected] |
Declare the methods that are remote-callable.
Reimplemented from PLearn::Kernel.
Definition at line 105 of file DTWKernel.cc.
References PLearn::Kernel::_getRemoteMethodMap_(), PLearn::declareMethod(), PLearn::RemoteMethodMap::inherited(), and remote_dtw().
{ rmm.inherited(inherited::_getRemoteMethodMap_()); declareMethod( rmm, "dtw", &DTWKernel::remote_dtw, (BodyDoc("Calc. DTW on two feature vectors\n"), ArgDoc("x1","first vector"), ArgDoc("x2","second vector"), RetDoc ("dpath, dpoint, bptrs"))); }
void PLearn::DTWKernel::declareOptions | ( | OptionList & | ol | ) | [static, protected] |
Declares the class options.
Reimplemented from PLearn::Kernel.
Definition at line 74 of file DTWKernel.cc.
References PLearn::OptionBase::buildoption, PLearn::declareOption(), PLearn::Kernel::declareOptions(), distance_type, local_paths, max_time_deviation, and subvec_length.
{ declareOption(ol, "subvec_length", &DTWKernel::subvec_length, OptionBase::buildoption, "length of each sub-vec within an example"); declareOption(ol, "local_paths", &DTWKernel::local_paths, OptionBase::buildoption, "Specifies local path constraints and weights. " "In each path, steps should be listed from " "the ending point to the starting point." "e.g. if a path can start at (0,0), go to (1,1) " "and then end at (2,1), it should be listed as: " "[((1,0),0.5), ((1,1),0.5)] where '0.5' are weights"); declareOption(ol, "distance_type", &DTWKernel::distance_type, OptionBase::buildoption, "Name of the 'distance' function to use " "when comparing features (sub-vecs).\n" "one of: 'L2' : sqrt{sum{(x-y)^2}}\n" " 'L1' : sum{|x-y|}\n" " 'pow2': sum{(x-y)^2}\n"); declareOption(ol, "max_time_deviation", &DTWKernel::max_time_deviation, OptionBase::buildoption, "Maximum allowed difference between i and j; " "negative means no limit."); inherited::declareOptions(ol); }
static const PPath& PLearn::DTWKernel::declaringFile | ( | ) | [inline, static] |
Reimplemented from PLearn::Kernel.
Definition at line 102 of file DTWKernel.h.
:
//##### Protected Options ###############################################
Reimplemented from PLearn::Kernel.
Definition at line 50 of file DTWKernel.cc.
Compute all distances and paths (to mutalbe vars)
***///***///***///
***///***///***///
Definition at line 184 of file DTWKernel.cc.
References PLearn::TVec< T >::begin(), bptrs, PLearn::dist(), dist_fn, dpath, dpoint, PLearn::TVec< T >::end(), PLearn::TVec< T >::first(), i, j, jbounds, PLearn::TVec< T >::length(), local_paths, PLearn::max(), max_time_deviation, PLearn::min(), mn, PLASSERT, PLERROR, PLearn::TMat< T >::resize(), slope_ij_min, slope_ji_min, PLearn::TVec< T >::subVec(), and subvec_length.
Referenced by evaluate(), and remote_dtw().
{ PLASSERT(x1.length() % subvec_length == 0); PLASSERT(x2.length() % subvec_length == 0); int n1= x1.length() / subvec_length;// n1 features TVec<Vec> subvecs1(n1); for(int i= 0; i < n1; ++i) subvecs1[i]= x1.subVec(i*subvec_length, subvec_length); int n2= x2.length() / subvec_length;// n2 features TVec<Vec> subvecs2(n2); for(int j= 0; j < n2; ++j) subvecs2[j]= x2.subVec(j*subvec_length, subvec_length); //init: calc. point-to-point distances // also pre-calc. bounds on j for each i int i,j,jmin,jmax; real jmin0, jmax0; dpoint.resize(n1,n2); jbounds.resize(n1,2); for(i= 0; i < n1; ++i) { if(slope_ij_min == 0.) {// avoid div by zero... especially if 0/0 jmin0= 0.; jmax0= n2; } else { jmin0= static_cast<real>(i+1-n1)/slope_ij_min + n2 - 1; jmax0= static_cast<real>(i)/slope_ij_min; } jmin= static_cast<int>(ceil(max(jmin0, slope_ji_min * i))); jmax= static_cast<int>( floor(min(jmax0, slope_ji_min*(i-n1+1) + n2 - 1))); if(max_time_deviation >= 0) {// max abs. delta time (if >= 0) jmin= max(jmin, i - max_time_deviation); jmax= min(jmax, i + max_time_deviation); } jbounds(i,0)= jmin; jbounds(i,1)= jmax; /* * TODO: make sure this is OK for exotic local_paths * (also see: option desc. for local_paths) */ for(j= jmin; j <= jmax; ++j) dpoint(i,j)= dist_fn(subvecs1[i], subvecs2[j]); } //recurs: calc. path distances dpath.resize(n1,n2); bptrs.resize(n1,n2); dpath(0,0)= dpoint(0,0); //starting point real mn; //min. found at each step int ai, aj; //'actual' coords when following a local path pair<int,int> scoords; //coords for a step real dist; //'distance' to a given point TVec<LocalPath>::iterator it; TVec<LocalPath>::iterator itbeg= local_paths.begin(); TVec<LocalPath>::iterator itend= local_paths.end(); TVec<LocalStep>::iterator jt; TVec<LocalStep>::iterator jtend; bool path_ok; //is this path valid? bool some_path_ok; //is there any valid path to those coords? for(i= 0; i < n1; ++i) { jmin= jbounds(i,0); if(i==0) jmin= max(1,jmin);//skip (0,0), already calc. jmax= jbounds(i,1); for(j= jmin; j <= jmax; ++j) { some_path_ok= false; mn= REAL_MAX; for(it= itbeg; it != itend; ++it) {// for all local paths path_ok= true; ai= i; aj= j; dist= 0.; jtend= it->end(); for(jt= it->begin(); jt != jtend; ++jt) {// for each step in the local path dist+= dpoint(ai,aj) * jt->second; scoords= jt->first; ai-= scoords.first; aj-= scoords.second; if(ai < 0 || aj < 0) { path_ok= false; break; } } if(ai < 0 || aj < jbounds(ai,0) || aj > jbounds(ai,1)) path_ok= false; if(path_ok) { dist+= dpath(ai,aj);//add dist. to beg. of path if(dist < mn || !some_path_ok) { mn= dist; bptrs(i,j)= make_pair(ai,aj); some_path_ok= true; } } } dpath(i,j)= mn;//will be REAL_MAX if no path... but should not happen if(!some_path_ok && i==n1-1 && j==n2-1) PLERROR("In DTWKernel::dtw : can't reach end of path! " "Check your local_paths, they may be inconsistent."); } } }
Compute K(x1,x2).
Implements PLearn::Kernel.
Definition at line 314 of file DTWKernel.cc.
References dpath, dtw(), and PLearn::TMat< T >::lastElement().
OptionList & PLearn::DTWKernel::getOptionList | ( | ) | const [virtual] |
Reimplemented from PLearn::Object.
Definition at line 50 of file DTWKernel.cc.
OptionMap & PLearn::DTWKernel::getOptionMap | ( | ) | const [virtual] |
Reimplemented from PLearn::Object.
Definition at line 50 of file DTWKernel.cc.
RemoteMethodMap & PLearn::DTWKernel::getRemoteMethodMap | ( | ) | const [virtual] |
Reimplemented from PLearn::Object.
Definition at line 50 of file DTWKernel.cc.
void PLearn::DTWKernel::makeDeepCopyFromShallowCopy | ( | CopiesMap & | copies | ) | [virtual] |
Transforms a shallow copy into a deep copy.
Reimplemented from PLearn::Kernel.
Definition at line 323 of file DTWKernel.cc.
References bptrs, PLearn::deepCopyField(), dpath, dpoint, jbounds, local_paths, and PLearn::Kernel::makeDeepCopyFromShallowCopy().
{ inherited::makeDeepCopyFromShallowCopy(copies); deepCopyField(local_paths, copies); deepCopyField(dpoint, copies); deepCopyField(dpath, copies); deepCopyField(bptrs, copies); deepCopyField(jbounds, copies); }
Reimplemented from PLearn::Kernel.
Definition at line 102 of file DTWKernel.h.
TMat<pair<int,int> > PLearn::DTWKernel::bptrs [mutable, private] |
back-pointers of optimal paths (pre-alloc'd)
Definition at line 138 of file DTWKernel.h.
Referenced by dtw(), makeDeepCopyFromShallowCopy(), and remote_dtw().
real(* PLearn::DTWKernel::dist_fn)(const Vec &, const Vec &) [private] |
actual pointer to distance function
Definition at line 144 of file DTWKernel.h.
name of the 'distance' function to use when comparing features (sub-vecs)
Definition at line 80 of file DTWKernel.h.
Referenced by build_(), and declareOptions().
Mat PLearn::DTWKernel::dpath [mutable, private] |
path length from (0,0) to (i,j) (pre-alloc'd)
Definition at line 135 of file DTWKernel.h.
Referenced by dtw(), evaluate(), makeDeepCopyFromShallowCopy(), and remote_dtw().
Mat PLearn::DTWKernel::dpoint [mutable, private] |
point-to-point distances (pre-alloc'd)
Definition at line 132 of file DTWKernel.h.
Referenced by dtw(), makeDeepCopyFromShallowCopy(), and remote_dtw().
TMat<int> PLearn::DTWKernel::jbounds [mutable, private] |
bounds on j for each i
Definition at line 141 of file DTWKernel.h.
Referenced by dtw(), and makeDeepCopyFromShallowCopy().
allowed local paths (incl. associated costs)
Definition at line 77 of file DTWKernel.h.
Referenced by build_(), declareOptions(), dtw(), DTWKernel(), and makeDeepCopyFromShallowCopy().
Maximum allowed difference between i and j.
Definition at line 83 of file DTWKernel.h.
Referenced by declareOptions(), and dtw().
real PLearn::DTWKernel::slope_ij_min [private] |
global path constraints calc.
from local_paths min. and max. slope
Definition at line 148 of file DTWKernel.h.
real PLearn::DTWKernel::slope_ji_min [private] |
Definition at line 149 of file DTWKernel.h.
length of each sub-vec within an example
Definition at line 74 of file DTWKernel.h.
Referenced by build_(), declareOptions(), and dtw().