Transition probability matrix for markov chain

Hi there

I have time, speed and acceleration data for a car in three columns. I'm trying to generate a 2 dimensional transition probability matrix of velocity and acceleration.

The concept is given a particular speed and acceleration I would like to know the next most likely (probable) speed and acceleration.

I have some code below, but cannot fully understand it. Will it generate a 2D transition matrix or a 4D transition matrix?

Thank you

   %%First bin data into categories
speedBinN = 5;
aceelBinN = 5;
speed = binit( data(:,2), linspace(min(data(:,2)),max(data(:,2)),speedBinN) ); % bin them into categories
accel = binit( data(:,3), linspace(min(data(:,3)),max(data(:,3)),aceelBinN) );

%%count up transitions
transCountMat = zeros(speedBinN,aceelBinN,speedBinN,aceelBinN);
for ii = 1:size(data,1)-1
  transCountMat( speed(ii),accel(ii),speed(ii+1),accel(ii+1) ) = transCountMat( speed(ii),accel(ii),speed(ii+1),accel(ii+1) ) + 1;
end

%%calculate probabilities
sumOverPossibleDestinations = sum( sum(transCountMat, 4), 3);
transMat = bsxfun( @rdivide, transCountMat, sumOverPossibleDestinations );

%%User Interactive stuff
IM = imagesc(squeeze(transMat(1,1,:,:)));
colorbar
set(IM,'ButtonDownFcn',@bdFcn)
set(gca,'ydir','normal')
ylabel speed
xlabel accel
hold on
p = plot(1,1,'w');
updateIndicator(1,1)

Answer 1

[Walter Roberson]

Looks to me like it will generate a 2D output for transMat. The count matrix is 4 dimensional, but it is summed twice, which reduces that to 2 dimensions.

Looks to me like binit() is just the second output of histc(). With the linspace nature of the bins, that operation could probably be made more efficient than even histc(). Also the transcount loop could probably be replaced with a single accumarray call.

Answer 2

[John]

Hi Walter,

Thank you for your reply and for explaining this to me. I'm happy that it generates a 2D output.

The code prints out the values of each element in the matrix. For example

val(:,:,1,3) =

       NaN    0.2000    0.7692    0.0043         0
         0         0    0.1294         0       NaN
         0         0         0         0       NaN
       NaN       NaN         0         0       NaN
       NaN       NaN       NaN         0       NaN

How can I make it just print out the actual matrix? I understand that this is probably a simple question but I don't know to do this.

I appreciate your help.

Thank you

[Walter Roberson]

There is no "val" in the code you show, so I am unsure what you are asking about?

When MATLAB displays a multidimensional matrix (4 dimensions in this case), it displays a "page" at a time, where a "page" is the first 2 dimensions. What format would you like the 4 dimensional matrix printed out in?

[Walter Roberson]

Hmmm, looking again, it appears that transMat will be 4 dimensional, not the 2 dimensional that I thought.

Answer 3

[John]

Hi Walter,

Would you know how to change the code to produce a 2D transition probability matrix of velocity and acceleration?

I've uploaded a sample data set to sendspace.com http://www.sendspace.com/file/oqx54r

And here is the full code

Thank you for your help

function transMat = mwExample

load('Sample data set mathworks.mat')

%%First bin data into categories
speedBinN = 5;
aceelBinN = 5;
speed = binit( data(:,2), linspace(min(data(:,2)),max(data(:,2)),speedBinN) ); % bin them into categories
accel = binit( data(:,3), linspace(min(data(:,3)),max(data(:,3)),aceelBinN) );

%%count up transitions
transCountMat = zeros(speedBinN,aceelBinN,speedBinN,aceelBinN);
for ii = 1:size(data,1)-1
  transCountMat( speed(ii),accel(ii),speed(ii+1),accel(ii+1) ) = transCountMat( speed(ii),accel(ii),speed(ii+1),accel(ii+1) ) + 1;
