|
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().
1.7.4