// The contents of this file are in the public domain. See LICENSE_FOR_EXAMPLE_PROGRAMS.txt /* This is an example illustrating the use of the machine learning tools for sequence labeling in the dlib C++ Library. The general problem addressed by these tools is the following. Suppose you have a set of sequences of some kind and you want to learn to predict a label for each element of a sequence. So for example, you might have a set of English sentences where each word is labeled with its part of speech and you want to learn a model which can predict the part of speech for each word in a new sentence. Central to these tools is the sequence_labeler object. It is the object which represents the label prediction model. In particular, the model used by this object is the following. Given an input sequence x, predict an output label sequence y such that: y == argmax_y dot(weight_vector, PSI(x,y)) where PSI() is supplied by the user and defines the form of the model. In this example program we will define it such that we obtain a simple Hidden Markov Model. However, it's possible to define much more sophisticated models. You should take a look at the following papers for a few examples: - Hidden Markov Support Vector Machines by Y. Altun, I. Tsochantaridis, T. Hofmann - Shallow Parsing with Conditional Random Fields by Fei Sha and Fernando Pereira In the remainder of this example program we will show how to define your own PSI(), as well as how to learn the "weight_vector" parameter. Once you have these two items you will be able to use the sequence_labeler to predict the labels of new sequences. */ #include <iostream> #include <dlib/svm_threaded.h> #include <dlib/rand.h> using namespace std; using namespace dlib; /* In this example we will be working with a Hidden Markov Model where the hidden nodes and observation nodes both take on 3 different states. The task will be to take a sequence of observations and predict the state of the corresponding hidden nodes. */ constunsignedlongnum_label_states = 3; constunsignedlongnum_sample_states = 3; // ---------------------------------------------------------------------------------------- classfeature_extractor{/* This object is where you define your PSI(). To ensure that the argmax_y remains a tractable problem, the PSI(x,y) vector is actually a sum of vectors, each derived from the entire input sequence x but only part of the label sequence y. This allows the argmax_y to be efficiently solved using the well known Viterbi algorithm. */ public: // This defines the type used to represent the observed sequence. You can use // any type here so long as it has a .size() which returns the number of things // in the sequence. typedef std::vector<unsignedlong> sequence_type;unsignedlongnum_features() const /*! ensures - returns the dimensionality of the PSI() feature vector. !*/{// Recall that we are defining a HMM. So in this case the PSI() vector // should have the same dimensionality as the number of parameters in the HMM. return num_label_states*num_label_states + num_label_states*num_sample_states;}unsignedlongorder() const /*! ensures - This object represents a Markov model on the output labels. This parameter defines the order of the model. That is, this value controls how many previous label values get to be taken into consideration when performing feature extraction for a particular element of the input sequence. Note that the runtime of the algorithm is exponential in the order. So don't make order very large. !*/{// In this case we are using a HMM model that only looks at the // previous label. return 1;}unsignedlongnum_labels() const /*! ensures - returns the number of possible output labels. !*/{return num_label_states;}template <typename feature_setter, typename EXP>voidget_features( feature_setter& set_feature, const sequence_type& x, const matrix_exp<EXP>& y,unsignedlongposition ) const /*! requires - EXP::type == unsigned long (i.e. y contains unsigned longs) - position < x.size() - y.size() == min(position, order) + 1 - is_vector(y) == true - max(y) < num_labels() - set_feature is a function object which allows expressions of the form: - set_features((unsigned long)feature_index, (double)feature_value); - set_features((unsigned long)feature_index); ensures - for all valid i: - interprets y(i) as the label corresponding to x[position-i] - This function computes the part of PSI() corresponding to the x[position] element of the input sequence. Moreover, this part of PSI() is returned as a sparse vector by invoking set_feature(). For example, to set the feature with an index of 55 to the value of 1 this method would call: set_feature(55); Or equivalently: set_feature(55,1); Therefore, the first argument to set_feature is the index of the feature to be set while the second argument is the value the feature should take. Additionally, note that calling set_feature() multiple times with the same feature index does NOT overwrite the old value, it adds to the previous value. For example, if you call set_feature(55) 3 times then it will result in feature 55 having a value of 3. - This function only calls set_feature() with feature_index values < num_features() !*/{// Again, the features below only define a simple HMM. But in general, you can // use a wide variety of sophisticated feature extraction methods here. // Pull out an indicator feature for the type of transition between the // previous label and the current label. if (y.size() > 1) set_feature(y(1)*num_label_states + y(0)); // Pull out an indicator feature for the type of observed node given // the current label. set_feature(num_label_states*num_label_states + y(0)*num_sample_states + x[position]);}}; // We need to define serialize() and deserialize() for our feature extractor if we want // to be able to serialize and deserialize our learned models. In this case the // implementation is empty since our feature_extractor doesn't have any state. But you // might define more complex feature extractors which have state that needs to be saved.voidserialize(const feature_extractor&, std::ostream&){}voiddeserialize(feature_extractor&, std::istream&){}// ----------------------------------------------------------------------------------------voidmake_dataset( const matrix<double>& transition_probabilities, const matrix<double>& emission_probabilities, std::vector<std::vector<unsignedlong> >& samples, std::vector<std::vector<unsignedlong> >& labels,unsignedlongdataset_size ); /*! requires - transition_probabilities.nr() == transition_probabilities.nc() - transition_probabilities.nr() == emission_probabilities.nr() - The rows of transition_probabilities and emission_probabilities must sum to 1. (i.e. sum_cols(transition_probabilities) and sum_cols(emission_probabilities) must evaluate to vectors of all 1s.) ensures - This function randomly samples a bunch of sequences from the HMM defined by transition_probabilities and emission_probabilities. - The HMM is defined by: - The probability of transitioning from hidden state H1 to H2 is given by transition_probabilities(H1,H2). - The probability of a hidden state H producing an observed state O is given by emission_probabilities(H,O). - #samples.size() == #labels.size() == dataset_size - for all valid i: - #labels[i] is a randomly sampled sequence of hidden states from the given HMM. #samples[i] is its corresponding randomly sampled sequence of observed states. !*/ // ----------------------------------------------------------------------------------------intmain(){// We need a dataset to test the machine learning algorithms. So we are going to // define a HMM based on the following two matrices and then randomly sample a // set of data from it. Then we will see if the machine learning method can // recover the HMM model from the training data. matrix<double> transition_probabilities(num_label_states, num_label_states); transition_probabilities = 0.05, 0.90, 0.05, 0.05, 0.05, 0.90, 0.90, 0.05, 0.05; matrix<double> emission_probabilities(num_label_states,num_sample_states); emission_probabilities = 0.5, 0.5, 0.0, 0.0, 0.5, 0.5, 0.5, 0.0, 0.5; std::vector<std::vector<unsignedlong> > samples; std::vector<std::vector<unsignedlong> > labels; // sample 1000 labeled sequences from the HMM. make_dataset(transition_probabilities,emission_probabilities, samples, labels, 1000); // print out some of the randomly sampled sequences for (inti = 0; i < 10; ++i){cout << "hidden states: " << trans(mat(labels[i])); cout << "observed states: " << trans(mat(samples[i])); cout << "******************************" << endl;}// Next we use the structural_sequence_labeling_trainer to learn our // prediction model based on just the samples and labels. structural_sequence_labeling_trainer<feature_extractor> trainer; // This is the common SVM C parameter. Larger values encourage the // trainer to attempt to fit the data exactly but might overfit. // In general, you determine this parameter by cross-validation. trainer.set_c(4); // This trainer can use multiple CPU cores to speed up the training. // So set this to the number of available CPU cores. trainer.set_num_threads(4); // Learn to do sequence labeling from the dataset sequence_labeler<feature_extractor> labeler = trainer.train(samples, labels); // Test the learned labeler on one of the training samples. In this // case it will give the correct sequence of labels. std::vector<unsignedlong> predicted_labels = labeler(samples[0]); cout << "true hidden states: "<< trans(mat(labels[0])); cout << "predicted hidden states: "<< trans(mat(predicted_labels)); // We can also do cross-validation. The confusion_matrix is defined as: // - confusion_matrix(T,P) == the number of times a sequence element with label T // was predicted to have a label of P. // So if all predictions are perfect then only diagonal elements of this matrix will // be non-zero. matrix<double> confusion_matrix; confusion_matrix = cross_validate_sequence_labeler(trainer, samples, labels, 4); cout << "\ncross-validation: " << endl; cout << confusion_matrix; cout << "label accuracy: "<< sum(diag(confusion_matrix))/sum(confusion_matrix) << endl; // In this case, the label accuracy is about 88%. At this point, we want to know if // the machine learning method was able to recover the HMM model from the data. So // to test this, we can load the true HMM model into another sequence_labeler and // test it out on the data and compare the results. matrix<double,0,1> true_hmm_model_weights = log(join_cols(reshape_to_column_vector(transition_probabilities), reshape_to_column_vector(emission_probabilities))); // With this model, labeler_true will predict the most probable set of labels // given an input sequence. That is, it will predict using the equation: // y == argmax_y dot(true_hmm_model_weights, PSI(x,y)) sequence_labeler<feature_extractor> labeler_true(true_hmm_model_weights); confusion_matrix = test_sequence_labeler(labeler_true, samples, labels); cout << "\nTrue HMM model: " << endl; cout << confusion_matrix; cout << "label accuracy: "<< sum(diag(confusion_matrix))/sum(confusion_matrix) << endl; // Happily, we observe that the true model also obtains a label accuracy of 88%. // Finally, the labeler can be serialized to disk just like most dlib objects. serialize("labeler.dat") << labeler; // recall from disk deserialize("labeler.dat") >> labeler;}// ---------------------------------------------------------------------------------------- // ---------------------------------------------------------------------------------------- // Code for creating a bunch of random samples from our HMM. // ---------------------------------------------------------------------------------------- // ----------------------------------------------------------------------------------------voidsample_hmm( dlib::rand& rnd, const matrix<double>& transition_probabilities, const matrix<double>& emission_probabilities,unsignedlongprevious_label,unsignedlong& next_label,unsignedlong& next_sample ) /*! requires - previous_label < transition_probabilities.nr() - transition_probabilities.nr() == transition_probabilities.nc() - transition_probabilities.nr() == emission_probabilities.nr() - The rows of transition_probabilities and emission_probabilities must sum to 1. (i.e. sum_cols(transition_probabilities) and sum_cols(emission_probabilities) must evaluate to vectors of all 1s.) ensures - This function randomly samples the HMM defined by transition_probabilities and emission_probabilities assuming that the previous hidden state was previous_label. - The HMM is defined by: - P(next_label |previous_label) == transition_probabilities(previous_label, next_label) - P(next_sample|next_label) == emission_probabilities (next_label, next_sample) - #next_label == the sampled value of the hidden state - #next_sample == the sampled value of the observed state !*/{// sample next_labeldoublep = rnd.get_random_double(); for (longc = 0; p >= 0 && c < transition_probabilities.nc(); ++c){next_label = c; p -= transition_probabilities(previous_label, c);}// now sample next_sample p = rnd.get_random_double(); for (longc = 0; p >= 0 && c < emission_probabilities.nc(); ++c){next_sample = c; p -= emission_probabilities(next_label, c);}}// ----------------------------------------------------------------------------------------voidmake_dataset( const matrix<double>& transition_probabilities, const matrix<double>& emission_probabilities, std::vector<std::vector<unsignedlong> >& samples, std::vector<std::vector<unsignedlong> >& labels,unsignedlongdataset_size ){samples.clear(); labels.clear(); dlib::rand rnd; // now randomly sample some labeled sequences from our Hidden Markov Model for (unsignedlongiter = 0; iter < dataset_size; ++iter){constunsignedlongsequence_size = rnd.get_random_32bit_number()%20+3; std::vector<unsignedlong> sample(sequence_size); std::vector<unsignedlong> label(sequence_size);unsignedlongprevious_label = rnd.get_random_32bit_number()%num_label_states; for (unsignedlongi = 0; i < sample.size(); ++i){unsignedlongnext_label = 0, next_sample = 0; sample_hmm(rnd, transition_probabilities, emission_probabilities, previous_label, next_label, next_sample); label[i] = next_label; sample[i] = next_sample; previous_label = next_label;}samples.push_back(sample); labels.push_back(label);}}// ----------------------------------------------------------------------------------------