Edge Selection for the Effective use of Piecewise-Constant Distributions as Neural Network Outputs for Event Prediction

Kevin Doran; Tom Baden

Dataset	rnn-logmix	rnn-pc
Yelp airport	4.715 $\pm$ 2.16e-02	4.685 $\pm$ 3.74e-02
Yelp Mississauga	3.916 $\pm$ 1.93e-02	3.260 $\pm$ 3.89e-02
Twitter	4.043 $\pm$ 4.44e-02	3.017 $\pm$ 7.35e-02
Wikipedia	4.364 $\pm$ 6.35e-02	1.962 $\pm$ 1.18e-01
Yelp Toronto	4.810 $\pm$ 6.27e-02	4.598 $\pm$ 6.98e-02
MOOC	1.023 $\pm$ 1.38e-01	-6.227 $\pm$ 2.90e-02

Appendix

Table 3: Confidence intervals for Table 2 ’s NLL results (from Section 6 ). The rnn-logmix and rnn-pc models evaluated in terms of test set NLL (lower is better) on 14 real-world datasets. 10 training repeats were carried out. Datasets were randomly split on each repeat. Point estimates are the mean over the trials. Variability is expressed as

95\%

confidence intervals calculated assuming a normal distribution of the mean:

\pm 1.96\frac{s}{\sqrt{10}}

, where

s

is the sample standard deviation.

Dataset	rnn-logmix	rnn-pc
Yelp airport	34.68 $\pm$ 7.42e-01	35.04 $\pm$ 7.75e-01
Yelp Mississauga	21.36 $\pm$ 4.65e-01	21.30 $\pm$ 5.27e-01
Twitter	37.23 $\pm$ 6.05e-01	37.34 $\pm$ 6.28e-01
Wikipedia	198.2 $\pm$ 7.39e+00	198.4 $\pm$ 7.44e+00
Yelp Toronto	62.82 $\pm$ 2.18e+00	62.75 $\pm$ 2.19e+00
MOOC	290.5 $\pm$ 4.07e+00	290.4 $\pm$ 4.08e+00

Appendix

Table 4: Confidence intervals for Table 2 ’s MAE results (from Section 6 ). The rnn-logmix and rnn-pc models evaluated in terms of test set MAE (lower is better) on 14 real-world datasets. 10 training repeats were carried out. Datasets were randomly split on each repeat. Point estimates are the mean over the trials. Variability is expressed as

95\%

confidence intervals calculated assuming a normal distribution of the mean:

\pm 1.96\frac{s}{\sqrt{10}}

, where

s

is the sample standard deviation.

	NLL rank $\downarrow$		MAE rank $\downarrow$
Model	#	mean	#	mean
rnn-logmix	5	5.36	2	5.29
gpt-a-logmix	4	4.86	7	6.71
gpt-b-logmix	6	5.71	5	6.29
rnn-pc	2	2.14	1	5.14
gpt-a-pc	1	1.50	6	6.64

Appendix

Table 7: Mean rank of models across all 14 datasets, in terms of NLL and MAE. The scores are taken from Table 5 and Table 6 . Bold entries are the lowest (best) mean rank for each metric (i.e. per column).

	NLL rank $\downarrow$			MAE rank $\downarrow$
Head	rnn	gpt-a	gpt-b	rnn	gpt-a	gpt-b
logmix	2.21	1.50	2.29	1.71	2.07	2.21
pc	2.07	1.50	2.43	1.71	2.07	2.21
nn	1.93	1.79	2.29	1.79	2.00	2.21
softplus	1.79	1.79	2.43	1.93	1.86	2.21
exp	1.64	2.21	2.14	1.79	2.14	2.07

Appendix

Table 8: Mean rank of three model stems— rnn , gpt-a and gpt-b —in terms of NLL and MAE across the 14 real-world datasets. In addition to this rank (which appears in the final row), the mean rank is also calculated (for the same datasets) by first aggregating by output head. Each row has an NLL and a MAE ranking. The scores are taken from Table 5 and Table 6 . Bold entries are the lowest (best) mean rank across the three model stems (i.e. per row, but separate for the two metrics).

	NLL $\downarrow$				MAE $\downarrow$
