Many real world applications depend on modeling the temporal dynamics of streams of diverse events, many of which are rare. We introduce a novel model class, Conjoint Piecewise-Constant Conditional Intensity Models, and a learning algorithm that together yield a data-driven approach to parameter sharing with the aim of better modeling such event streams. We empirically demonstrate that our approach yields more accurate models of two real world data sets: search query logs and data center system logs.
Event streams—temporal sequences of discrete events,
are ubiquitous in many domains such as the firing
patterns of neurons [
In many domains, it is valuable to model fine
distinctions between event types. For example, in targeted
advertising, it is valuable to distinguish whether a user
will issue queries related to mental health or to back
pain rather than simply predicting that a user will
issue a healthcare query. In a data center, it is more
useful to learn that particular disk errors predict failed
reboots than to know that generic error messages
predict generic failures. While useful to model, such fine
grained event types are rarer than the coarser grained
ones that include them, and are therefore more difficult
to model. Many models of temporal dependencies in
event streams, such as the Piecewise-Constant
Conditional Intensity Model (PCIM) [
In this paper, we address this problem using parameter sharing, by introducing Conjoint PiecewiseConstant Conditional Intensity Models (C-PCIMs) and a learning algorithm for C-PCIMs, which yield a novel data-driven approach to modeling fine grained event streams. C-PCIMs generalize PCIMs by allowing parameters to be shared across event types, and our learning algorithm uses the data to determine which parameters should be shared. In particular, we give a conjugate prior that allows parameter learning for the C-PCIM to be performed as efficiently as for the PCIM, and that leads to a closed-form marginal likelihood, allowing efficient structure learning. During structure learning, the C-PCIM learns what event types in what historical contexts can be modeled by shared parameters, thereby allowing more efficient use of data during parameter estimation. In cases where events are structured, with the different event types having known attributes, we show how structure learning can take advantage of these attributes to distinguish between different event types when their dependencies differ, while sharing parameters when they do not. Finally, we give empirical evidence that demonstrates the value of C-PCIMs in two real applications which are not well addressed by existing approaches– modeling the temporal query dynamics of web search users and modeling the temporal dynamics of system events in a data center. In the second application, we demonstrate that the expressive power of C-PCIMs combined with the data driven learning approach allows us to relax the strong assumption of identical machines, yielding further accuracy improvements. 2
Event streams can be modeled in either discrete or
continuous time. Using discrete time approaches such
as Hidden Markov Models (HMMs) [
We represent an event sequence as y = {(ti, li)}in=1 with 0 < t1 < · · · < tn, where ti ∈ [0, ∞) is the time of the ith event and li is its label, drawn from a finite label set L. The history at time t of event sequence y is the sub-sequence h(t, y) = {(ti, li) | (ti, li) ∈ y, ti ≤ t}. We write hi for h(ti−1, y) when it is clear from context which y is meant. By convention t0 = 0. We define the ending time t(y) of an event sequence y as the time of the last event in y: t(y) = max ({t : (t, l) ∈ y}) so that t(hi) = ti−1.
The data x, which is a particular event sequence, is
modeled as a realization of a regular marked point
process [
n
Y Y λl(ti|hi, θ)1l(li)e−Λl(ti|hi;θ)
l∈L i=1
(1)
where λl(t|h; θ) is the conditional intensity function [
In this section, we review PCIMs [
Note that the state s summarizes all the information
about t and y necessary for computing λl(t|y) in that
given s, λl(t|y) can be computed without further
information about t and y. However, unlike in Markov
models such as CTBNs [
As described above, the conditional intensity function λl(t|y) can be specified by a structure Sl = (Σl, σl(·, ·)) consisting of the state set Σl and the state function σl(·, ·) and a parameter parameter vector θl composed of a non-negative intensity λls for each s ∈ Σl. In turn, a PCIM is specified by a structure S and a parameter Θ that consist of the per-label structures Sl and perlabel parameter vectors θl.
Gunawardana et al. show [
The structure of a PCIM can be represented by a set
of decision trees [
Conjoint PCIMs (C-PCIMs), like PCIMs, are marked point processes where the conditional intensity function λl(t|y) are piecewise constant and take on a finite number of values, but unlike in PCIMs, the conditional intensity functions in C-PCIMs take on values from a single set of values shared across all labels l ∈ L. Thus λl(t|y) takes on values {λs} for s ∈ Σ which are shared across all l. Which of these values is taken on by λl(t|y) is specified by a C-PCIM state function σ(l, t, y) which unlike PCIM state functions, is also a function of the label l whose conditional intensity function is being evaluated. Thus, λl(t|y) = λσ(l,t,y). C-PCIMs thereA in [t-1,t) no
yes λA=0.1
A in [t-2,t-1) no
yes λA=10.0
λA=0.0 B in [t-1,t) no
yes fore allow an intensity value λs to be shared across conditional intensity functions for different labels, possibly at different times and for different histories. Thus, a C-PCIM is defined by a structure S = (Σ, σ(·, ·, ·)) consisting of a state set Σ and a state function σ(·, ·, ·) as well as a parameter vector Θ = {λs}s∈Σ, all of which are shared across labels l ∈ L.
We use a decision tree representation of the structure
S of a C-PCIM. However, instead of using a different
decision tree for each label l as in Gunawardana et
al. [
l in [t-2,t-1) no
yes λl=0.1 λl=10.0 λl=0.0 l = A no
yes
yes λl=0.0
λl=0.1
In this section, we directly generalize the parameter
and structure learning approaches for PCIMs [
Y λcs(x)e−λsds(x)
s s∈Σ (2) where ds(x) and cs(x) are sufficient statistics of the data. ds(x) is the total duration spent in state s, i.e., that σ(l, t, h(t, x)) = s for some l. cs(x) is the number of times a label l occurs in x when the state function maps to state s for label l. Formally, ds(x) = cs(x) =
X Z t(x) l∈L 0 X 1l (li) 1s (σ(l, ti, hi)) .
i
1s (σ (l, τ, h (τ, x))) dτ Note that since σ(l, τ, h) in the integral above is piecewise constant in τ , the integral reduces to a sum over the constant pieces of σ(l, τ, h).
A product of Gamma priors on λs is conjugate for Θ. The corresponding prior and the posterior densities for λs are given by
βα p(λs|α, β) = Γ(α) λsα−1e−βλs p(λs|α, β, x) = p (λs|α + cs(x), β + ds(x)) . leaves given by the tree is also a valid piecewise constant state function σ(l, t, y).
In our experiments, we obtain the point estimate Θˆ = E[Θ|S, x] from the training data, given by λˆs = α + cs(x) β + ds(x) . 4.1
For structure learning, we can write the marginal likelihood of the data x given the structure S in closed form as p(x|S) = Y s∈Σ | βα Γ(α + cs(x)) Γ(α) (β + ds(x))α+cs(x)
} γs{(zx) .
As with PCIMs, we use a Bayesian decision tree
building procedure [
[ s0∈Σf {s
s0} ∪ Σl\s σ0(l, t, y) = (s f (l, t, y) if σ(l, t, y) = s
σ(l, t, y) otherwise where is the concatenation operator. Thus, S0 can be represented as a tree where leaf s of the sub-tree S has been split according to the result of f .
In order to select the state s and basis state function f to use in producing a refined structure S0 from S, we define a factored prior
p(S) ∝ κ|Σ| on the structure S. The posterior probability of a structure S given the data x is then proportional to p(S)p(x|S) = Qs∈Σ κγs(x), which can be computed in closed form. Thus, the gain in p(S|x) due to splitting state s using basis state function f is
Gain(S → S0) = p(S0|x) p(S|x) = QQs0s∈∈ΣΣ0 κκγγss(0 x(x)) =
Qs0∈Σf κγs s0 (x) κγs(x) .
We refine the structure greedily, choosing the refinement with the highest gain, until no further gain results.
using this trivial identity attribute.
The modeling power of a family of C-PCIM is determined by the basis B of state functions selected. The basis needs to capture the aspects of the history that determine the intensities of events, and need to distinguish labels with different intensities. In addition, the basis needs to allow the sharing of parameters between labels to allow for generalization of event behavior between labels. This is particularly important in problems where some labels occur rarely. We will give basis state functions that take advantage of known structure in the label sets in order to do this. We first describe how we capture label space structure through label attributes, and then give an ontology of basis state functions that make use of this structure. 5.1
When the labels have a known structure, we will take
advantage of it in order to define models that can learn
dependencies between events with labels that may be
rare, or even not occur in the training data. For
example, in data center system event logs, events may
be labeled with the machine on which the event took
place and the type of the event. An event of type
disk-sector-error may occur on machine 9,045.
While we may have never observed a disk sector error
on a different machine 6,732, we may wish to allow
the structure learning procedure to determine whether
the behavior of disk-sector-error events generalizes
across machines. Thus, we would like the basis state
functions to be able to query for the message
represented by a label independently of the machine.
In general, we assume that the label set L has a
set of attributes A, where each attribute a ∈ A
can take values in a set Va. Label l takes on
value va(l) of attribute a. In the example above,
A = {machine-id, event-type}, and Vmachine-id
ranges over all the machines in the data center, and
Vevent-type ranges over all possible events. If prior
information about the labels is available, it may be
encoded through label attributes. For example, if we
know a priori that machines in the data center are
grouped into database servers and web servers, we
could introduce an attribute server-type that takes
on values Vserver-type{database, web}. On the other
hand, we can access label identity as an attribute
by using the attribute identity with Videntity = L,
videntity(l) = l. In the descriptions below, we will
therefore always assume that there are label attributes
defined. In cases where no structural information is
available we will simply use A = {identity}. In
particular, the basis state functions for PCIMs [
Allowing large classes of basis state functions that depend arbitrarily on both the history and time as well as the label is difficult computationally. We therefore restrict attention to three specific classes of basis state functions in this paper.
History Basis State Functions: A history basis state function f (l, t, y) depends only on the history y and the time t and not the label l. In this paper, we concentrate on a particular class of history basis state functions fa,v,d1,d2 (l, t, y) indexed by an attribute a ∈ A, a value v ∈ Va and time offsets d2 > d1 ≥ 0, and given by fa,v,d1,d2 (l, t, y) = 1 0 otherwise.
if ∃(t0, l0) ∈ y : t0 ∈ [t − d2, t − d1) ∧ va(l0) = v That is fa,v,d1,d2 (l, t, y) tests if the history y contains an event in the time window between d1 and d2 before t, whose label has the value v of attribute a. Example. In modeling web search query logs, the history basis state function fquery-category,Health,1 hr,1 day(l, t, y) tests whether y contains a query whose query-category attribute is Health between 1 hour and 1 day before t. Label Basis State Functions: A label basis state function f (l, t, y) depends only on the label l and not the time t nor the history y. A label basis state function is fa,v(l, t, y) is indexed by an attribute a ∈ A, a value v ∈ Va and is given by fa,v(l, t, y) = (1 if va(l) = v 0 otherwise.
That is fa,v(l, t, y) simply tests whether the attribute a of label l has value v.
Example. The label basis fquery-category,Health(l, t, y) tests query-category attribute Health.
state whether function l has
function fa,d1,d2 (l, t, y) is given by A match basis fa,d1,d2 (l, t, y) = 1 0 otherwise.
if ∃(t0, l0) ∈ y : t0 ∈ [t − d2, t − d1) ∧ va(l0) = va(l) In other words, the match basis state function tests whether the history y contains an event in the time window between d1 and d2 before t, whose label matches l in attribute a. This kind of basis state function is useful in modeling repetitions of a given attribute in an event stream.
Example. The basis state function
fquery-category,1 hr,1 day(l, t, y) tests whether y
contains a query with the same query-category
attribute as l between 1 hour and 1 day before t.
We note that history basis state functions are
equivalent to the history basis functions of PCIMs [
In this section we evaluate the value of C-PCIMs on
two real world tasks with large structured label spaces.
The first is to model the query behavior of web search
users, and the second is to model the behavior of a
cluster of machines in a commercial data center.
In order to evaluate the value of C-PCIMs in
modeling event streams with large label spaces, we
compare C-PCIMs to PCIMs. To explore the gains due
to conjoint modeling as opposed to the use of richer
label attributes in modeling, we also compare to
APCIMs. It has been shown that PCIMs have better
computational and predictive performance in
comparison to Poisson networks [
Queries issued by the users of a major commercial search engine were used to generate a training set consisting of approximately 100,000 queries collected -4 5) -5 0 (x1 -6 d o iho -7 l e ikL -8 g oL -9 -10 1%
10% Training Set Size
from approximately 6,000 users over a two month period and a test set consisting of approximately 170,000 queries from approximately 6,000 users over the next month. There was no user or time overlap between the training and test sets. The test set was restricted to contain only users whose query history was available for at least two weeks. The queries were automatically mapped to a two level hierarchy of categories such as Health & Wellness/Mental Health. Thus, our label set consisted of the 476 categories in the hierarchy, while the 37 coarse level categories were used as a second (i.e. non-identity) attribute, which we name coarse. All labels occurred in the training set. We use a product of terms of the form of equation (1), one per user, to model the data, choosing not to model inter-user dependencies. We investigated three model classes for modeling users’ query behavior. First, we built PCIMs which used only history basis state functions using the identity attribute (i.e. the history basis functions only tested for the occurrence of specific labels in the history). Second, we built A-PCIMs that were also allowed to use the coarse attributes in the history basis functions. Third, we built C-PCIMs that also used label basis state functions that used the identity and coarse attributes and match state functions that used the identity attribute. Match state functions using the coarse attribute were not allowed due to reduce the computation time. All models used a prior with α = 1/365 and β = 1 day, and κ = 0.001. The history and match basis state functions used the time windows [t − 1 hr, t), [t − 1 day, t − 1 hr), [t − 7 days, t − 1 day), and (∞, t − 7 days). All models took less than 12 hours to train on a single 3 GHz workstation.
Figure 3 shows the test set log likelihood of all three models as the amount of training data is varied. The log likelihoods of the PCIM and A-PCIM are nearly indistinguishable, while the C-PCIM performs much better, especially with smaller amounts of training data. This is the expected behavior, since C-PCIMs are better able to share parameters. Note that since C-PCIMs, A-PCIMs, and PCIMs define the same family of marked point processes, we expect them to approach the same predictive performance as the training set grows. While the gap between C-PCIMs and APCIMs/PCIMs does shrink as the amount of training data grows, C-PCIMs have higher training set likelihood even when all the training data is used. We examined the likelihoods assigned to each test event by the C-PCIM and the A-PCIM trained with the full training set, in order to determine the statistical significance of this gap. We grouped the per-event likelihoods by label, and found that the C-PCIM significantly outperforms the A-PCIM (p = 0.01) on 391 out of the 436 labels observed in the test set, while under-performing the A-PCIM on none, according to a paired sign test.
To understand the practical impact of the
likelihood gains, we used importance sampling [
System logs from a cluster of machines in a commercial data center were used to generate a data set of about 300,000 logged system events from 71 machines, over the period of a month. There were 221 possible messages. This gave 15,691 possible labels, each of which was a machine-message combination. Each machine belonged to one of four machine types that was known a priori. Thus, each label had four attributes {machine, message, machine-type, identity}. The first two weeks of data was used for training, and the rest for testing.
We use a product of terms of the form of equation (1), one per machine, to model the data, choosing to not allow inter-machine dependencies. We experimented with using the power of C-PCIMs to allow machine specific dependencies. In particular, we compare a PCIM and a C-PCIM that treat machines identically with a PCIM and a C-PCIM that allow machine specific dependencies. Non-identical modeling of machines may be useful if, for example, a certain machine is old is more prone to failures. Models that treat machines identically are allowed to use only the message attributes of labels. The PCIM that treats machines identically is forced to use the same conditional intensity function for all labels that agree on their message attributes, pooling data from these labels during training. Note that in this setting, PCIMs and A-PCIMs are equivalent in both the identical machine and nonidentical machine cases.
All models used the prior α = 0.01, β = 1.0 day, and κ = 0.01. The C-PCIM trees were truncated at a depth of 30 to save computation. The history and match basis state functions used the time windows [t− 20 min, t) and [t − 1 hr, t − 20 min). The models took less than 2 hours to train, except the non-identical machine PCIM, which learned a separate tree for each of the 5,307 labels present in the training data. This took less than 12 hours.
Figure 5 shows the log likelihood of events after the first two weeks given the events of the first two weeks for all four models. Note the log likelihoods can be positive since the likelihoods are density values and not probabilities. It can be seen that building separate PCIMs for each label, without pooling data across machines for each message results in a large loss in test set likelihood, due to data sparsity. Both C-PCIMs outperform the PCIMs. Note that the identical machine C-PCIM only has access to message information, and therefore does not have access to any label struc
(ident)
PCIM (non-ident)
C-PCIM (ident)
C-PCIM (non-ident) ture. However, it gives a large gain over PCIMs due to the use of match basis state functions, which model repeated events. The ability of the non-identical machine C-PCIM to leverage label structure to learn dependencies specific to machines or machine types leads to a further gain in likelihood. Unfortunately, events of interest such as machine failures are very rare in this data set, so that there are not enough test cases to obtain statistically significant comparisons between C-PCIMs and PCIMs. 7
We have introduced Conjoint PCIMs, and shown how they improve upon PCIMs in modeling the dynamics of two real world event streams with large structured label sets. We have shown how conjoint modeling across labels allows better models to be built from sparse data, and how C-PCIMs can leverage known structure in the label space. We have also shown that the predictive gains of C-PCIMs are not achieved by Attribute PCIMs that leverage label structure but do not use conjoint modeling.
While it would be of interest to compare the performance of C-PCIMs with other approaches such as CTBNs, limitations in the currently available CTBN implementation prevented us from doing so. It would also be interesting to investigate approaches that extend CTBNs to allow them to take advantage of label structure in the manner of C-PCIMs. Another future direction of interest is to investigate other extensions of PCIMs that allow parameter sharing across labels, such as hierarchical Bayesian approaches or regularization approaches.