#include <stochTable.h>

Classes
struct	stoch_value

Public Member Functions
	stochTable (size_t)
	~stochTable ()
void	push (size_t pos, size_t st, size_t st_to, float val)
std::string	stringify ()
	Stringify the stochTable.
void	print ()
	Prints the stochTable to stdout.
void	finalize ()
size_t	get_state_position (size_t pos, uint16_t)
void	traceback (traceback_path &path)

Private Attributes
size_t	last_position
std::vector< stoch_value > *	state_val
std::vector< size_t > *	position

Detailed Description

Stochastic table stores stochastic values in a vector. Data structure is implemented to reduce the memory that would be needed if we allocated a 2D table with all the transitions. This lookup table is 1D and only stores those values which we add. Each the value are stores (Current state, Previous State, Score as P(X)). In addition, the indices of each state and position are recorded so that they can be referenced quickly. So the memory size necessary to store the values for a sparsely connected model are greatly reduce. However, the time to recreate the table is increased because it doesn't allocate the memory up front, but rather pushes values as they are recorded.

Definition at line 34 of file stochTable.h.

Constructor & Destructor Documentation

StochHMM::stochTable::stochTable ( size_t seq_size )

stochTable constructor

Parameters:

[in] seq_size Size of sequence

Definition at line 15 of file stochTable.cpp.

References last_position, position, and state_val.

                                             :state_val(NULL){
                
                state_val = new(std::nothrow) std::vector<stoch_value>;
                state_val->reserve(seq_size);
                
                position = new(std::nothrow) std::vector<size_t>(seq_size,0);
                if (state_val == NULL){
                        std::cerr << "Cannot allocate stochTable- OUT OF MEMORY" << std::endl;
                        delete state_val;
                        delete position;
                        state_val = NULL;
                        position = NULL;
                        exit(2);
                }
                last_position = 0;
                return;
        }

StochHMM::stochTable::~stochTable ( )

Definition at line 33 of file stochTable.cpp.

References position, and state_val.

                               {
                delete state_val;
                delete position;
                state_val = NULL;
                position = NULL;
        }

Member Function Documentation

void StochHMM::stochTable::finalize ( )

Finalized stochTable Normalizes the traceback pointer values and calculates the previous cell iterator within the previous position segment. This speeds up the the referencing necessary for tracebacks across the traceback table.

Definition at line 59 of file stochTable.cpp.

References StochHMM::addLog(), get_state_position(), last_position, position, SIZE_MAX, and state_val.

Referenced by StochHMM::trellis::naive_stochastic_forward(), StochHMM::trellis::naive_stochastic_viterbi(), StochHMM::trellis::simple_stochastic_forward(), and StochHMM::trellis::simple_stochastic_viterbi().

                                 {
                (*position)[last_position] = state_val->size()-1;
                
                last_position = 0;
                
                double sum(-INFINITY);
                uint16_t current_state(SIZE_MAX);
                size_t state_start(-1);
                
                //For each position in the sequence we want to normalize the viterbi/forward values
                //for the state from previous states
                for(size_t i=0;i<position->size()-1;++i){
                        
                        //Need to sum the values.  If we see another state then we'll need to
                        //normalize the previous states that contributed to the sum.
                        //Then set the sum for the current state.
                        for (size_t j = (i==0) ? 0 : (*position)[i-1]+1; j <= (*position)[i] ; ++j ){
                                
                                //If this is a different state then we'll need to apply the sum
                                //if this is the first state then we'll just set the current state
                                //and set the sum value.  Also need to keep track of which state
                                // is the first state so when we normalize we only normalize the
                                // the previous state
                                if ((*state_val)[j].state_id != current_state){
                                        
                                        //Normalize
                                        for(size_t k = state_start; k < j ;++k){
                                                (*state_val)[k].prob = exp((*state_val)[k].prob - sum);
                                        }
                                        
                                        //Set state and sum value and starting state
                                        current_state = (*state_val)[j].state_id;
                                        sum = (*state_val)[j].prob;
                                        state_start = j;
                                }
                                else{
                                        sum = addLog(sum,(double) (*state_val)[j].prob);
                                }
                        }
                        
                        //Normalize the last states seen (b/c) we'll exit out of for loop before
                        //we have done these
                        for(size_t k = state_start; k <= (*position)[i]; ++k){
                                (*state_val)[k].prob = exp((*state_val)[k].prob - sum);
                        }
                        
                        //Set values for next loop
                        state_start = (*position)[i] + 1;
                        current_state = SIZE_MAX;
                }
                
                
                //Process and normalize the ending cell
                //Calculate ending state sum
                sum = -INFINITY;
                for (size_t j=state_start; j < state_val->size();j++){
                        sum=addLog(sum,(double)(*state_val)[j].prob);
                }
                
                //Normalize the ending cell probability
                for (size_t j=state_start; j < state_val->size();j++){
                        (*state_val)[j].prob = exp((*state_val)[j].prob - sum);
                }
                
                
                
                
                //Assign previous cell relative to (position) value.  Used when traceback
                //That way function won't have to search for correct value;
                for (size_t i =1; i < position->size(); ++i){
                        for (size_t j = (*position)[i-1]+1; j <= (*position)[i] ; ++j){
                                (*state_val)[j].prev_cell = get_state_position(i-1, (*state_val)[j].state_prev);
                        }
                }
                
                return;
        }