Dataset	rnn-logmix	rnn-pc	rnn-qpc	rnn-wpc	rnn-logmix	rnn-pc	rnn-qpc	rnn-wpc
Yelp airport	4.715	4.685	4.779	4.772	34.68	35.04	35.11	35.10
Yelp Miss.	3.916	3.260	3.949	3.968	21.36	21.30	21.64	21.52
Twitter	4.043	3.017	4.089	4.173	37.23	37.34	37.54	37.50
Wiki.	4.364	1.962	4.385	5.417	198.2	198.4	198.5	211.6
Yelp Toronto	4.810	4.598	4.808	5.005	62.82	62.75	62.75	62.79

Appendix

Table 9: With rnn-logmix as a reference, the three edge selection methods are compared: rnn-wpc (equal-width), rnn-qpc (equal-quantile) and rnn-pc (maximum likelihood). All models share the same architecture up until the output representation. They are evaluated on 14 datasets in terms of test-set NLL and MAE. Values are means over 10 training repeats, where each repeat uses a random data split. Cells are coloured when the score difference to the rnn-logmix model,

\Delta

, is statistically significant with respect to the standard errors (SE) of the means,

|\Delta|>1.96\sqrt{\mathrm{SE}_{\text{rnn-logmix}}^{2}+\mathrm{SE}_{\text{model}}^{2}}

; green when a model is better than rnn-logmix , red when worse.

Figure 8: NLL scores for rnn-pc and rnn-logmix on 14 datasets with jittered event times. Event times are jittered by adding Gaussian noise with standard deviation proportional to the median inter-event time,

\tilde{\tau}

. That is,

t_{i}^{*}=t_{i}+\eta

where

\eta\sim\mathcal{N}(0,(\tilde{\tau}q)^{2})

. Five values of

q

are used, from

1\times 10^{-5}

to

1\times 10^{-1}

. Values are means over 10 repeats, where each repeat involves a new random data split and noise seed. Both models’ scores improve under lower noise, but more so for rnn-pc .

	NLL $\downarrow$			MAE $\downarrow$
Dataset	rnn-pc	rnn-qpch	rnn-pch	rnn-pc	rnn-qpch	rnn-pch
Yelp airport	4.685	4.781	4.682	35.04	35.22	35.16
Yelp Mississauga	3.260	3.947	3.234	21.30	21.78	21.61
Twitter	3.017	4.089	2.998	37.34	37.55	37.37
Wikipedia	1.962	4.376	1.927	198.4	198.7	198.4
Yelp Toronto	4.598	4.805	4.646	62.75	62.76	62.77

Appendix

Table 12: Density versus hazard. A piecewise-constant hazard output paired with the rnn model is compared to the rnn-pc model. Two piecewise-constant hazard outputs are considered: rnn-qpch and rnn-pch . They differ in the edge choice method— rnn-qpch uses the equal-quantile method and rnn-pch uses the maximum likelihood method. The models are evaluated on the 14 real-world datasets in terms of test-set NLL and MAE. All models share the same architecture up until the output representation. Values are means over 10 training repeats, where each repeat uses a random data split. Cells are coloured when the score difference to the rnn-pc model,

\Delta

, is statistically significant with respect to the standard errors (SE) of the means,

|\Delta|>1.96\sqrt{\mathrm{SE}_{\text{rnn-pc}}^{2}+\mathrm{SE}_{\text{rnn-}x}^{2}}

; green when a model is better than rnn-pc , red when worse.

model	NLL $\downarrow$	MAE $\downarrow$
rnn-logmix	-0.036 $\pm$ 2.32e-03	0.954 $\pm$ 1.56e-03
gpt-a-logmix	-0.036 $\pm$ 3.75e-03	0.954 $\pm$ 2.44e-03
gpt-b-logmix	-0.035 $\pm$ 3.60e-03	0.954 $\pm$ 2.42e-03
rnn-pc	-0.029 $\pm$ 3.74e-03	0.955 $\pm$ 2.43e-03
gpt-a-pc	-0.034 $\pm$ 3.75e-03	0.954 $\pm$ 2.45e-03
gpt-b-pc	-0.031 $\pm$ 3.70e-03	0.954 $\pm$ 2.47e-03

