build-tree-utils.h

Go to the documentation of this file.

// tree/build-tree-utils.h

// Copyright 2009-2011  Microsoft Corporation

// See ../../COPYING for clarification regarding multiple authors
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//  http://www.apache.org/licenses/LICENSE-2.0
//
// THIS CODE IS PROVIDED *AS IS* BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
// KIND, EITHER EXPRESS OR IMPLIED, INCLUDING WITHOUT LIMITATION ANY IMPLIED
// WARRANTIES OR CONDITIONS OF TITLE, FITNESS FOR A PARTICULAR PURPOSE,
// MERCHANTABLITY OR NON-INFRINGEMENT.
// See the Apache 2 License for the specific language governing permissions and
// limitations under the License.

#ifndef KALDI_TREE_BUILD_TREE_UTILS_H_
#define KALDI_TREE_BUILD_TREE_UTILS_H_

#include "tree/build-tree-questions.h"

// build-tree-questions.h needed for this typedef:
// typedef std::vector<std::pair<EventType, Clusterable*> > BuildTreeStatsType;
// and for other #includes.

namespace kaldi {





void DeleteBuildTreeStats(BuildTreeStatsType *stats);

void WriteBuildTreeStats(std::ostream &os, bool binary,
                         const BuildTreeStatsType &stats);

void ReadBuildTreeStats(std::istream &is, bool binary,
                        const Clusterable &example, BuildTreeStatsType *stats);

bool PossibleValues(EventKeyType key, const BuildTreeStatsType &stats,
                    std::vector<EventValueType> *ans);


void SplitStatsByMap(const BuildTreeStatsType &stats_in, const EventMap &e,
                     std::vector<BuildTreeStatsType> *stats_out);

void SplitStatsByKey(const BuildTreeStatsType &stats_in, EventKeyType key,
                     std::vector<BuildTreeStatsType> *stats_out);


bool ConvertStats(int32 oldN, int32 oldP, int32 newN, int32 newP,
                  BuildTreeStatsType *stats);


void FilterStatsByKey(const BuildTreeStatsType &stats_in,
                      EventKeyType key,
                      std::vector<EventValueType> &values,
                      bool include_if_present,  // true-> retain only if in "values",
                      // false-> retain only if not in "values".
                      BuildTreeStatsType *stats_out);


Clusterable *SumStats(const BuildTreeStatsType &stats_in);

BaseFloat SumNormalizer(const BuildTreeStatsType &stats_in);

BaseFloat SumObjf(const BuildTreeStatsType &stats_in);


void SumStatsVec(const std::vector<BuildTreeStatsType> &stats_in, std::vector<Clusterable*> *stats_out);

BaseFloat ObjfGivenMap(const BuildTreeStatsType &stats_in, const EventMap &e);


void FindAllKeys(const BuildTreeStatsType &stats, AllKeysType keys_type,
                 std::vector<EventKeyType> *keys);




inline EventMap *TrivialTree(int32 *num_leaves) {
  KALDI_ASSERT(*num_leaves == 0);  // in envisaged usage.
  return new ConstantEventMap( (*num_leaves)++ );
}

EventMap *DoTableSplit(const EventMap &orig, EventKeyType key,
                       const BuildTreeStatsType &stats, int32 *num_leaves);


EventMap *DoTableSplitMultiple(const EventMap &orig,
                               const std::vector<EventKeyType> &keys,
                               const BuildTreeStatsType &stats,
                               int32 *num_leaves);


// The function returns the #leaves we combined.  The same leaf-ids of the leaves being clustered
// will be used for the clustered leaves (but other than that there is no special rule which
// leaf-ids should be used at output).
// It outputs the mapping for leaves, in "mapping", which may be empty at the start
// but may also contain mappings for other parts of the tree, which must contain
// disjoint leaves from this part.  This is so that Cluster can
// be called multiple times for sub-parts of the tree (with disjoint sets of leaves),
// e.g. if we want to avoid sharing across phones.  Afterwards you can use Copy function
// of EventMap to apply the mapping, i.e. call e_in.Copy(mapping) to get the new map.
// Note that the application of Cluster creates gaps in the leaves.  You should then
// call RenumberEventMap(e_in.Copy(mapping), num_leaves).
// *If you only want to cluster a subset of the leaves (e.g. just non-silence, or just
// a particular phone, do this by providing a set of "stats" that correspond to just
// this subset of leaves*.  Leaves with no stats will not be clustered.
// See build-tree.cc for an example of usage.
int ClusterEventMapGetMapping(const EventMap &e_in, const BuildTreeStatsType &stats,
                              BaseFloat thresh, std::vector<EventMap*> *mapping);

EventMap *ClusterEventMap(const EventMap &e_in, const BuildTreeStatsType &stats,
                          BaseFloat thresh, int32 *num_removed);

EventMap *ClusterEventMapRestrictedByKeys(const EventMap &e_in,
                                          const BuildTreeStatsType &stats,
                                          BaseFloat thresh,
                                          const std::vector<EventKeyType> &keys,
                                          int32 *num_removed);


EventMap *ClusterEventMapRestrictedByMap(const EventMap &e_in,
                                         const BuildTreeStatsType &stats,
                                         BaseFloat thresh,
                                         const EventMap &e_restrict,
                                         int32 *num_removed);


EventMap *ClusterEventMapToNClustersRestrictedByMap(
    const EventMap &e_in,
    const BuildTreeStatsType &stats,
    int32 num_clusters,
    const EventMap &e_restrict,
    int32 *num_removed);

EventMap *RenumberEventMap(const EventMap &e_in, int32 *num_leaves);

EventMap *MapEventMapLeaves(const EventMap &e_in,
                            const std::vector<int32> &mapping);



EventMap *ShareEventMapLeaves(const EventMap &e_in, EventKeyType key,
                              std::vector<std::vector<EventValueType> > &values,
                              int32 *num_leaves);



EventMap *SplitDecisionTree(const EventMap &orig,
                            const BuildTreeStatsType &stats,
                            Questions &qcfg,
                            BaseFloat thresh,
                            int32 max_leaves,  // max_leaves<=0 -> no maximum.
                            int32 *num_leaves,
                            BaseFloat *objf_impr_out,
                            BaseFloat *smallest_split_change_out);

void CreateRandomQuestions(const BuildTreeStatsType &stats, int32 num_quest, Questions *cfg_out);


BaseFloat FindBestSplitForKey(const BuildTreeStatsType &stats,
                              const Questions &qcfg,
                              EventKeyType key,
                              std::vector<EventValueType> *yes_set);



EventMap *GetStubMap(int32 P,
                     const std::vector<std::vector<int32> > &phone_sets,
                     const std::vector<int32> &phone2num_pdf_classes,
                     const std::vector<bool> &share_roots,  // indexed by index into phone_sets.
                     int32 *num_leaves);



}// end namespace kaldi

#endif