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

Kernel for Dynamic Time Warping see sect.4.7 of Rabiner, L. More...

#include <DTWKernel.h>

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

List of all members.

Public Types

typedef pair< pair< int, int >
, real
LocalStep
 LocalStep specifies an (x,y) offset and associated cost (weight)
typedef TVec< LocalStepLocalPath
 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 OptionListgetOptionList () const
virtual OptionMapgetOptionMap () const
virtual RemoteMethodMapgetRemoteMethodMap () const
virtual DTWKerneldeepCopy (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 PPathdeclaringFile ()

Public Attributes

int subvec_length
 length of each sub-vec within an example
TVec< LocalPathlocal_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< intjbounds
 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

Detailed Description

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.


Member Typedef Documentation

Reimplemented from PLearn::Kernel.

Definition at line 57 of file DTWKernel.h.

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.


Constructor & Destructor Documentation

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.)));
}

Here is the call graph for this function:


Member Function Documentation

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.

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

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_();
}

Here is the call graph for this function:

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;
    }

}

Here is the call graph for this function:

Here is the caller graph for this function:

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")));
}

Here is the call graph for this function:

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);
}

Here is the call graph for this function:

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

Reimplemented from PLearn::Kernel.

Definition at line 102 of file DTWKernel.h.

:
    //#####  Protected Options  ###############################################
DTWKernel * PLearn::DTWKernel::deepCopy ( CopiesMap copies) const [virtual]

Reimplemented from PLearn::Kernel.

Definition at line 50 of file DTWKernel.cc.

void PLearn::DTWKernel::dtw ( const Vec x1,
const Vec x2 
) const

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.");
        }
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

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

Compute K(x1,x2).

Implements PLearn::Kernel.

Definition at line 314 of file DTWKernel.cc.

References dpath, dtw(), and PLearn::TMat< T >::lastElement().

{
    dtw(x1, x2);
    return dpath.lastElement();
}

Here is the call graph for this function:

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

Here is the call graph for this function:

tuple< Mat, Mat, TMat< pair< int, int > > > PLearn::DTWKernel::remote_dtw ( const Vec x1,
const Vec x2 
) const

Definition at line 305 of file DTWKernel.cc.

References bptrs, dpath, dpoint, and dtw().

Referenced by declareMethods().

{
    dtw(x1,x2);
    return make_tuple(dpath, dpoint, bptrs);

}

Here is the call graph for this function:

Here is the caller graph for this function:


Member Data Documentation

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.

Referenced by build_(), and dtw().

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

global path constraints calc.

from local_paths min. and max. slope

Definition at line 148 of file DTWKernel.h.

Referenced by build_(), and dtw().

Definition at line 149 of file DTWKernel.h.

Referenced by build_(), and dtw().

length of each sub-vec within an example

Definition at line 74 of file DTWKernel.h.

Referenced by build_(), declareOptions(), and dtw().


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