Appendix

Table 13: Hawkes process dataset results. NLL and MAE results for all models. 10 training repeats were carried out, where variability is in the random dataset split, random model initialization and training stochasticity. Point estimates are means over the repeats, and variability is expressed as

95\%

confidence intervals calculated assuming a normal distribution of the mean:

\pm 1.96\frac{s}{\sqrt{10}}

, where

s

is the sample standard deviation. The Hawkes process is defined by a conditional hazard function:

\lambda(t|H_{t})=\mu+\sum_{t_{i}<t}\sum_{j=1}^{M}\alpha_{j}\beta_{j}\exp{-\beta_j(t-t_i)}

, with the parameters set as in Omi et al. (2019) to

M=2,\mu=0.2,\alpha_{1}=0.4,\beta_{1}=1,\alpha_{2}=0.4,

and

\beta_{2}=20

. Bold highlights the lowest (best) point estimate.

Dataset	Event type	Unit	Source
Yelp airport	Time between check-ins at McCarran International Airport.	minutes	( Lüdke et al., 2023 )
Yelp Mississauga	Time between check-ins at businesses in Mississauga.	minutes	( Lüdke et al., 2023 )
Twitter	Time between tweets of a single user.	minutes	( Lüdke et al., 2023 )
Wikipedia	Time between edits of the site’s top edited pages.	minutes	( Shchur et al., 2020 )
Yelp Toronto	Time between check-ins at restaurants in Toronto.	hours	( Shchur et al., 2020 )
MOOC	Time between user interactions on an online course system.	minutes	( Shchur et al., 2020 ; Kumar et al., 2019 )

Appendix

Table 14: Sources of the event sequences. The unit column reports the units used in this work, which may differ from the units used in the original source (see Section C.4 ).

Dataset	Gini coefficient
Amazon	0.000
Stack Overflow	0.141
Yelp airport	0.148
Yelp Toronto	0.192
Yelp Mississauga	0.361
Twitter	0.438

Appendix

Table 15: Gini coefficients for the distribution of inter-event times of the real-world datasets.

Figure 9: Histograms for 7 real-world datasets. Histograms extend until the 0.95 quantile ( left ) and 0.6 quantile ( right ). All histograms have 128 bins. The

y

-axis shows normalized counts.

Figure 10: Histograms for 7 real-world datasets. Histograms extend until the 0.95 quantile ( left ) and 0.6 quantile ( right ). All histograms have 128 bins. The

y

-axis shows normalized counts.

Figure 11: Distribution of pairs of inter-event times,

\tau_{i}

and

\tau_{i+1}

for 6 real-world datasets. The first 4 datasets ( MOOC – Reddit Politics ) appear to have a grid structure on account of the resolution at which the data was recorded. The last 2 datasets ( NYC Taxi and Last.fm ) have a grid structure embedded within a smoother distribution. Each figure has a quantile threshold chosen so that the structure is visible. Each figure is a rasterization of event counts into a

256\times 256

pixel grid.

Figure 13: The instability of a logmix output head when a dataset has a probability mass at a certain point. (a): shows the distribution of inter-event times. The dataset is formed from a mixture where 10% of values come from a point source at

t=\exp(2)

, and the remaining values are drawn from a lognormal distribution with parameters

\mu=0

and

\sigma=1.0

. All events are independent. The model used is a gpt-a stem with a 2-component lognormal mixture output. The model is trained using stochastic gradient descent with momentum (0.9) and a learning rate of

5\times 10^{-4}

. (b): shows the mixture parameters (the model output) and the NLL (calculated on an evaluation set) over the course of training. The six model parameters are the mixing parameters (

\tau_{0},\tau_{1}

) and the means and variances (

\mu_{0},\mu_{1},\sigma_{0},\sigma_{1}

) of the two underlying Gaussian distributions. Notably, neither

\mu_{0}

nor

\mu_{1}

approach 2.0 in a stable manner. Training stopped when evaluating the distribution median produced NaN values. This instability occurs reliably across runs.

Figure 14: An nn head where the first embedding vector

\mathbf{u}

is 2-dimensional. The matrix projecting

