RefineClusterer Class Reference

Collaboration diagram for RefineClusterer:

Classes
struct	point_info

Public Types
typedef int32	LocalInt
typedef uint_smaller	ClustIndexInt

Public Member Functions
	RefineClusterer (const std::vector< Clusterable *> &points, std::vector< Clusterable *> *clusters, std::vector< int32 > *assignments, RefineClustersOptions cfg)
BaseFloat	Refine ()

Private Member Functions
void	InitPoint (int32 point)
void	InitPoints ()
void	Iterate ()
void	MovePoint (int32 point, int32 new_index)
void	UpdateClust (int32 clust)
void	ProcessPoint (int32 point)
void	UpdateInfo (int32 point, int32 idx)
point_info &	GetInfo (int32 point, int32 idx)

Private Attributes
const std::vector< Clusterable * > &	points_
std::vector< Clusterable * > *	clusters_
std::vector< int32 > *	assignments_
std::vector< point_info >	info_
std::vector< ClustIndexInt >	my_clust_index_
std::vector< LocalInt >	clust_time_
std::vector< BaseFloat >	clust_objf_
BaseFloat	ans_
int32	num_clust_
int32	num_points_
int32	t_
RefineClustersOptions	cfg_

Detailed Description

Definition at line 686 of file cluster-utils.cc.

Member Typedef Documentation

ClustIndexInt

typedef uint_smaller ClustIndexInt

Definition at line 693 of file cluster-utils.cc.

LocalInt

typedef int32 LocalInt

Definition at line 692 of file cluster-utils.cc.

Constructor & Destructor Documentation

RefineClusterer()

RefineClusterer ( const std::vector< Clusterable *> &  points, std::vector< Clusterable *> *  clusters, std::vector< int32 > *  assignments, RefineClustersOptions  cfg  )

inline

Definition at line 695 of file cluster-utils.cc.

References BottomUpClusterer::ans_, BottomUpClusterer::clusters_, rnnlm::i, KALDI_ASSERT, and BottomUpClusterer::points_.

      : points_(points), clusters_(clusters), assignments_(assignments),
        cfg_(cfg) {
    KALDI_ASSERT(cfg_.top_n >= 2);
    num_points_ = points_.size();
    num_clust_ = static_cast<int32> (clusters->size());

    // so can fit clust-id in LocalInt
    if (cfg_.top_n > (int32) num_clust_) cfg_.top_n
        = static_cast<int32> (num_clust_);
    KALDI_ASSERT(cfg_.top_n == static_cast<int32>(static_cast<ClustIndexInt>(cfg_.top_n)));
    t_ = 0;
    my_clust_index_.resize(num_points_);
    // will set all PointInfo's to 0 too (they will be up-to-date).
    clust_time_.resize(num_clust_, 0);
    clust_objf_.resize(num_clust_);
    for (int32 i = 0; i < num_clust_; i++)
      clust_objf_[i] = (*clusters_)[i]->Objf();
    info_.resize(num_points_ * cfg_.top_n);
    ans_ = 0;
    InitPoints();
  }

Member Function Documentation

GetInfo()

point_info& GetInfo ( int32  point, int32  idx  )

inlineprivate

Definition at line 868 of file cluster-utils.cc.

References rnnlm::i, KALDI_ASSERT, and KALDI_PARANOID_ASSERT.

                                              {
    KALDI_ASSERT(point < num_points_ && idx < cfg_.top_n);
    int32 i = point*cfg_.top_n + idx;
    KALDI_PARANOID_ASSERT(i < static_cast<int32>(info_.size()));
    return info_[i];
  }

InitPoint()

void InitPoint ( int32  point )

inlineprivate

Definition at line 728 of file cluster-utils.cc.

