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

We introduce an integrated approach to the study of visual navigation strategies
based on a combination of the optimal information foraging theory and Hidden
Markov Models (HMMs). This approach visualizes users' navigation trails through
an information space with reference to an indicator of the profitability of each
document. The information space is organized based on a spatial-semantic mapping
so that similar documents tend to appear near to each other. Explicit links highlight
strongly similar documents. The profitability of a document therefore relies on the
semantics of the immediate neighboring area in which the given document resides.
If we know that one area contains one document relevant to the query, then it is
more likely that its nearby neighboring documents are also relevant to the query. In
this way, we can translate the optimal information foraging theory into observable
attributes associated with users' visual navigation strategies. Next, we present a
conceptual framework that accommodates the optimal information foraging theory,
Hidden Markov Models, spatial-semantic interfaces, and a taxonomy of visual
navigation. Then, we describe each component of the framework. The overall
approach is illustrated through an example in which visual navigation data were
drawn from an information retrieval experiment. Finally, implications of this
approach for understanding users' navigation strategies are discussed.

4.1.4.1 Hidden Markov Models

Hidden Markov Models (HMMs) are widely used in signal processing and speech
recognition. If we conceptualize users' navigation as a sequence of observable
actions, such as clicking on a node or marking a node, we would expect that
behavioral patterns of navigation are likely to be governed by a latent cognitive
process, which is opaque to observers. For example, cognitive processes behind the
scene may include estimating the profitability of a document cluster and assessing
the relevance of a particular document. HMMs provide a potentially useful tool
to model such dual-process sequences. Given a sequence of observed actions, one
may want to know the dynamics of the underlying process. Given a model of an
underlying process, one may like to see what sequence is most likely to be observed.
Thus an HMM-based approach provides a suitable way to study users' navigation
strategies as an information foraging process.
Hidden Markov Models are defined in terms of states and observations. States
are not observable, whereas observations are observable and they are probabilistic
functions of states. A stochastic process governs state transitions, which means at
each step the process of change is controlled by probabilities. Observations are also
a stochastic process. An HMM can be defined as follows:

N denotes the number of hidden states
Q denotes the set of states Q Df 1, 2, :::,N g
M denotes the number of symbols, or observations
V denotes the set of symbols V Df 1, 2, :::,M g
A denotes the state-transition probability matrix