end

%%calculate probabilities
sumOverPossibleDestinations = sum( sum(transCountMat, 4), 3);
transMat = bsxfun( @rdivide, transCountMat, sumOverPossibleDestinations );

%%User Interactive stuff
IM = imagesc(squeeze(transMat(1,1,:,:)));
colorbar
set(IM,'ButtonDownFcn',@bdFcn)
set(gca,'ydir','normal')
ylabel speed
xlabel accel
hold on
p = plot(1,1,'w');
updateIndicator(1,1)

Answer 4

[Hanane]

Hi; what is the role of this function ''binit''?

[BolinSV]

I believe it is applied to divide the data into different bins in equal number.

Answer 5

[Harini pushparaj]

@john..HI can i get your sample data file ..I maybe useful for my work ..I don't understand what is binit is ..it will be great if you could help me..Thank you!!

[Walter Roberson]

It looks to me as if the code for binit would be

function indices = binit(vector, edges)
  [~, indices] = histc(vector, edges);

[Harini pushparaj]

if i use binit ..i am getting error saying undefined binit and if i use histc..there is no error ..how come?

[Walter Roberson]

You would need to store the above two lines in binit.m in your code directory.

Answer 6

[shahab anjum]

please help me too if i have 1000x286 matrix how can i calculate the transistion and emission probabilites of that matrix plz

help

[Walter Roberson]

What do the entries in the matrix indicate? For example what does the entry at (793,271) mean?

Is it a matrix of counts? Is the matrix normalized by row? By column?

[shahab anjum]

i just scale the data by using following code

function dataout=scaledata(datain,minval,maxval)
dataout=datain-min(datain(:));
dataout=(dataout/range(dataout(:)))*(maxval-minval);
dataout=dataout+minval;
end

and (793,271) entry is 0.1954

[Walter Roberson]

Scaling the data does not tell me how to interpret the entries. Does the (793,271) entry mean that if you managed to arrive at state 271 then there is a probability 0.1954 that you transition to state 793? If so why is it not a square matrix?

[shahab anjum]

because i have to work on that kind of matrix

can u please build the code for me please

[Walter Roberson]

No, I do not understand what the matrix elements designate.

You talk about transmission and emission probabilities. Are you doing a hidden Markov model?

[shahab anjum]

yes im please can u help me with this im really stuck since last 4 months but still dont found soluion

[Walter Roberson]

What you have described of your data does not appear to be data suitable for Hidden Markov Model.

[shahab anjum]

can u please describe the reason please.

i have to implement HMM on this data :(

can u please help

[Walter Roberson]

HMM requires a symbol list. You are trying to deduce the internal states of a Markov Chain that takes into account multiple symbols in a row (that is, if you had ABC then the probability of B->C might be different than if you had DBC). In order to do that you need observed sequences of symbols.

All I know about what you have instead is that it is a 1000 x 286 numeric matrix. That is not a sequence of symbols.

Not unless perhaps each row of the matrix is a "sample", and you have (for whatever reason) 286 symbols in a row of sample data, and the numeric contents of the array are symbol numbers ???

[shahab anjum]

in image processing there is also a matrix with numeric values. but i found many codes but icant implement that :(

[Walter Roberson]

The way you processed your data originally is not compatible with the possibility that your array is an image.

There appear to be a number of techniques available for HMM processing of images for different purposes.

https://www.intechopen.com/books/reviews-refinements-and-new-ideas-in-face-recognition/hidden-markov-models-in-automatic-face-recognition-a-review

[Attilio Pittelli]

you spoke about a list, but in the previous example he got the velocity and acceleration matrix. In my case i've got a double matrix of those inputs: a duration and a sequence of values. I'm trying to code it out but i'm still getting a transition probability matrix of 0 or 1 and the most of the outputs are 0 and it's not working. Do you have any suggestion? I'm really stucked at this point

Thank you