Trajectories of Search - Mapping Scientific Frontiers: The Quest for Knowledge Visualization - page 151

2 3

a 11 a 12 ::: a 1N

4 5

::: ::: a ij :::

A D

::: ::: ::: :::

a N1 a N2 ::: a NN

where a ij D P(q t Dj q t 1 D i), 1 k M
B denotes the observation probability distribution:
B j (k) D P(o t D k j q t D j), 1 k M
denotes the initial state distribution:
i D P(q 1 D i), 1 i N
œ denotes the entire HMM model œ D (A, B, )
An HMM is completely defined by œ D (A, B, ), which are known as parameters
of the model. HMMs are typically used in the following scenarios:

Given observation O D (o1, o2, :::, oT) and model œ D (A, B, ), efficiently
compute P(O j œ).
Given two models œ1andœ2, this can be used to choose the better one.
Given observation O D (o1, o2, :::, oT) and model œ find the optimal state sequence
q D (q1, q2, :::,qT).
Given O D (o1, o2, :::, oT), estimate model parameters œ D (A, B, )that

maximize P(O j œ).

A well-known algorithm from Viterbi has been widely used to find the most
likely path through a given HMM for each sequence, although for small state spaces
it is possible to work out the answer using a brute-force approach.
In order to apply HMMs to users' navigation sequences observed in each
thematic space, we derived the transition matrix and observation probability as
follows. The state space is defined by all the documents in a thematic space. Each
document defines a unique state:

d1 ! S 1 ,d 2 ! S 2 , :::,d N ! S N

A user's trail is defined by a sequence of profitability estimates of documents
perceived by the user in a course of visual navigation. Since this is not directly
observable, we modeled such sequences as a stochastic process. Thus each trail
corresponds to a state transition sequence S Df S i1 ,S i2 ,S i3 , ::: g . The state transition
probability matrix is derived from the sequence of documents visited by a user in
his/her session.

d i ! d j
d i

a ij D

The observation probabilities reflect the underlying stochastic process - the
perceived profitability of a sequence of documents. Three observation symbols
are defined: ok, K D 1, 2, 3. O1 denotes the user's mouse cursor moves over a
document. O2 denotes the user clicks on the document. O3 denotes the user marks
the document as relevant. A sequence of observed symbols could be O Df 1, 1, 1, 2,
1, 1, 2, 3, ::: g . The observation probability is also estimated from the log files: