Beyond Classification Tasks - Data Mining with Decision Trees: Theory and Applications - page 97

a single HMM. When the user performs a new task, we first employ her
attributes to find the suitable node in each of the goal trees. Then, based
on the actions the user has already performed in implementing this task, we
anticipate the goal she is trying to accomplish and the action she intends
to perform next.
In a typical sequence learning problem, a training set of sequences S =

{ s 1 ,s 2 ,...,s m }

is given. Each sequence s j ∈ S is an ordered set of n j

{ , e 2 ,..., e n j }

elements (actions) . G denotes the set of all possible goals

(for example, in an email application G =

e

1

{ 'Add recipient', 'Send an email',

'Read email' ). Each training sequence is associated with one goal and

several characterizing attributes. The notation U denotes the set of input
attributes containing η attributes: U = {v 1 ,...,v η }

}

. The domain (possible
values for each attribute) of an attribute is denoted by dom ( v i ). User space
(the set of all possible users) is defined as a Cartesian product of all the
input attribute domains. The input in the problem consists of a set of m
records and is denoted as Train =( s 1 ,g 1 ,u 1 ,..., s m ,g m ,u m )where

s q ∈ U .

The notation L represents a probabilistic sequence learning algorithm
such as HMM. We mainly focus on HMM, but the same algorithm can be
used with other base models, for example, conditional random field (CRF)
as a base model. These algorithms generate models that can estimate the
conditional probability of a goal g given a sequence and the input user
attributes. Let λ represent a probabilistic model which was induced by
activating L onto dataset Train . In this case, we would like to estimate
the conditional probability p λ ( G = g j |

S, g q ∈ G, u q ∈

s q ,u q ) of a sequence s q that was
generated by user u q . Thus, the aim of intention prediction is to find the
most accurate probability estimations.
As indicated in Figure 8.1, we are using a tree structure to improve the
accuracy of training models. For each goal in the system, a different tree
is generated. This structure is built using user attributes in an attempt to
differentiate between various usage behaviors in the system. For example,
in Figure 1 we are employing the age, gender and device for differentiating
between usage behaviors. In this structure, each node contains a model
andanattribute v i that splits the node. Assuming this tree structure, the
problem can be formally phrased as follows:
Given a sequence learning algorithm L and a training set Train with
input sessions set S ,users U and goals G , the aim is to find an optimal set
of trees (a tree for each goal). Optimality is defined in terms of minimizing
prediction errors.