\tau

into u -space,

W_{\tau}\in\mathbb{R}^{2\times 1}

, is the unit vector

[0.86,0.51]^{T}

. The second and third layers have 5 and 3 units respectively (

W_{1}\in\mathbb{R}^{5\times 2},W_{2}\in\mathbb{R}^{5\times 3},W_{\text{out}}\in\mathbb{R}^{3\times 1}

). (b) shows the altitude change along the

\tau

-paths from (a) ; this is the cumulative intensity

\Lambda

. The derivative,

\lambda

, is a solid curve. The corresponding probability densities are shown in (c) . All possible probability densities for this head correspond to a different starting position in the

u

-space.

Figure 15: Empirical and predicted cumulative distribution function (CDF) for the PUBG dataset. The green curve is the empirical CDF of the training set’s inter-event times. The other curves are mean CDFs calculated from rnn-nn , rnn-logmix and rnn-pc outputs, meaned over 4096 input histories drawn from the training set.

Figure 16: Probability distributions emitted by rnn-nn , rnn-pc and rnn-logmix models trained on a synthetic sequence where inter-event times are drawn from a stationary mixture (lognormal and five narrow Gaussian peaks). The true distribution of the inter-event times is shown in green . The rnn-nn ’s distribution contains five peaks at the correct locations. A black dashed line is the mean of five training runs. The individual runs are shown as semi-transparent gray curves; however, all are close to the mean and difficult to distinguish.

Figure 17: Two different outputs for three models trained on a synthetic sequence where the distribution of the next inter-event time switches between having and not having a narrow peak. The distribution of

\tau_{i+1}

depends only on

\tau_{i}

: if

\tau_{i}\geq 1

, then

p(\tau_{i+1}|\tau_{i})\sim\operatorname{lognormal}(0,1)

, else

p(\tau_{i+1}|\tau_{i})

is a mixture of the same lognormal distribution and a narrow Gaussian (

\sigma=0.02

) centered at

\tau_{i+1}=2

. The mixture is

0.7\cdot\operatorname{LogNormal}(0,1)+0.3\cdot\mathcal{N}(2,0.02^{2})

. Both rnn-pc and rnn-logmix can (somewhat) use the history input to modulate the probability density at the peak location. We do not observe the rnn-nn model carrying out this modulation. This experiment was repeated five times with different random seeds, and the same pattern was observed each time (the figures above show just one run).

Figure 18: Three models trained on a synthetic sequence in which the distribution of the next inter-event time has a narrow peak whose center is equal to the previous inter-event duration. The distribution of

\tau_{i+1}

is a mixture of a background lognormal and a Gaussian (

\sigma=0.03\tau_{i}

) centered at

\tau_{i}

. Specifically,

p(\tau_{i+1}\mid\tau_{i})=0.6\cdot\operatorname{LogNormal}(0,1)+0.4\cdot\mathcal{N}\bigl(\tau_{i},\,(0.03\,\tau_{i})^{2}\bigr)

. All three models can use the history input to translate the location of a peak.

Figure 19: NLL evaluated every 5k steps throughout 200k-step training runs for the three models ( rnn-nn , rnn-pc and rnn-logmix ) on the three synthetic datasets (fixed peaks, binary peaks, and moving peaks). The NLL is calculated on

2^{16}

samples from a held-out set. There are 5 individual runs displayed as semi-transparent curves, and the mean across them is opaque.

Figure 20: Decomposition of

\phi(h)\in\mathbb{R}^{64}

(from Equation 6 ) along the unit direction

\hat{W}_{\tau}=W_{\tau}/\|W_{\tau}\|

, and the (63-dimensional) orthogonal complement,

W_{\tau}^{\perp}

. This is done for two datasets, the present/absent peaks dataset ( left ) and the translated peaks dataset ( right ). The component of

\phi(h)

parallel to

\hat{W}_{\tau}

is

\langle\hat{W}_{\tau},\,\phi(h)\rangle

( top ) and the norm of the 63-d orthogonal component is

\|\phi(h)-\langle\hat{W}_{\tau},\,\phi(h)\rangle\hat{W}_{\tau}\|

, which we denote as

\|\phi_{\perp}(h)\|

