18 #include <shogun/lib/config.h> 23 #ifdef USE_HMMPARALLEL 24 #define USE_HMMPARALLEL_STRUCTURES 1 30 template <
class ST>
class CStringFeatures;
37 #ifndef DOXYGEN_SHOULD_SKIP_THIS 45 T_ALPHA_BETA_TABLE* table;
53 #endif // DOXYGEN_SHOULD_SKIP_THIS 110 inline int32_t get_learn_a(int32_t line, int32_t column)
const 113 return learn_a[line*2 + column];
119 return learn_b[line*2 + column];
125 return learn_p[offset];
131 return learn_q[offset];
137 return const_a[line*2 + column];
143 return const_b[line*2 + column];
149 return const_p[offset];
155 return const_q[offset];
161 return const_a_val[line];
167 return const_b_val[line];
173 return const_p_val[offset];
179 return const_q_val[offset];
182 inline char get_fix_pos_state(int32_t pos, T_STATES state, T_STATES num_states)
186 if ((pos<0)||(pos*num_states+state>65336))
187 SG_DEBUG(
"index out of range in get_fix_pos_state(%i,%i,%i) \n", pos,state,num_states)
189 return fix_pos_state[pos*num_states+state] ;
198 inline void set_learn_a(int32_t offset, int32_t value)
201 learn_a[offset]=value;
207 learn_b[offset]=value;
213 learn_p[offset]=value;
219 learn_q[offset]=value;
225 const_a[offset]=value;
231 const_b[offset]=value;
237 const_p[offset]=value;
243 const_q[offset]=value;
249 const_a_val[offset]=value;
255 const_b_val[offset]=value;
261 const_p_val[offset]=value;
267 const_q_val[offset]=value;
270 inline void set_fix_pos_state(
272 int32_t pos, T_STATES state, T_STATES num_states,
char value)
275 if ((pos<0)||(pos*num_states+state>65336))
276 SG_DEBUG(
"index out of range in set_fix_pos_state(%i,%i,%i,%i) [%i]\n", pos,state,num_states,(
int)value, pos*num_states+state)
278 fix_pos_state[pos*num_states+state]=value;
279 if (value==FIX_ALLOWED)
280 for (int32_t i=0; i<num_states; i++)
281 if (get_fix_pos_state(pos,i,num_states)==FIX_DEFAULT)
282 set_fix_pos_state(pos,i,num_states,FIX_DISALLOWED) ;
287 const static char FIX_DISALLOWED ;
290 const static char FIX_ALLOWED ;
293 const static char FIX_DEFAULT ;
296 const static float64_t DISALLOWED_PENALTY ;
373 T_STATES trans_list_len ;
374 T_STATES **trans_list_forward ;
375 T_STATES *trans_list_forward_cnt ;
377 T_STATES **trans_list_backward ;
378 T_STATES *trans_list_backward_cnt ;
379 bool mem_initialized ;
381 #ifdef USE_HMMPARALLEL_STRUCTURES 384 struct S_DIM_THREAD_PARAM
392 struct S_BW_THREAD_PARAM
406 inline T_ALPHA_BETA & ALPHA_CACHE(int32_t dim) {
407 return alpha_cache[dim%parallel->get_num_threads()] ; } ;
408 inline T_ALPHA_BETA & BETA_CACHE(int32_t dim) {
409 return beta_cache[dim%parallel->get_num_threads()] ; } ;
410 #ifdef USE_LOGSUMARRAY 412 return arrayS[dim%parallel->get_num_threads()] ; } ;
415 return arrayN1[dim%parallel->get_num_threads()] ; } ;
417 return arrayN2[dim%parallel->get_num_threads()] ; } ;
418 inline T_STATES* STATES_PER_OBSERVATION_PSI(int32_t dim) {
419 return states_per_observation_psi[dim%parallel->get_num_threads()] ; } ;
420 inline const T_STATES* STATES_PER_OBSERVATION_PSI(int32_t dim)
const {
421 return states_per_observation_psi[dim%parallel->get_num_threads()] ; } ;
422 inline T_STATES* PATH(int32_t dim) {
423 return path[dim%parallel->get_num_threads()] ; } ;
424 inline bool & PATH_PROB_UPDATED(int32_t dim) {
425 return path_prob_updated[dim%parallel->get_num_threads()] ; } ;
426 inline int32_t & PATH_PROB_DIMENSION(int32_t dim) {
427 return path_prob_dimension[dim%parallel->get_num_threads()] ; } ;
429 inline T_ALPHA_BETA & ALPHA_CACHE(int32_t ) {
430 return alpha_cache ; } ;
431 inline T_ALPHA_BETA & BETA_CACHE(int32_t ) {
432 return beta_cache ; } ;
433 #ifdef USE_LOGSUMARRAY 441 inline T_STATES* STATES_PER_OBSERVATION_PSI(int32_t ) {
442 return states_per_observation_psi ; } ;
443 inline const T_STATES* STATES_PER_OBSERVATION_PSI(int32_t )
const {
444 return states_per_observation_psi ; } ;
445 inline T_STATES* PATH(int32_t ) {
447 inline bool & PATH_PROB_UPDATED(int32_t ) {
448 return path_prob_updated ; } ;
449 inline int32_t & PATH_PROB_DIMENSION(int32_t ) {
450 return path_prob_dimension ; } ;
509 virtual bool train(
CFeatures* data=NULL);
511 virtual float64_t get_log_model_parameter(int32_t num_param);
512 virtual float64_t get_log_derivative(int32_t num_param, int32_t num_example);
515 return model_probability(num_example);
523 bool initialize_hmm(
Model* model,
float64_t PSEUDO, FILE* model_file=NULL);
527 bool alloc_state_dependend_arrays();
530 void free_state_dependend_arrays();
543 float64_t forward_comp(int32_t time, int32_t state, int32_t dimension);
545 int32_t time, int32_t state, int32_t dimension);
554 float64_t backward_comp(int32_t time, int32_t state, int32_t dimension);
556 int32_t time, int32_t state, int32_t dimension);
579 if (mod_prob_updated)
580 return mod_prob/p_observations->get_num_vectors();
582 return model_probability_comp()/p_observations->get_num_vectors();
585 return forward(p_observations->get_vector_length(dimension), 0, dimension);
598 uint16_t* o=p_observations->get_feature_vector(dimension, len, free_vec);
603 for (int32_t i=0; i<N; i++)
608 p_observations->free_feature_vector(o, dimension, free_vec);
641 void estimate_model_baum_welch(
CHMM* train);
642 void estimate_model_baum_welch_trans(
CHMM* train);
644 #ifdef USE_HMMPARALLEL_STRUCTURES 649 void estimate_model_baum_welch_old(
CHMM* train);
655 void estimate_model_baum_welch_defined(
CHMM* train);
660 void estimate_model_viterbi(
CHMM* train);
665 void estimate_model_viterbi_defined(
CHMM* train);
670 bool linear_train(
bool right_align=
false);
673 bool permutation_entropy(int32_t window_width, int32_t sequence_number);
681 void output_model(
bool verbose=
false);
684 void output_model_defined(
bool verbose=
false);
692 void normalize(
bool keep_dead_states=
false);
697 void add_states(int32_t num_states,
float64_t default_val=0);
710 bool append_model(
CHMM* append_model);
716 void convert_to_log();
719 void init_model_random();
726 void init_model_defined();
732 void clear_model_defined();
735 void copy_model(
CHMM* l);
741 void invalidate_model();
763 #ifdef USE_HMMPARALLEL_STRUCTURES 764 static void* bw_dim_prefetch(
void * params);
765 static void* bw_single_dim_prefetch(
void * params);
766 static void* vit_dim_prefetch(
void * params);
773 inline bool set_fix_pos_state(int32_t pos, T_STATES state,
char value)
777 model->set_fix_pos_state(pos, state, N, value) ;
802 return p_observations;
873 bool load_definitions(FILE* file,
bool verbose,
bool initialize=
true);
910 bool load_model(FILE* file);
915 bool save_model(FILE* file);
920 bool save_model_derivatives(FILE* file);
925 bool save_model_derivatives_bin(FILE* file);
930 bool save_model_bin(FILE* file);
933 bool check_model_derivatives() ;
934 bool check_model_derivatives_combined() ;
941 T_STATES* get_path(int32_t dim,
float64_t& prob);
946 bool save_path(FILE* file);
951 bool save_path_derivatives(FILE* file);
956 bool save_path_derivatives_bin(FILE* file);
959 bool check_path_derivatives() ;
961 #endif //USE_HMMDEBUG 966 bool save_likelihood_bin(FILE* file);
971 bool save_likelihood(FILE* file);
981 inline T_STATES
get_N()
const {
return N ; }
984 inline int32_t
get_M()
const {
return M ; }
994 SG_DEBUG(
"index out of range in set_q(%i,%e) [%i]\n", offset,value,N)
996 end_state_distribution_q[offset]=value;
1007 SG_DEBUG(
"index out of range in set_p(%i,.) [%i]\n", offset,N)
1009 initial_state_distribution_p[offset]=value;
1020 if ((line_>N)||(column>N))
1021 SG_DEBUG(
"index out of range in set_A(%i,%i,.) [%i,%i]\n",line_,column,N,N)
1023 transition_matrix_A[line_+column*N]=value;
1034 if ((line_>N)||(column>N))
1035 SG_DEBUG(
"index out of range in set_a(%i,%i,.) [%i,%i]\n",line_,column,N,N)
1037 transition_matrix_a[line_+column*N]=value;
1048 if ((line_>=N)||(column>=M))
1049 SG_DEBUG(
"index out of range in set_B(%i,%i) [%i,%i]\n", line_, column,N,M)
1051 observation_matrix_B[line_*M+column]=value;
1062 if ((line_>=N)||(column>=M))
1063 SG_DEBUG(
"index out of range in set_b(%i,%i) [%i,%i]\n", line_, column,N,M)
1065 observation_matrix_b[line_*M+column]=value;
1075 int32_t time, T_STATES state, T_STATES value, int32_t dimension)
1078 if ((time>=p_observations->get_max_vector_length())||(state>N))
1079 SG_DEBUG(
"index out of range in set_psi(%i,%i,.) [%i,%i]\n",time,state,p_observations->get_max_vector_length(),N)
1081 STATES_PER_OBSERVATION_PSI(dimension)[time*N+state]=value;
1092 SG_DEBUG(
"index out of range in %e=get_q(%i) [%i]\n", end_state_distribution_q[offset],offset,N)
1094 return end_state_distribution_q[offset];
1105 SG_DEBUG(
"index out of range in get_p(%i,.) [%i]\n", offset,N)
1107 return initial_state_distribution_p[offset];
1118 if ((line_>N)||(column>N))
1119 SG_DEBUG(
"index out of range in get_A(%i,%i) [%i,%i]\n",line_,column,N,N)
1121 return transition_matrix_A[line_+column*N];
1132 if ((line_>N)||(column>N))
1133 SG_DEBUG(
"index out of range in get_a(%i,%i) [%i,%i]\n",line_,column,N,N)
1135 return transition_matrix_a[line_+column*N];
1146 if ((line_>=N)||(column>=M))
1147 SG_DEBUG(
"index out of range in get_B(%i,%i) [%i,%i]\n", line_, column,N,M)
1149 return observation_matrix_B[line_*M+column];
1160 if ((line_>=N)||(column>=M))
1161 SG_DEBUG(
"index out of range in get_b(%i,%i) [%i,%i]\n", line_, column,N,M)
1164 return observation_matrix_b[line_*M+column];
1174 int32_t time, T_STATES state, int32_t dimension)
const 1177 if ((time>=p_observations->get_max_vector_length())||(state>N))
1178 SG_DEBUG(
"index out of range in get_psi(%i,%i) [%i,%i]\n",time,state,p_observations->get_max_vector_length(),N)
1180 return STATES_PER_OBSERVATION_PSI(dimension)[time*N+state];
1268 #ifdef USE_HMMPARALLEL_STRUCTURES 1273 #else //USE_HMMPARALLEL_STRUCTURES 1278 #endif //USE_HMMPARALLEL_STRUCTURES 1280 #ifdef USE_LOGSUMARRAY 1281 #ifdef USE_HMMPARALLEL_STRUCTURES 1287 #endif // USE_HMMPARALLEL_STRUCTURES 1288 #endif // USE_LOGSUMARRAY 1290 #ifdef USE_HMMPARALLEL_STRUCTURES 1293 T_ALPHA_BETA* alpha_cache ;
1295 T_ALPHA_BETA* beta_cache ;
1298 T_STATES** states_per_observation_psi ;
1304 bool* path_prob_updated ;
1307 int32_t* path_prob_dimension ;
1309 #else //USE_HMMPARALLEL_STRUCTURES 1310 T_ALPHA_BETA alpha_cache;
1327 #endif //USE_HMMPARALLEL_STRUCTURES 1370 int32_t time, int32_t state, int32_t dimension)
1372 return forward(time, state, dimension) + backward(time, state, dimension) - model_probability(dimension);
1377 int32_t time, int32_t state_i, int32_t state_j, int32_t dimension)
1379 return forward(time, state_i, dimension) +
1380 backward(time+1, state_j, dimension) +
1381 get_a(state_i,state_j) + get_b(state_j,p_observations->
get_feature(dimension ,time+1)) - model_probability(dimension);
1394 T_STATES i, uint16_t j, int32_t dimension)
1398 for (int32_t k=0; k<N; k++)
1400 if (k!=i || p_observations->
get_feature(dimension, k) != j)
1401 der+=get_b(k, p_observations->
get_feature(dimension, k));
1412 return backward(0,i,dimension)+get_b(i, p_observations->
get_feature(dimension, 0));
1459 best_path(dimension);
1460 return (i==PATH(dimension)[0]) ? (exp(-get_p(PATH(dimension)[0]))) : (0) ;
1466 best_path(dimension);
1473 prepare_path_derivative(dimension) ;
1474 return (get_A(i,j)==0) ? (0) : (get_A(i,j)*exp(-get_a(i,j))) ;
1480 prepare_path_derivative(dimension) ;
1481 return (get_B(i,j)==0) ? (0) : (get_B(i,j)*exp(-get_b(i,j))) ;
1492 bool get_numbuffer(FILE* file,
char* buffer, int32_t length);
1496 void open_bracket(FILE* file);
1499 void close_bracket(FILE* file);
1502 bool comma_or_space(FILE* file);
1505 inline void error(int32_t p_line,
const char* str)
1508 SG_ERROR(
"error in line %d %s\n", p_line, str)
1517 if (path_deriv_updated && (path_deriv_dimension==dim))
1533 set_A(PATH(dim)[t], PATH(dim)[t+1], get_A(PATH(dim)[t], PATH(dim)[t+1])+1);
1534 set_B(PATH(dim)[t], p_observations->
get_feature(dim,t), get_B(PATH(dim)[t], p_observations->
get_feature(dim,t))+1);
1537 path_deriv_dimension=dim ;
1538 path_deriv_updated=true ;
1548 if (ALPHA_CACHE(dimension).table && (dimension==ALPHA_CACHE(dimension).dimension) && ALPHA_CACHE(dimension).updated)
1550 if (time<p_observations->get_vector_length(dimension))
1551 return ALPHA_CACHE(dimension).table[time*N+state];
1553 return ALPHA_CACHE(dimension).sum;
1556 return forward_comp(time, state, dimension) ;
1562 if (BETA_CACHE(dimension).table && (dimension==BETA_CACHE(dimension).dimension) && (BETA_CACHE(dimension).updated))
1565 return BETA_CACHE(dimension).sum;
1566 if (time<p_observations->get_vector_length(dimension))
1567 return BETA_CACHE(dimension).table[time*N+state];
1572 return backward_comp(time, state, dimension) ;
int32_t * learn_p
start states to be learned
float64_t * transition_matrix_a
transition matrix
int32_t get_const_p(int32_t offset) const
get entry out of const_p vector
bool mod_prob_updated
true if model probability is up to date
int32_t N
number of states
float64_t backward(int32_t time, int32_t state, int32_t dimension)
inline proxies for backward pass
static const int32_t GOTp
float64_t * const_a_val
values for transitions that have constant probability
virtual int32_t get_num_model_parameters()
void set_const_p(int32_t offset, int32_t value)
set value in const_p vector
float64_t pat_prob
probability of best path
float64_t get_const_p_val(int32_t offset) const
get value out of const_p_val vector
void set_const_p_val(int32_t offset, float64_t value)
set value in const_p_val vector
static const float64_t INFTY
infinity
T_STATES * states_per_observation_psi
backtracking table for viterbi can be terrible HUGE O(T*N)
float64_t forward(int32_t time, int32_t state, int32_t dimension)
inline proxies for forward pass
float64_t * const_q_val
values for end states that have constant probability
bool all_path_prob_updated
true if path probability is up to date
float64_t epsilon
convergence criterion epsilon
static const int32_t GOTconst_p
viterbi only for defined transitions/observations
int32_t get_M() const
access function for number of observations M
baum welch only for defined transitions/observations
int32_t get_learn_p(int32_t offset) const
get entry out of learn_p vector
int32_t * learn_b
emissions to be learned
float64_t * transition_matrix_A
matrix of absolute counts of transitions
static const int32_t GOTlearn_a
float64_t path_derivative_b(T_STATES i, uint16_t j, int32_t dimension)
computes d log p(lambda,best_path)/d b_ij
T_ALPHA_BETA beta_cache
cache for backward variables can be terrible HUGE O(T*N)
bool path_prob_updated
true if path probability is up to date
float64_t get_b(T_STATES line_, uint16_t column) const
float64_t state_probability(int32_t time, int32_t state, int32_t dimension)
calculates probability of being in state i at time t for dimension
static const int32_t GOTO
float64_t * observation_matrix_B
matrix of absolute counts of observations within each state
float64_t T_ALPHA_BETA_TABLE
type for alpha/beta caching table
Base class Distribution from which all methods implementing a distribution are derived.
float64_t linear_model_derivative(T_STATES i, uint16_t j, int32_t dimension)
static const int32_t GOTlearn_p
float64_t * const_b_val
values for emissions that have constant probability
static const int32_t GOTlearn_q
uint16_t get_best_path_state(int32_t dim, int32_t t)
CStringFeatures< uint16_t > * get_observations()
return observation pointer
int32_t path_prob_dimension
dimension for which path_prob was calculated
virtual int32_t get_vector_length(int32_t vec_num)
int32_t * learn_q
end states to be learned
void set_pseudo(float64_t pseudo)
sets current pseudo value
float64_t model_probability(int32_t dimension=-1)
inline proxy for model probability.
int32_t path_deriv_dimension
dimension for which path_deriv was calculated
static const int32_t GOTb
int32_t get_const_q(int32_t offset) const
get entry out of const_q vector
float64_t get_const_q_val(int32_t offset) const
get value out of const_q_val vector
float64_t mod_prob
probability of model
float64_t get_const_a_val(int32_t line) const
get value out of const_a_val vector
virtual const char * get_name() const
T_STATES get_N() const
access function for number of states N
float64_t get_q(T_STATES offset) const
float64_t model_derivative_q(T_STATES i, int32_t dimension)
float64_t * const_p_val
values for start states that have constant probability
virtual float64_t get_log_likelihood_example(int32_t num_example)
void set_p(T_STATES offset, float64_t value)
float64_t get_A(T_STATES line_, T_STATES column) const
static const int32_t GOTconst_a
float64_t * end_state_distribution_q
distribution of end-states
float64_t PSEUDO
define pseudocounts against overfitting
float64_t all_pat_prob
probability of best path
float64_t path_derivative_a(T_STATES i, T_STATES j, int32_t dimension)
computes d log p(lambda,best_path)/d a_ij
void set_const_q_val(int32_t offset, float64_t value)
set value in const_q_val vector
float64_t transition_probability(int32_t time, int32_t state_i, int32_t state_j, int32_t dimension)
calculates probability of being in state i at time t and state j at time t+1 for dimension ...
float64_t get_const_b_val(int32_t line) const
get value out of const_b_val vector
T_STATES get_psi(int32_t time, T_STATES state, int32_t dimension) const
int32_t * const_q
end states that have constant probability
CStringFeatures< uint16_t > * p_observations
observation matrix
float64_t get_p(T_STATES offset) const
void set_learn_q(int32_t offset, int32_t value)
set value in learn_q vector
void set_A(T_STATES line_, T_STATES column, float64_t value)
void set_q(T_STATES offset, float64_t value)
void set_B(T_STATES line_, uint16_t column, float64_t value)
int32_t iterations
convergence criterion iterations
int32_t get_const_b(int32_t line, int32_t column) const
get entry out of const_b matrix
static const int32_t GOTq
static const int32_t GOTlearn_b
float64_t get_a(T_STATES line_, T_STATES column) const
float64_t * observation_matrix_b
distribution of observations within each state
float64_t model_derivative_a(T_STATES i, T_STATES j, int32_t dimension)
computes log dp(lambda)/d a_ij.
void set_const_b_val(int32_t offset, float64_t value)
set value in const_b_val vector
bool path_deriv_updated
true if path derivative is up to date
bool set_epsilon(float64_t eps)
void sort_learn_a()
sorts learn_a matrix
void set_learn_p(int32_t offset, int32_t value)
set value in learn_p vector
bool set_iterations(int32_t num)
float64_t linear_model_probability(int32_t dimension)
void set_learn_b(int32_t offset, int32_t value)
set value in learn_b matrix
float64_t * initial_state_distribution_p
initial distribution of states
baum welch only for specified transitions
float64_t get_pseudo() const
returns current pseudo value
all of classes and functions are contained in the shogun namespace
float64_t path_derivative_p(T_STATES i, int32_t dimension)
computes d log p(lambda,best_path)/d p_i
T sum(const Container< T > &a, bool no_diag=false)
float64_t model_derivative_p(T_STATES i, int32_t dimension)
int32_t * const_b
emissions that have constant probability
int32_t get_const_a(int32_t line, int32_t column) const
get entry out of const_a matrix
void sort_learn_b()
sorts learn_b matrix
The class Features is the base class of all feature objects.
static const int32_t GOTconst_b
int32_t get_learn_q(int32_t offset) const
get entry out of learn_q vector
float64_t get_B(T_STATES line_, uint16_t column) const
void set_const_a_val(int32_t offset, float64_t value)
set value in const_a_val vector
void set_const_a(int32_t offset, int32_t value)
set value in const_a matrix
void set_b(T_STATES line_, uint16_t column, float64_t value)
float64_t path_derivative_q(T_STATES i, int32_t dimension)
computes d log p(lambda,best_path)/d q_i
int32_t get_learn_b(int32_t line, int32_t column) const
get entry out of learn_b matrix
static const int32_t GOTM
void prepare_path_derivative(int32_t dim)
initialization function that is called before path_derivatives are calculated
static void sort(int32_t *a, int32_t cols, int32_t sort_col=0)
static const int32_t GOTconst_q
void set_psi(int32_t time, T_STATES state, T_STATES value, int32_t dimension)
void set_a(T_STATES line_, T_STATES column, float64_t value)
static float64_t logarithmic_sum(float64_t p, float64_t q)
static const int32_t GOTN
virtual ST get_feature(int32_t vec_num, int32_t feat_num)
T_STATES * path
best path (=state sequence) through model
int32_t * const_p
start states that have constant probability
void set_const_b(int32_t offset, int32_t value)
set value in const_b matrix
void set_const_q(int32_t offset, int32_t value)
set value in const_q vector
void error(int32_t p_line, const char *str)
parse error messages
float64_t model_derivative_b(T_STATES i, uint16_t j, int32_t dimension)
computes log dp(lambda)/d b_ij.
static const int32_t GOTa