References Clusterable::Add(), RefineClusterer::point_info::clust, Clusterable::Copy(), RefineClusterer::point_info::objf, BottomUpClusterer::points_, and RefineClusterer::point_info::time.

                              {
    // Find closest clusters to this point.
    // distances are really negated objf changes, ignoring terms that don't vary with the "other" cluster.

    std::vector<std::pair<BaseFloat, LocalInt> > distances;
    distances.reserve(num_clust_-1);
    int32 my_clust = (*assignments_)[point];
    Clusterable *point_cl = points_[point];

    for (int32 clust = 0;clust < num_clust_;clust++) {
      if (clust != my_clust) {
        Clusterable *tmp = (*clusters_)[clust]->Copy();
        tmp->Add(*point_cl);
        BaseFloat other_clust_objf = clust_objf_[clust];
        BaseFloat other_clust_plus_me_objf = (*clusters_)[clust]->ObjfPlus(* (points_[point]));

        BaseFloat distance = other_clust_objf-other_clust_plus_me_objf;  // negated delta-objf, with only "varying" terms.
        distances.push_back(std::make_pair(distance, (LocalInt)clust));
        delete tmp;
      }
    }
    if ((cfg_.top_n-1-1) >= 0) {
      std::nth_element(distances.begin(), distances.begin()+(cfg_.top_n-1-1), distances.end());
    }
    // top_n-1 is the # of elements we want to retain.  -1 because we need the iterator
    // that points to the end of that range (i.e. not potentially off the end of the array).

    for (int32 index = 0;index < cfg_.top_n-1;index++) {
      point_info &info = GetInfo(point, index);
      int32 clust = distances[index].second;
      info.clust = clust;
      BaseFloat distance = distances[index].first;
      BaseFloat other_clust_objf = clust_objf_[clust];
      BaseFloat other_clust_plus_me_objf = -(distance - other_clust_objf);
      info.objf = other_clust_plus_me_objf;
      info.time = 0;
    }
    // now put the last element in, which is my current cluster.
    point_info &info = GetInfo(point, cfg_.top_n-1);
    info.clust = my_clust;
    info.time = 0;
    info.objf = (*clusters_)[my_clust]->ObjfMinus(*(points_[point]));
    my_clust_index_[point] = cfg_.top_n-1;
  }

InitPoints()

void InitPoints ( )

inlineprivate

Definition at line 772 of file cluster-utils.cc.

                    {
    // finds, for each point, the closest cfg_.top_n clusters (including its own cluster).
    // this may be the most time-consuming step of the algorithm.
    for (int32 p = 0;p < num_points_;p++) InitPoint(p);
  }

Iterate()

void Iterate ( )

inlineprivate

Definition at line 777 of file cluster-utils.cc.

References KALDI_WARN.

                 {
    int32 iter, num_iters = cfg_.num_iters;
    for (iter = 0;iter < num_iters;iter++) {
      int32 cur_t = t_;
      for (int32 point = 0;point < num_points_;point++) {
        if (t_+1 == 0) {
          KALDI_WARN << "Stopping iterating at int32 moves";
          return;  // once we use up all time points, must return-- this
                  // should rarely happen as int32 is large.
        }
        ProcessPoint(point);
      }
      if (t_ == cur_t) break;  // nothing changed so we converged.
    }
  }

MovePoint()

void MovePoint ( int32  point, int32  new_index  )

inlineprivate

Definition at line 792 of file cluster-utils.cc.

References BottomUpClusterer::assignments_, RefineClusterer::point_info::clust, KALDI_ASSERT, and BottomUpClusterer::points_.

                                               {
    // move point to a different cluster.
    t_++;
    int32 old_index = my_clust_index_[point];  // index into info
    // array corresponding to current cluster.
    KALDI_ASSERT(new_index < cfg_.top_n  && new_index != old_index);
    point_info &old_info = GetInfo(point, old_index),
        &new_info = GetInfo(point, new_index);
    my_clust_index_[point] = new_index;  // update to new index.

    int32 old_clust = old_info.clust, new_clust = new_info.clust;
    KALDI_ASSERT( (*assignments_)[point] == old_clust);
    (*assignments_)[point] = new_clust;
    (*clusters_)[old_clust]->Sub( *(points_[point]) );
    (*clusters_)[new_clust]->Add( *(points_[point]) );
    UpdateClust(old_clust);
    UpdateClust(new_clust);
  }

ProcessPoint()

void ProcessPoint ( int32  point )

inlineprivate

Definition at line 815 of file cluster-utils.cc.