( bottom ). For each dataset we draw

2^{17}

histories from a held-out set and evaluate

\phi(h)

, making note of

\tau_{i-1}

. This is done for 5 runs (grey), and the mean across runs is plotted in black. All runs have their individual mean subtracted to bring the curves into the same range. The per-run mean operates on values binned by the x-axis,

\tau_{i-1}

into 64 bins from the 5th until the 95th quantile of

\tau_{i-1}

. The parallel component is strongly correlated with

\tau_{i-1}

for the translated peaks dataset, and not for the present/absent peaks dataset.

Figure 21: Probability distributions emitted by gpt-a-nn , gpt-a-pc and gpt-a-logmix models trained on a synthetic sequence where inter-event times are drawn from a stationary mixture (lognormal and five narrow Gaussian peaks). The true distribution of the inter-event times is shown in green . The gpt-a-nn ’s distribution contains five peaks at the correct locations. A black dashed line is the mean of five training runs. The individual runs are shown as semi-transparent gray curves; however, all are close to the mean and difficult to distinguish.

Figure 22: Three models trained on a synthetic sequence in which the distribution of the next inter-event time has a narrow peak whose center is equal to the previous inter-event duration. The distribution of

\tau_{i+1}

is a mixture of a background lognormal and a Gaussian (

\sigma=0.03\tau_{i}

) centered at

\tau_{i}

. Specifically,

p(\tau_{i+1}\mid\tau_{i})=0.6\cdot\operatorname{LogNormal}(0,1)+0.4\cdot\mathcal{N}\bigl(\tau_{i},\,(0.03\,\tau_{i})^{2}\bigr)

. All three models can use the history input to translate the location of a peak.

Figure 23: NLL evaluated every 5k steps throughout 200k-step training runs for the three models ( gpt-a-nn , gpt-a-pc and gpt-a-logmix ) on the three synthetic datasets (fixed peaks, binary peaks, and moving peaks). The NLL is calculated on

2^{16}

samples from a held-out set. There are 5 individual runs displayed as semi-transparent curves, and the mean across them is opaque.

Figure 24: Decomposition of

\phi(h)\in\mathbb{R}^{64}

(from Equation 6 ) along the unit direction

\hat{W}_{\tau}=W_{\tau}/\|W_{\tau}\|

, and the (63-dimensional) orthogonal complement,

W_{\tau}^{\perp}

. This is done for two datasets, the present/absent peaks dataset ( left ) and the translated peaks dataset ( right ). The component of

\phi(h)

parallel to

\hat{W}_{\tau}

is

\langle\hat{W}_{\tau},\,\phi(h)\rangle

( top ) and the norm of the 63-d orthogonal component is

\|\phi(h)-\langle\hat{W}_{\tau},\,\phi(h)\rangle\hat{W}_{\tau}\|

, which we denote as

\|\phi_{\perp}(h)\|

( bottom ). For each dataset we draw

2^{17}

histories from a held-out set and evaluate

\phi(h)

, making note of

\tau_{i-1}

. This is done for 5 runs (grey), and the mean across runs is plotted in black. All runs have their individual mean subtracted to bring the curves into the same range. The per-run mean operates on values binned by the x-axis,

\tau_{i-1}

into 64 bins from the 5th until the 95th quantile of

\tau_{i-1}

. The parallel component is strongly correlated with

\tau_{i-1}

for the translated peaks dataset, and not for the present/absent peaks dataset.

Label	Stem description	Input	Layers	Heads	Embed dim.	Parameters
rnn	gated recurrent unit ( Cho et al., 2014 )	32	1	NA	64	13k
gpt-a	GPT-2 transformer ( Radford et al., 2019 )	128	2	4	16	108k
gpt-b	GPT-2 transformer	128	6	4	32	1.20M

Edge Selection for the Effective use of Piecewise-Constant Distributions as Neural Network Outputs for Event Prediction

Abstract

Figures & tables

Appendix

Explore similar work

Structured Neural Marked Point Processes for Interpretable Event Interaction Modeling

Convergence Rates for Neural-Network Estimation with Current-Status Data

Promoting Simple Agents: Ensemble Methods for Event-Log Prediction