// See www.openfst.org for extensive documentation on this weighted
|
// finite-state transducer library.
|
|
#ifndef FST_EXTENSIONS_LINEAR_LINEAR_FST_DATA_BUILDER_H_
|
#define FST_EXTENSIONS_LINEAR_LINEAR_FST_DATA_BUILDER_H_
|
|
#include <map>
|
#include <queue>
|
#include <set>
|
#include <sstream>
|
#include <stack>
|
#include <string>
|
#include <vector>
|
|
#include <fst/compat.h>
|
#include <fst/log.h>
|
#include <fst/fst.h>
|
#include <fst/symbol-table.h>
|
#include <fst/util.h>
|
|
#include <fst/extensions/linear/linear-fst-data.h>
|
|
namespace fst {
|
|
// Forward declaration
|
template <class A>
|
class FeatureGroupBuilder;
|
|
// For logging purposes
|
inline string TranslateLabel(int64 label, const SymbolTable *syms);
|
template <class Iterator>
|
string JoinLabels(Iterator begin, Iterator end, const SymbolTable *syms);
|
template <class Label>
|
string JoinLabels(const std::vector<Label> &labels, const SymbolTable *syms);
|
|
// Guesses the appropriate boundary label (start- or end-of-sentence)
|
// for all labels equal to `boundary` and modifies the `sequence`
|
// in-place. Returns the number of positions that are still uncertain.
|
template <class A>
|
typename A::Label GuessStartOrEnd(std::vector<typename A::Label> *sequence,
|
typename A::Label boundary);
|
|
// Builds a `LinearFstData` object by adding words and feature
|
// weights. A few conventions:
|
//
|
// - Input labels forms a dense non-empty range from 1 to `MaxInputLabel()`.
|
// - Feature labels, output labels are > 0.
|
// - Being a discriminative linear model, it only makes sense to use tropical
|
// semirings.
|
template <class A>
|
class LinearFstDataBuilder {
|
public:
|
typedef typename A::Label Label;
|
typedef typename A::Weight Weight;
|
|
// Constructs a builder with associated symbol tables for diagonstic
|
// output. Each of these symbol tables may also be nullptr.
|
explicit LinearFstDataBuilder(const SymbolTable *isyms = nullptr,
|
const SymbolTable *fsyms = nullptr,
|
const SymbolTable *osyms = nullptr)
|
: error_(false),
|
max_future_size_(0),
|
max_input_label_(1),
|
isyms_(isyms),
|
fsyms_(fsyms),
|
osyms_(osyms) {}
|
|
// Tests whether the builder has encountered any error. No operation
|
// is valid if the builder is already at error state. All other
|
// public methods should check this before any actual operations.
|
bool Error() const { return error_; }
|
|
// Adds a word and its feature labels to the vocabulary; this
|
// version allows the word to have any output label. Returns true
|
// iff the word is added.
|
//
|
// This may fail if the word is added twice or if the feature labels
|
// are non-positive.
|
bool AddWord(Label word, const std::vector<Label> &features);
|
|
// Adds a word and its feature labels to the vocabulary; this
|
// version puts constraint on possible output labels the word can
|
// have. `possible_output` must not be empty. Returns true iff the
|
// word is added.
|
//
|
// In addition to the reasons above in the two-parameter version,
|
// this may also fail if `possible_output` is empty or any output
|
// label in it is non-positive.
|
bool AddWord(Label word, const std::vector<Label> &word_features,
|
const std::vector<Label> &possible_output);
|
|
// Creates a new feature group with specified future size (size of
|
// the look-ahead window), returns the group id to be used for
|
// adding actual feature weights or a negative number when called at
|
// error state.
|
//
|
// This does not fail unless called at error state.
|
int AddGroup(size_t future_size);
|
|
// Adds an instance of feature weight to the specified feature
|
// group. If some weight has already been added with the same
|
// feature, the product of the old and new weights are
|
// stored. Returns true iff the weight is added. A weight is not
|
// added when the context has ill-formed context involving start-,
|
// end-of-sentence marks.
|
//
|
// For two features to be within the same group, it must satisfy
|
// that (1) they have the same future size; (2) the two either have
|
// disjoint context or one is the back-off context of the
|
// other. Furthermore, for all features in a single group, there
|
// must be one and only one other context (not necessarily an active
|
// feature) that the feature immediately backs off to (i.e. there is
|
// no other context that is the back-off of the first and backs off
|
// to the second).
|
//
|
// Consider for example features with zero look-ahead of the form
|
// (input, OUTPUT).
|
//
|
// - The following two features can be put in the same group because
|
// their context is disjoint: (a a a, A A), (b, B B);
|
//
|
// - The following two features can be put in the same group because
|
// one is the back-off context of the other: (a a a, A A), (a a, A
|
// A);
|
//
|
// - The following two features can NOT be put in the same group
|
// because there is overlap but neither is the other's back-off: (a
|
// a a, A), (a a, A A);
|
//
|
// - Finally, the following three features cannot be in a same group
|
// because the first one can immediately back off to either of the
|
// rest: (a a a, A A), (a a, A A), (a a a, A).
|
//
|
// The easiest way to satisfy the constraints is to create a feature
|
// group for each feature template. However, better feature grouping
|
// may help improve speed.
|
//
|
// This may fail if any of input or output labels are non-positive,
|
// or if any call to `FeatureGroupBuilder<>::AddWeight()` fails.
|
bool AddWeight(size_t group, const std::vector<Label> &input,
|
const std::vector<Label> &output, Weight weight);
|
|
// Returns a newly created `LinearFstData` object or nullptr in case
|
// of failure. The caller takes the ownership of the memory. No
|
// other methods shall be called after this --- this is enforced by
|
// putting the builder at error state, even when a
|
// `LinearFstData<>` object is successfully built.
|
//
|
// This may fail if the call to any `FeatureGroupBuilder<>::Dump()`
|
// fails.
|
LinearFstData<A> *Dump();
|
|
private:
|
bool error_;
|
CompactSet<Label, kNoLabel> all_output_labels_;
|
std::map<Label, std::set<Label>> word_output_map_, word_feat_map_;
|
std::map<Label, std::set<size_t>> feat_groups_;
|
std::vector<std::unique_ptr<FeatureGroupBuilder<A>>> groups_;
|
size_t max_future_size_;
|
Label max_input_label_;
|
const SymbolTable *isyms_, *fsyms_, *osyms_;
|
|
LinearFstDataBuilder(const LinearFstDataBuilder &) = delete;
|
LinearFstDataBuilder &operator=(const LinearFstDataBuilder &) = delete;
|
};
|
|
// Builds a LinearFstData tailored for a LinearClassifierFst. The
|
// major difference between an ordinary LinearFstData that works on
|
// taggers and a LinearFstData that works on classifiers is that
|
// feature groups are divided into sections by the prediction class
|
// label. For a prediction label `pred` and a logical group id
|
// `group`, the actual group id is `group * num_classes + pred -
|
// 1`.
|
//
|
// This layout saves us from recording output labels in each single
|
// FeatureGroup. Because there is no need for any delaying, stripping
|
// the output allows features with different shapes but using the same
|
// set of feature label mapping to reside in a single FeatureGroup.
|
template <class A>
|
class LinearClassifierFstDataBuilder {
|
public:
|
typedef typename A::Label Label;
|
typedef typename A::Weight Weight;
|
|
// Constructs a builder for a `num_classes`-class classifier,
|
// optinally with associated symbol tables for diagnostic
|
// output. The output labels (i.e. prediction) must be in the range
|
// of [1, num_classes].
|
explicit LinearClassifierFstDataBuilder(size_t num_classes,
|
const SymbolTable *isyms = nullptr,
|
const SymbolTable *fsyms = nullptr,
|
const SymbolTable *osyms = nullptr)
|
: error_(false),
|
num_classes_(num_classes),
|
num_groups_(0),
|
builder_(isyms, fsyms, osyms) {}
|
|
// Tests whether the builder has encountered any error. Similar to
|
// LinearFstDataBuilder<>::Error().
|
bool Error() const { return error_; }
|
|
// Same as LinearFstDataBuilder<>::AddWord().
|
bool AddWord(Label word, const std::vector<Label> &features);
|
|
// Adds a logical feature group. Similar to
|
// LinearFstDataBuilder<>::AddGroup(), with the exception that the
|
// returned group id is the logical group id. Also there is no need
|
// for "future" in a classifier.
|
int AddGroup();
|
|
// Adds an instance of feature weight to the specified logical
|
// feature group. Instead of a vector of output, only a single
|
// prediction is needed as the output.
|
//
|
// This may fail if `pred` is not in the range of [1, num_classes_].
|
bool AddWeight(size_t group, const std::vector<Label> &input, Label pred,
|
Weight weight);
|
|
// Returns a newly created `LinearFstData` object or nullptr in case of
|
// failure.
|
LinearFstData<A> *Dump();
|
|
private:
|
std::vector<Label> empty_;
|
bool error_;
|
size_t num_classes_, num_groups_;
|
LinearFstDataBuilder<A> builder_;
|
};
|
|
// Builds a single feature group. Usually used in
|
// `LinearFstDataBuilder::AddWeight()`. See that method for the
|
// constraints on grouping features.
|
template <class A>
|
class FeatureGroupBuilder {
|
public:
|
typedef typename A::Label Label;
|
typedef typename A::Weight Weight;
|
|
// Constructs a builder with the given future size. All features
|
// added to the group will have look-ahead windows of this size.
|
FeatureGroupBuilder(size_t future_size, const SymbolTable *fsyms,
|
const SymbolTable *osyms)
|
: error_(false), future_size_(future_size), fsyms_(fsyms), osyms_(osyms) {
|
// This edge is special; see doc of class `FeatureGroup` on the
|
// details.
|
start_ = trie_.Insert(trie_.Root(), InputOutputLabel(kNoLabel, kNoLabel));
|
}
|
|
// Tests whether the builder has encountered any error. No operation
|
// is valid if the builder is already at error state. All other
|
// public methods should check this before any actual operations.
|
bool Error() const { return error_; }
|
|
// Adds a feature weight with the given context. Returns true iff
|
// the weight is added. A weight is not added if it has ill-formed
|
// context involving start-, end-of-sentence marks.
|
//
|
// Note: `input` is the sequence of input
|
// features, instead of input labels themselves. `input` must be at
|
// least as long as `future_size`; `output` may be empty, but
|
// usually should be non-empty because an empty output context is
|
// useless in discriminative modelling. All labels in both `input`
|
// and `output` must be > 0 (this is checked in
|
// `LinearFstDataBuilder::AddWeight()`). See
|
// LinearFstDataBuilder<>::AddWeight for more details.
|
//
|
// This may fail if the input is smaller than the look-ahead window.
|
bool AddWeight(const std::vector<Label> &input,
|
const std::vector<Label> &output, Weight weight);
|
|
// Creates an actual FeatureGroup<> object. Connects back-off links;
|
// pre-accumulates weights from back-off features. Returns nullptr if
|
// there is any violation in unique immediate back-off
|
// constraints.
|
//
|
// Regardless of whether the call succeeds or not, the error flag is
|
// always set before this returns, to prevent repeated dumping.
|
//
|
// TODO(wuke): check overlapping top-level contexts (see
|
// `DumpOverlappingContext()` in tests).
|
FeatureGroup<A> *Dump(size_t max_future_size);
|
|
private:
|
typedef typename FeatureGroup<A>::InputOutputLabel InputOutputLabel;
|
typedef typename FeatureGroup<A>::InputOutputLabelHash InputOutputLabelHash;
|
typedef typename FeatureGroup<A>::WeightBackLink WeightBackLink;
|
// Nested trie topology uses more memory but we can traverse a
|
// node's children easily, which is required in `BuildBackLinks()`.
|
typedef NestedTrieTopology<InputOutputLabel, InputOutputLabelHash> Topology;
|
typedef MutableTrie<InputOutputLabel, WeightBackLink, Topology> Trie;
|
|
// Finds the first node with an arc with `label` following the
|
// back-off chain of `parent`. Returns the node index or
|
// `kNoTrieNodeId` when not found. The number of hops is stored in
|
// `hop` when it is not `nullptr`.
|
//
|
// This does not fail.
|
int FindFirstMatch(InputOutputLabel label, int parent, int *hop) const;
|
|
// Links each node to its immediate back-off. root is linked to -1.
|
//
|
// This may fail when the unique immediate back-off constraint is
|
// violated.
|
void BuildBackLinks();
|
|
// Traces back on the back-chain for each node to multiply the
|
// weights from back-offs to the node itself.
|
//
|
// This does not fail.
|
void PreAccumulateWeights();
|
|
// Reconstruct the path from trie root to given node for logging.
|
bool TrieDfs(const Topology &topology, int cur, int target,
|
std::vector<InputOutputLabel> *path) const;
|
string TriePath(int node, const Topology &topology) const;
|
|
bool error_;
|
size_t future_size_;
|
Trie trie_;
|
int start_;
|
const SymbolTable *fsyms_, *osyms_;
|
|
FeatureGroupBuilder(const FeatureGroupBuilder &) = delete;
|
FeatureGroupBuilder &operator=(const FeatureGroupBuilder &) = delete;
|
};
|
|
//
|
// Implementation of methods in `LinearFstDataBuilder`
|
//
|
template <class A>
|
bool LinearFstDataBuilder<A>::AddWord(Label word,
|
const std::vector<Label> &features) {
|
if (error_) {
|
FSTERROR() << "Calling LinearFstDataBuilder<>::AddWord() at error state";
|
return false;
|
}
|
if (word == LinearFstData<A>::kStartOfSentence ||
|
word == LinearFstData<A>::kEndOfSentence) {
|
LOG(WARNING) << "Ignored: adding boundary label: "
|
<< TranslateLabel(word, isyms_)
|
<< "(start-of-sentence=" << LinearFstData<A>::kStartOfSentence
|
<< ", end-of-sentence=" << LinearFstData<A>::kEndOfSentence
|
<< ")";
|
return false;
|
}
|
if (word <= 0) {
|
error_ = true;
|
FSTERROR() << "Word label must be > 0; got " << word;
|
return false;
|
}
|
if (word > max_input_label_) max_input_label_ = word;
|
// Make sure the word hasn't been added before
|
if (word_feat_map_.find(word) != word_feat_map_.end()) {
|
error_ = true;
|
FSTERROR() << "Input word " << TranslateLabel(word, isyms_)
|
<< " is added twice";
|
return false;
|
}
|
// Store features
|
std::set<Label> *feats = &word_feat_map_[word];
|
for (size_t i = 0; i < features.size(); ++i) {
|
Label feat = features[i];
|
if (feat <= 0) {
|
error_ = true;
|
FSTERROR() << "Feature label must be > 0; got " << feat;
|
return false;
|
}
|
feats->insert(feat);
|
}
|
return true;
|
}
|
|
template <class A>
|
bool LinearFstDataBuilder<A>::AddWord(
|
Label word, const std::vector<Label> &word_features,
|
const std::vector<Label> &possible_output) {
|
if (error_) {
|
FSTERROR() << "Calling LinearFstDataBuilder<>::AddWord() at error state";
|
return false;
|
}
|
if (!AddWord(word, word_features)) return false;
|
// Store possible output constraint
|
if (possible_output.empty()) {
|
error_ = true;
|
FSTERROR() << "Empty possible output constraint; "
|
<< "use the two-parameter version if no constraint is need.";
|
return false;
|
}
|
std::set<Label> *outputs = &word_output_map_[word];
|
for (size_t i = 0; i < possible_output.size(); ++i) {
|
Label output = possible_output[i];
|
if (output == LinearFstData<A>::kStartOfSentence ||
|
output == LinearFstData<A>::kEndOfSentence) {
|
LOG(WARNING) << "Ignored: word = " << TranslateLabel(word, isyms_)
|
<< ": adding boundary label as possible output: " << output
|
<< "(start-of-sentence="
|
<< LinearFstData<A>::kStartOfSentence
|
<< ", end-of-sentence=" << LinearFstData<A>::kEndOfSentence
|
<< ")";
|
continue;
|
}
|
if (output <= 0) {
|
error_ = true;
|
FSTERROR() << "Output label must be > 0; got " << output;
|
return false;
|
}
|
outputs->insert(output);
|
all_output_labels_.Insert(output);
|
}
|
return true;
|
}
|
|
template <class A>
|
inline int LinearFstDataBuilder<A>::AddGroup(size_t future_size) {
|
if (error_) {
|
FSTERROR() << "Calling LinearFstDataBuilder<>::AddGroup() at error state";
|
return -1;
|
}
|
size_t ret = groups_.size();
|
groups_.emplace_back(new FeatureGroupBuilder<A>(future_size, fsyms_, osyms_));
|
if (future_size > max_future_size_) max_future_size_ = future_size;
|
return ret;
|
}
|
|
template <class A>
|
bool LinearFstDataBuilder<A>::AddWeight(size_t group,
|
const std::vector<Label> &input,
|
const std::vector<Label> &output,
|
Weight weight) {
|
if (error_) {
|
FSTERROR() << "Calling LinearFstDataBuilder<>::AddWeight() at error state";
|
return false;
|
}
|
// Check well-formedness of boundary marks on the input.
|
{
|
bool start_in_middle = false, end_in_middle = false;
|
for (int i = 1; i < input.size(); ++i) {
|
if (input[i] == LinearFstData<A>::kStartOfSentence &&
|
input[i - 1] != LinearFstData<A>::kStartOfSentence)
|
start_in_middle = true;
|
if (input[i - 1] == LinearFstData<A>::kEndOfSentence &&
|
input[i] != LinearFstData<A>::kEndOfSentence)
|
end_in_middle = true;
|
}
|
if (start_in_middle) {
|
LOG(WARNING) << "Ignored: start-of-sentence in the middle of the input!";
|
LOG(WARNING) << "\tInput: " << JoinLabels(input, fsyms_);
|
LOG(WARNING) << "\tOutput: " << JoinLabels(output, osyms_);
|
return false;
|
}
|
if (end_in_middle) {
|
LOG(WARNING) << "Ignored: end-of-sentence in the middle of the input!";
|
LOG(WARNING) << "\tInput: " << JoinLabels(input, fsyms_);
|
LOG(WARNING) << "\tOutput: " << JoinLabels(output, osyms_);
|
return false;
|
}
|
}
|
// Check well-formedness of boundary marks on the output.
|
{
|
bool non_first_start = false, non_last_end = false;
|
for (int i = 1; i < output.size(); ++i) {
|
if (output[i] == LinearFstData<A>::kStartOfSentence)
|
non_first_start = true;
|
if (output[i - 1] == LinearFstData<A>::kEndOfSentence)
|
non_last_end = true;
|
}
|
if (non_first_start) {
|
LOG(WARNING) << "Ignored: start-of-sentence not appearing "
|
<< "as the first label in the output!";
|
LOG(WARNING) << "\tInput: " << JoinLabels(input, fsyms_);
|
LOG(WARNING) << "\tOutput: " << JoinLabels(output, osyms_);
|
return false;
|
}
|
if (non_last_end) {
|
LOG(WARNING) << "Ignored: end-of-sentence not appearing "
|
<< "as the last label in the output!";
|
LOG(WARNING) << "\tInput: " << JoinLabels(input, fsyms_);
|
LOG(WARNING) << "\tOutput: " << JoinLabels(output, osyms_);
|
return false;
|
}
|
}
|
|
for (size_t i = 0; i < input.size(); ++i) {
|
Label feat = input[i];
|
if (feat != LinearFstData<A>::kStartOfSentence &&
|
feat != LinearFstData<A>::kEndOfSentence && feat <= 0) {
|
error_ = true;
|
FSTERROR() << "Feature label must be > 0; got " << feat;
|
return false;
|
}
|
feat_groups_[feat].insert(group);
|
}
|
for (size_t i = 0; i < output.size(); ++i) {
|
Label label = output[i];
|
if (label != LinearFstData<A>::kStartOfSentence &&
|
label != LinearFstData<A>::kEndOfSentence && label <= 0) {
|
error_ = true;
|
FSTERROR() << "Output label must be > 0; got " << label;
|
return false;
|
}
|
if (label != LinearFstData<A>::kStartOfSentence &&
|
label != LinearFstData<A>::kEndOfSentence)
|
all_output_labels_.Insert(label);
|
}
|
|
// Everything looks good at this point (more checks on the way in
|
// the feature group). Add this feature weight.
|
bool added = groups_[group]->AddWeight(input, output, weight);
|
if (groups_[group]->Error()) {
|
error_ = true;
|
FSTERROR() << "FeatureGroupBuilder<>::AddWeight() failed";
|
return false;
|
}
|
return added;
|
}
|
|
template <class A>
|
LinearFstData<A> *LinearFstDataBuilder<A>::Dump() {
|
if (error_) {
|
FSTERROR() << "Calling LinearFstDataBuilder<>::Dump() at error state";
|
return nullptr;
|
}
|
|
std::unique_ptr<LinearFstData<A>> data(new LinearFstData<A>());
|
data->max_future_size_ = max_future_size_;
|
data->max_input_label_ = max_input_label_;
|
|
// Feature groups; free builders after it's dumped.
|
data->groups_.resize(groups_.size());
|
for (int group = 0; group != groups_.size(); ++group) {
|
FeatureGroup<A> *new_group = groups_[group]->Dump(max_future_size_);
|
if (new_group == nullptr) {
|
error_ = true;
|
FSTERROR() << "Error in dumping group " << group;
|
return nullptr;
|
}
|
data->groups_[group].reset(new_group);
|
groups_[group].reset();
|
VLOG(1) << "Group " << group << ": " << new_group->Stats();
|
}
|
|
// Per-group feature mapping
|
data->group_feat_map_.Init(data->NumGroups(), max_input_label_ + 1);
|
for (Label word = 1; word <= max_input_label_; ++word) {
|
typename std::map<Label, std::set<Label>>::const_iterator it =
|
word_feat_map_.find(word);
|
if (it == word_feat_map_.end()) continue;
|
for (typename std::set<Label>::const_iterator oit = it->second.begin();
|
oit != it->second.end(); ++oit) {
|
Label feat = *oit;
|
typename std::map<Label, std::set<size_t>>::const_iterator jt =
|
feat_groups_.find(feat);
|
if (jt == feat_groups_.end()) continue;
|
for (std::set<size_t>::const_iterator git = jt->second.begin();
|
git != jt->second.end(); ++git) {
|
size_t group_id = *git;
|
if (!data->group_feat_map_.Set(group_id, word, feat)) {
|
error_ = true;
|
return nullptr;
|
}
|
}
|
}
|
}
|
|
// Possible output labels
|
{
|
std::vector<typename LinearFstData<A>::InputAttribute> *input_attribs =
|
&data->input_attribs_;
|
std::vector<Label> *output_pool = &data->output_pool_;
|
input_attribs->resize(max_input_label_ + 1);
|
for (Label word = 0; word <= max_input_label_; ++word) {
|
typename std::map<Label, std::set<Label>>::const_iterator it =
|
word_output_map_.find(word);
|
if (it == word_output_map_.end()) {
|
(*input_attribs)[word].output_begin = 0;
|
(*input_attribs)[word].output_length = 0;
|
} else {
|
(*input_attribs)[word].output_begin = output_pool->size();
|
(*input_attribs)[word].output_length = it->second.size();
|
for (typename std::set<Label>::const_iterator oit = it->second.begin();
|
oit != it->second.end(); ++oit) {
|
Label olabel = *oit;
|
output_pool->push_back(olabel);
|
}
|
}
|
}
|
}
|
|
for (typename CompactSet<Label, kNoLabel>::const_iterator it =
|
all_output_labels_.Begin();
|
it != all_output_labels_.End(); ++it)
|
data->output_set_.push_back(*it);
|
|
error_ = true; // prevent future calls on this object
|
return data.release();
|
}
|
|
//
|
// Implementation of methods in `LinearClassifierFstDataBuilder`
|
//
|
template <class A>
|
inline bool LinearClassifierFstDataBuilder<A>::AddWord(
|
Label word, const std::vector<Label> &features) {
|
if (error_) {
|
FSTERROR() << "Calling LinearClassifierFstDataBuilder<>::AddWord() at "
|
"error state";
|
return false;
|
}
|
bool added = builder_.AddWord(word, features);
|
if (builder_.Error()) error_ = true;
|
return added;
|
}
|
|
template <class A>
|
inline int LinearClassifierFstDataBuilder<A>::AddGroup() {
|
if (error_) {
|
FSTERROR() << "Calling LinearClassifierFstDataBuilder<>::AddGroup() at "
|
"error state";
|
return -1;
|
}
|
for (int i = 0; i < num_classes_; ++i) builder_.AddGroup(0);
|
if (builder_.Error()) {
|
error_ = true;
|
return -1;
|
}
|
return num_groups_++;
|
}
|
|
template <class A>
|
inline bool LinearClassifierFstDataBuilder<A>::AddWeight(
|
size_t group, const std::vector<Label> &input, Label pred, Weight weight) {
|
if (error_) {
|
FSTERROR() << "Calling LinearClassifierFstDataBuilder<>::AddWeight() at "
|
"error state";
|
return false;
|
}
|
if (pred <= 0 || pred > num_classes_) {
|
FSTERROR() << "Out-of-range prediction label: " << pred
|
<< " (num classes = " << num_classes_ << ")";
|
error_ = true;
|
return false;
|
}
|
size_t real_group = group * num_classes_ + pred - 1;
|
bool added = builder_.AddWeight(real_group, input, empty_, weight);
|
if (builder_.Error()) error_ = true;
|
return added;
|
}
|
|
template <class A>
|
inline LinearFstData<A> *LinearClassifierFstDataBuilder<A>::Dump() {
|
if (error_) {
|
FSTERROR()
|
<< "Calling LinearClassifierFstDataBuilder<>::Dump() at error state";
|
return nullptr;
|
}
|
LinearFstData<A> *data = builder_.Dump();
|
error_ = true;
|
return data;
|
}
|
|
//
|
// Implementation of methods in `FeatureGroupBuilder`
|
//
|
template <class A>
|
bool FeatureGroupBuilder<A>::AddWeight(const std::vector<Label> &input,
|
const std::vector<Label> &output,
|
Weight weight) {
|
if (error_) {
|
FSTERROR() << "Calling FeatureGroupBuilder<>::AddWeight() at error state";
|
return false;
|
}
|
|
// `LinearFstDataBuilder<>::AddWeight()` ensures prefix/suffix
|
// properties for us. We can directly count.
|
int num_input_start = 0;
|
while (num_input_start < input.size() &&
|
input[num_input_start] == LinearFstData<A>::kStartOfSentence)
|
++num_input_start;
|
int num_output_start = 0;
|
while (num_output_start < output.size() &&
|
output[num_output_start] == LinearFstData<A>::kStartOfSentence)
|
++num_output_start;
|
int num_input_end = 0;
|
for (int i = input.size() - 1;
|
i >= 0 && input[i] == LinearFstData<A>::kEndOfSentence; --i)
|
++num_input_end;
|
int num_output_end = 0;
|
for (int i = output.size() - 1;
|
i >= 0 && output[i] == LinearFstData<A>::kEndOfSentence; --i)
|
++num_output_end;
|
|
DCHECK_LE(num_output_end, 1);
|
|
if (input.size() - num_input_start < future_size_) {
|
LOG(WARNING) << "Ignored: start-of-sentence in the future!";
|
LOG(WARNING) << "\tInput: " << JoinLabels(input, fsyms_);
|
LOG(WARNING) << "\tOutput: " << JoinLabels(output, fsyms_);
|
return false;
|
}
|
if (num_input_start > 0 &&
|
input.size() - future_size_ - num_input_start <
|
output.size() - num_output_start) {
|
LOG(WARNING) << "Ignored: matching start-of-sentence with actual output!";
|
LOG(WARNING) << "\tInput: " << JoinLabels(input, fsyms_);
|
LOG(WARNING) << "\tOutput: " << JoinLabels(output, osyms_);
|
return false;
|
}
|
if (num_output_start > 0 &&
|
input.size() - future_size_ - num_input_start >
|
output.size() - num_output_start) {
|
LOG(WARNING) << "Ignored: matching start-of-sentence with actual input!";
|
LOG(WARNING) << "\tInput: " << JoinLabels(input, fsyms_);
|
LOG(WARNING) << "\tOutput: " << JoinLabels(output, osyms_);
|
return false;
|
}
|
// The following two require `num_output_end` <= 1.
|
if (num_input_end > future_size_ && num_input_end - future_size_ != 1) {
|
LOG(WARNING) << "Ignored: matching end-of-sentence with actual output!";
|
LOG(WARNING) << "\tInput: " << JoinLabels(input, fsyms_);
|
LOG(WARNING) << "\tOutput: " << JoinLabels(output, osyms_);
|
return false;
|
}
|
if (num_output_end > 0 &&
|
((input.size() == future_size_ && future_size_ != num_input_end) ||
|
(input.size() > future_size_ &&
|
num_input_end != future_size_ + num_output_end))) {
|
LOG(WARNING) << "Ignored: matching end-of-sentence with actual input!";
|
LOG(WARNING) << "\tInput: " << JoinLabels(input, fsyms_);
|
LOG(WARNING) << "\tOutput: " << JoinLabels(output, osyms_);
|
return false;
|
}
|
// Check if the context has no other labels than boundary marks
|
// (such features are useless).
|
if (num_input_start + num_input_end == input.size() &&
|
num_output_start + num_output_end == output.size()) {
|
LOG(WARNING)
|
<< "Ignored: feature context consisting of only boundary marks!";
|
LOG(WARNING) << "\tInput: " << JoinLabels(input, fsyms_);
|
LOG(WARNING) << "\tOutput: " << JoinLabels(output, osyms_);
|
return false;
|
}
|
|
// Start point for insertion in the trie. Insert at `start_` iff the
|
// beginning of the context is non-consumed start-of-sentence.
|
int cur = (num_input_start == 0 && num_output_start <= future_size_)
|
? trie_.Root()
|
: start_;
|
// Skip all input start-of-sentence marks
|
size_t ipos = num_input_start;
|
// Skip to keep at most `future_size_` start-of-sentence marks
|
size_t opos =
|
num_output_start <= future_size_ ? 0 : num_output_start - future_size_;
|
// Skip `num_output_end` end-of-sentence marks on both input and output
|
size_t iend = !input.empty() ? input.size() - num_output_end : 0,
|
oend = output.size() - num_output_end;
|
// Further, when output is empty, keep at most `future_size_`
|
// end-of-sentence marks on input.
|
if (output.empty() && num_input_end > future_size_)
|
iend = input.size() - num_input_end + future_size_;
|
|
// Actual feature context is (input[ipos:iend], output[opos:oend]).
|
|
// Pad `kNoLabel` as don't cares on the shorter of actual `input`
|
// and `output`.
|
const size_t effective_input_size = iend - ipos,
|
effective_output_size = oend - opos;
|
if (effective_input_size > effective_output_size) {
|
for (size_t pad = effective_input_size - effective_output_size; pad != 0;
|
--pad, ++ipos)
|
cur = trie_.Insert(cur, InputOutputLabel(input[ipos], kNoLabel));
|
} else if (effective_input_size < effective_output_size) {
|
for (size_t pad = effective_output_size - effective_input_size; pad != 0;
|
--pad, ++opos)
|
cur = trie_.Insert(cur, InputOutputLabel(kNoLabel, output[opos]));
|
}
|
CHECK_EQ(iend - ipos, oend - opos);
|
for (; ipos != iend; ++ipos, ++opos)
|
cur = trie_.Insert(cur, InputOutputLabel(input[ipos], output[opos]));
|
// We only need to attach final weight when there is an output
|
// end-of-sentence. When there is only end-of-sentence on the input,
|
// they are all consumed as the end-of-sentence paddings from
|
// `LinearFstImpl<>::ShiftBuffer()`. `LinearFstImpl<>::Expand()`
|
// and `LinearFstImpl<>::MatchInput()` ensures no other
|
// transition takes place after consuming the padding.
|
if (num_output_end > 0 || (output.empty() && num_input_end > future_size_))
|
trie_[cur].final_weight = Times(trie_[cur].final_weight, weight);
|
else
|
trie_[cur].weight = Times(trie_[cur].weight, weight);
|
|
return true;
|
}
|
|
template <class A>
|
FeatureGroup<A> *FeatureGroupBuilder<A>::Dump(size_t max_future_size) {
|
if (error_) {
|
FSTERROR() << "Calling FeatureGroupBuilder<>::PreAccumulateWeights() "
|
<< "at error state";
|
return nullptr;
|
}
|
|
if (max_future_size < future_size_) {
|
error_ = true;
|
FSTERROR() << "max_future_size (= " << max_future_size
|
<< ") is smaller the builder's future_size (= " << future_size_
|
<< ")";
|
return nullptr;
|
}
|
|
BuildBackLinks();
|
if (error_) return nullptr;
|
PreAccumulateWeights(); // does not fail
|
|
FeatureGroup<A> *ret =
|
new FeatureGroup<A>(max_future_size - future_size_, start_);
|
|
// Walk around the trie to compute next states
|
ret->next_state_.resize(trie_.NumNodes());
|
const Topology &topology = trie_.TrieTopology();
|
for (int i = 0; i < topology.NumNodes(); ++i) {
|
int next = i;
|
while (next != topology.Root() && topology.ChildrenOf(next).empty() &&
|
trie_[next].final_weight ==
|
trie_[trie_[next].back_link].final_weight)
|
next = trie_[next].back_link;
|
ret->next_state_[i] = next;
|
}
|
|
// Copy the trie
|
typename FeatureGroup<A>::Trie store_trie(trie_);
|
ret->trie_.swap(store_trie);
|
|
// Put the builder at error state to prevent repeated call of `Dump()`.
|
error_ = true;
|
return ret;
|
}
|
|
template <class A>
|
int FeatureGroupBuilder<A>::FindFirstMatch(InputOutputLabel label, int parent,
|
int *hop) const {
|
int hop_count = 0;
|
int ret = kNoTrieNodeId;
|
for (; parent >= 0; parent = trie_[parent].back_link, ++hop_count) {
|
int next = trie_.Find(parent, label);
|
if (next != kNoTrieNodeId) {
|
ret = next;
|
break;
|
}
|
}
|
if (hop != nullptr) *hop = hop_count;
|
return ret;
|
}
|
|
template <class A>
|
void FeatureGroupBuilder<A>::BuildBackLinks() {
|
// Breadth first search from the root. In the case where we only
|
// have the input label, the immedate back-off is simply the longest
|
// suffix of the current node that is also in the trie. For a node
|
// reached from its parent with label L, we can simply walk through
|
// the parent's back-off chain to find the first state with an arc
|
// of the same label L. The uniqueness is always
|
// guanranteed. However, in the case with both input and output
|
// labels, it is possible to back off by removing first labels from
|
// either side, which in general causes non-uniqueness.
|
|
const Topology &topology = trie_.TrieTopology();
|
std::queue<int> q; // all enqueued or visited nodes have known links
|
|
// Note: nodes have back link initialized to -1 in their
|
// constructor.
|
q.push(trie_.Root());
|
while (!error_ && !q.empty()) {
|
int parent = q.front();
|
q.pop();
|
// Find links for every child
|
const typename Topology::NextMap &children = topology.ChildrenOf(parent);
|
for (typename Topology::NextMap::const_iterator eit = children.begin();
|
eit != children.end(); ++eit) {
|
const std::pair<InputOutputLabel, int> &edge = *eit;
|
InputOutputLabel label = edge.first;
|
int child = edge.second;
|
if (label.input == kNoLabel || label.output == kNoLabel) {
|
// Label pairs from root to here all have one and only one
|
// `kNoLabel` on the same side; equivalent to the
|
// "longest-suffix" case.
|
trie_[child].back_link =
|
FindFirstMatch(label, trie_[parent].back_link, nullptr);
|
} else {
|
// Neither side is `kNoLabel` at this point, there are
|
// three possible ways to back-off: if the parent backs
|
// off to some context with only one side non-empty, the
|
// empty side may remain empty; or else an exact match of
|
// both sides is needed. Try to find all three possible
|
// backs and look for the closest one (in terms of hops
|
// along the parent's back-off chain).
|
int only_input_hop, only_output_hop, full_hop;
|
int only_input_link =
|
FindFirstMatch(InputOutputLabel(label.input, kNoLabel), parent,
|
&only_input_hop),
|
only_output_link =
|
FindFirstMatch(InputOutputLabel(kNoLabel, label.output), parent,
|
&only_output_hop),
|
full_link =
|
FindFirstMatch(label, trie_[parent].back_link, &full_hop);
|
if (only_input_link != -1 && only_output_link != -1) {
|
error_ = true;
|
FSTERROR() << "Branching back-off chain:\n"
|
<< "\tnode " << child << ": " << TriePath(child, topology)
|
<< "\n"
|
<< "\tcan back-off to node " << only_input_link << ": "
|
<< TriePath(only_input_link, topology) << "\n"
|
<< "\tcan back-off to node " << only_output_link << ": "
|
<< TriePath(only_output_link, topology);
|
return;
|
} else if (full_link != -1) {
|
++full_hop;
|
if (full_hop <= only_input_hop && full_hop <= only_output_hop) {
|
trie_[child].back_link = full_link;
|
} else {
|
error_ = true;
|
int problem_link = only_input_link != kNoTrieNodeId
|
? only_input_link
|
: only_output_link;
|
CHECK_NE(problem_link, kNoTrieNodeId);
|
FSTERROR() << "Branching back-off chain:\n"
|
<< "\tnode " << child << ": "
|
<< TriePath(child, topology) << "\n"
|
<< "\tcan back-off to node " << full_link << ": "
|
<< TriePath(full_link, topology) << "\n"
|
<< "tcan back-off to node " << problem_link << ": "
|
<< TriePath(problem_link, topology);
|
return;
|
}
|
} else {
|
trie_[child].back_link =
|
only_input_link != -1 ? only_input_link : only_output_link;
|
}
|
}
|
if (error_) break;
|
// Point to empty context (root) when no back-off can be found
|
if (trie_[child].back_link == -1) trie_[child].back_link = 0;
|
q.push(child);
|
}
|
}
|
}
|
|
template <class A>
|
void FeatureGroupBuilder<A>::PreAccumulateWeights() {
|
std::vector<bool> visited(trie_.NumNodes(), false);
|
visited[trie_.Root()] = true;
|
|
for (size_t i = 0; i != trie_.NumNodes(); ++i) {
|
std::stack<int> back_offs;
|
for (int j = i; !visited[j]; j = trie_[j].back_link) back_offs.push(j);
|
while (!back_offs.empty()) {
|
int j = back_offs.top();
|
back_offs.pop();
|
WeightBackLink &node = trie_[j];
|
node.weight = Times(node.weight, trie_[node.back_link].weight);
|
node.final_weight =
|
Times(node.final_weight, trie_[node.back_link].final_weight);
|
visited[j] = true;
|
}
|
}
|
}
|
|
template <class A>
|
bool FeatureGroupBuilder<A>::TrieDfs(
|
const Topology &topology, int cur, int target,
|
std::vector<InputOutputLabel> *path) const {
|
if (cur == target) return true;
|
const typename Topology::NextMap &children = topology.ChildrenOf(cur);
|
for (typename Topology::NextMap::const_iterator eit = children.begin();
|
eit != children.end(); ++eit) {
|
const std::pair<InputOutputLabel, int> &edge = *eit;
|
path->push_back(edge.first);
|
if (TrieDfs(topology, edge.second, target, path)) return true;
|
path->pop_back();
|
}
|
return false;
|
}
|
|
template <class A>
|
string FeatureGroupBuilder<A>::TriePath(int node,
|
const Topology &topology) const {
|
std::vector<InputOutputLabel> labels;
|
TrieDfs(topology, topology.Root(), node, &labels);
|
bool first = true;
|
std::ostringstream strm;
|
for (typename std::vector<InputOutputLabel>::const_iterator it =
|
labels.begin();
|
it != labels.end(); ++it) {
|
InputOutputLabel i = *it;
|
if (first)
|
first = false;
|
else
|
strm << ", ";
|
strm << "(" << TranslateLabel(i.input, fsyms_) << ", "
|
<< TranslateLabel(i.output, osyms_) << ")";
|
}
|
return strm.str();
|
}
|
|
inline string TranslateLabel(int64 label, const SymbolTable *syms) {
|
string ret;
|
if (syms != nullptr) ret += syms->Find(label);
|
if (ret.empty()) {
|
std::ostringstream strm;
|
strm << '<' << label << '>';
|
ret = strm.str();
|
}
|
return ret;
|
}
|
|
template <class Iterator>
|
string JoinLabels(Iterator begin, Iterator end, const SymbolTable *syms) {
|
if (begin == end) return "<empty>";
|
std::ostringstream strm;
|
bool first = true;
|
for (Iterator it = begin; it != end; ++it) {
|
if (first)
|
first = false;
|
else
|
strm << '|';
|
strm << TranslateLabel(*it, syms);
|
}
|
return strm.str();
|
}
|
|
template <class Label>
|
string JoinLabels(const std::vector<Label> &labels, const SymbolTable *syms) {
|
return JoinLabels(labels.begin(), labels.end(), syms);
|
}
|
|
template <class A>
|
typename A::Label GuessStartOrEnd(std::vector<typename A::Label> *sequence,
|
typename A::Label boundary) {
|
const size_t length = sequence->size();
|
std::vector<bool> non_boundary_on_left(length, false),
|
non_boundary_on_right(length, false);
|
for (size_t i = 1; i < length; ++i) {
|
non_boundary_on_left[i] =
|
non_boundary_on_left[i - 1] || (*sequence)[i - 1] != boundary;
|
non_boundary_on_right[length - 1 - i] = non_boundary_on_right[length - i] ||
|
(*sequence)[length - i] != boundary;
|
}
|
int unresolved = 0;
|
for (size_t i = 0; i < length; ++i) {
|
if ((*sequence)[i] != boundary) continue;
|
const bool left = non_boundary_on_left[i], right = non_boundary_on_right[i];
|
if (left && right) {
|
// Boundary in the middle
|
LOG(WARNING) << "Boundary label in the middle of the sequence! position: "
|
<< i << "; boundary: " << boundary
|
<< "; sequence: " << JoinLabels(*sequence, nullptr);
|
LOG(WARNING)
|
<< "This is an invalid sequence anyway so I will set it to start.";
|
(*sequence)[i] = LinearFstData<A>::kStartOfSentence;
|
} else if (left && !right) {
|
// Can only be end
|
(*sequence)[i] = LinearFstData<A>::kEndOfSentence;
|
} else if (!left && right) {
|
// Can only be start
|
(*sequence)[i] = LinearFstData<A>::kStartOfSentence;
|
} else {
|
// !left && !right; can't really tell
|
++unresolved;
|
}
|
}
|
return unresolved;
|
}
|
|
} // namespace fst
|
|
#endif // FST_EXTENSIONS_LINEAR_LINEAR_FST_DATA_BUILDER_H_
|