size_t StochHMM::stochTable::get_state_position	(	size_t	pos,
		uint16_t	state
	)

Returns the states iterator position within the array

Parameters:

pos	Position within the sequence
state	Iterator of state that you want

Returns:: Position within the table where state can be found

Definition at line 141 of file stochTable.cpp.

References position, state_val, and UINT16_MAX.

Referenced by finalize().

                                                                       {
                size_t start_val = (pos == 0) ? 0 : (*position)[pos-1]+1;
                for (size_t i = start_val ; i <= (*position)[pos] ;  ++i){
                        if ((*state_val)[i].state_id == state){
                                return i-start_val;
                        }
                }
                
                return UINT16_MAX;
        }

void StochHMM::stochTable::print ( )

Prints the stochTable to stdout.

Definition at line 153 of file stochTable.cpp.

References stringify().

                              {
                std::cout << stringify();
                return;
        }

void StochHMM::stochTable::push	(	size_t	pos,
		size_t	st,
		size_t	st_to,
		float	value
	)

Pushes the information for traceback pointer onto the table

Parameters:

pos	Position of current traceback pointer in sequence
st	Current State
st_to	Previous State
value	Unnormalized value of traceback pointer

See also:: stochTable::finalize

Definition at line 46 of file stochTable.cpp.

References last_position, and state_val.

Referenced by StochHMM::trellis::naive_stochastic_forward(), StochHMM::trellis::naive_stochastic_viterbi(), StochHMM::trellis::simple_stochastic_forward(), and StochHMM::trellis::simple_stochastic_viterbi().

                                                                             {
                if (pos != last_position){
                        (*position)[last_position] = state_val->size()-1;
                        last_position = pos;
                }
                
                state_val->push_back( stoch_value(st,st_to,value));
        }

std::string StochHMM::stochTable::stringify ( )

Stringify the stochTable.

Definition at line 159 of file stochTable.cpp.

References last_position, and position.

Referenced by print().

                                       {
                std::stringstream str;
                
                last_position = 0;
                
                for(size_t i=0;i<position->size();++i){
                        for (size_t j = (i==0) ? 0 : (*position)[i-1]+1 ; j <= (*position)[i] ; ++j ){
                                str << (*state_val)[j].state_id <<":"<< (*state_val)[j].state_prev << " : " << (*state_val)[j].prob << "\t";
                        }
                        str << std::endl;
                }
                return str.str();
        }

void StochHMM::stochTable::traceback ( traceback_path & path )

Traceback through the table using the traceback probabilities

Parameters:

[out] path Reference to traceback_path

Definition at line 177 of file stochTable.cpp.

References position, StochHMM::traceback_path::push_back(), SIZE_MAX, and UINT16_MAX.

Referenced by StochHMM::trellis::stochastic_traceback().

                                                      {
                
                double random((double)rand()/((double)(RAND_MAX)+(double)(1)));
                double cumulative_prob(0.0);
                //std::cout << random << std::endl;
                
                size_t offset(0);
                uint16_t state_prev(UINT16_MAX);
                
                //Get traceback from END state
                for(size_t i = (*position)[position->size()-2]+1 ; i <= position->back() ; ++i){
                        cumulative_prob += (*state_val)[i].prob;
                        if (random <= cumulative_prob){
                                state_prev = (*state_val)[i].state_prev;
                                path.push_back(state_prev);
                                offset = (*state_val)[i].prev_cell;
                                //std::cout << "Chose:\t" << state_prev << std::endl;
                                break;
                        }
                }
                
                //For the rest of the table traceback to the beginning of the sequence
                for(size_t i = position->size()-2; i != SIZE_MAX ; --i){
                        random = (double)rand()/((double)(RAND_MAX)+(double)(1));
                        //std::cout << random << std::endl;
                        cumulative_prob = 0;
                        
                        for (size_t cells = (i == 0) ? 0 + offset : (*position)[i-1]+offset+1; cells <= (*position)[i] ; ++cells){
//                              if ((*state_val)[cells].state_id != state_prev ){
//                                      std::cout << "Houston, We have an error!" << std::endl;
//                              }
                
                                cumulative_prob+=(*state_val)[cells].prob;
                                
                if (random <= cumulative_prob){
                    state_prev = (*state_val)[cells].state_prev;
                                        path.push_back(state_prev);
                                        offset = (*state_val)[cells].prev_cell;
                                        //std::cout << "Chose:\t" << state_prev << std::endl;
                                        break;
                }
            }
                }
                return;
        }