References BottomUpClusterer::ans_, RefineClusterer::point_info::clust, KALDI_ASSERT, and RefineClusterer::point_info::objf.

                                 {
    // note: calling code uses the fact
    // that it only ever increases t_ by one.
    KALDI_ASSERT(point < num_points_);
    // (1) Make sure own-cluster like is updated.
    int32 self_index = my_clust_index_[point];  // index <cfg_.top_n of own cluster.
    point_info &self_info = GetInfo(point, self_index);
    int32 self_clust = self_info.clust;  // cluster index of own cluster.
    KALDI_ASSERT(self_index < cfg_.top_n);
    UpdateInfo(point, self_index);

    float own_clust_objf = clust_objf_[self_clust];
    float own_clust_minus_me_objf = self_info.objf;  // objf of own cluster minus self.
    // Now check the other "close" clusters and see if we want to move there.
           for (int32 index = 0;index < cfg_.top_n;index++) {
      if (index != self_index) {
        UpdateInfo(point, index);
        point_info &other_info = GetInfo(point, index);
        BaseFloat other_clust_objf = clust_objf_[other_info.clust];
        BaseFloat other_clust_plus_me_objf = other_info.objf;
        BaseFloat impr = other_clust_plus_me_objf + own_clust_minus_me_objf
            - other_clust_objf - own_clust_objf;
        if (impr > 0) {  // better to switch...
          ans_ += impr;
          MovePoint(point, index);
          return;  // the stuff we precomputed at the top is invalidated now, and it's
          // easiest just to wait till next time we visit this point.
        }
      }
    }
  }

Refine()

BaseFloat Refine ( )

inline

Definition at line 721 of file cluster-utils.cc.

References BottomUpClusterer::ans_.

Referenced by kaldi::RefineClusters().

                     {
    if (cfg_.top_n <= 1) return 0.0;  // nothing to do.
    Iterate();
    return ans_;
  }

UpdateClust()

void UpdateClust ( int32  clust )

inlineprivate

Definition at line 810 of file cluster-utils.cc.

References KALDI_ASSERT.

                                {
    KALDI_ASSERT(clust < num_clust_);
    clust_objf_[clust] = (*clusters_)[clust]->Objf();
    clust_time_[clust] = t_;
  }

UpdateInfo()

void UpdateInfo ( int32  point, int32  idx  )

inlineprivate

Definition at line 847 of file cluster-utils.cc.

References Clusterable::Add(), RefineClusterer::point_info::clust, Clusterable::Copy(), Clusterable::Objf(), RefineClusterer::point_info::objf, BottomUpClusterer::points_, Clusterable::Sub(), and RefineClusterer::point_info::time.

                                          {
    point_info &pinfo = GetInfo(point, idx);
    if (pinfo.time < clust_time_[pinfo.clust]) {  // it's not up-to-date...
      Clusterable *tmp_cl = (*clusters_)[pinfo.clust]->Copy();
      if (idx == my_clust_index_[point]) {
        tmp_cl->Sub( *(points_[point]) );
      } else{
        tmp_cl->Add( *(points_[point]) );
      }
      pinfo.time = t_;
      pinfo.objf = tmp_cl->Objf();
      delete tmp_cl;
    }
  }

Member Data Documentation

ans_

BaseFloat ans_

private

Definition at line 886 of file cluster-utils.cc.

assignments_

std::vector<int32>* assignments_

private

Definition at line 877 of file cluster-utils.cc.

cfg_

RefineClustersOptions cfg_

private

Definition at line 891 of file cluster-utils.cc.

clust_objf_

std::vector<BaseFloat> clust_objf_

private

Definition at line 884 of file cluster-utils.cc.

clust_time_

std::vector<LocalInt> clust_time_

private

Definition at line 883 of file cluster-utils.cc.

clusters_

std::vector<Clusterable*>* clusters_

private

Definition at line 876 of file cluster-utils.cc.

info_

std::vector<point_info> info_

private

Definition at line 879 of file cluster-utils.cc.

my_clust_index_

std::vector<ClustIndexInt> my_clust_index_

private

Definition at line 880 of file cluster-utils.cc.

num_clust_

int32 num_clust_

private

Definition at line 888 of file cluster-utils.cc.

num_points_

int32 num_points_

private

Definition at line 889 of file cluster-utils.cc.

points_

const std::vector<Clusterable*>& points_

private

Definition at line 875 of file cluster-utils.cc.

t_

int32 t_

private

Definition at line 890 of file cluster-utils.cc.

---

The documentation for this class was generated from the following file:

• tree/cluster-utils.cc