2
$\begingroup$

I have a series of events. I think there are n periods that make up this series. (I do not know the bounds of the periods). I assume that the delay between the events of each of these periods follows exponential distribution (again I do not know the lambda parameters of those distributions) . Do you know if anyone has ever developed an algorithm to solve this problem, i.e. find those unknown parameters (number of periods, bounds of periods and lambdas) that would maximise the likelihood?

enter image description here

$\endgroup$
  • $\begingroup$ Do you mean that the delays follow an exponential distribution? (i.e. a Poisson point process) $\endgroup$ – GeoMatt22 Oct 19 at 18:10
  • $\begingroup$ @GeoMatt22 Yeah I'm sorry, exponential distribution, right $\endgroup$ – hans glick Oct 19 at 23:27
  • $\begingroup$ It looks like a generative model for events modelization $\endgroup$ – hans glick Oct 20 at 8:41
1
+50
$\begingroup$

If we simplify to assume that the segment boundaries coincide with events, then we can use dynamic programming to maximize the likelihood.

First consider the case of a single segment. The data consists of $n+1$ distinct events, occuring at times $t_0 < \ldots < t_n$. If we assume that the waiting times $\tau_i = t_{i+1} - t_{i}$ are independent and identically (exponentially) distributed with rate parameter $\lambda$, then the likelihood is $$ L = \lambda^n e^{-\lambda T} $$ where $$ T = \sum_{i=1}^{n-1}\tau_i = t_n - t_0 $$ is the length of the segment, equal to the sum of waiting times.

To simplify the optimization, rather than maximizing the likelihood, we can minimize the cost $$ c \equiv -\log{L} = \lambda T - n \log\left(\lambda\right) $$

Minimizing the single-segment cost gives $\hat{c} \equiv \min_{\lambda} c\left(\lambda\right) = c\left(\hat{\lambda}\right)$, where for $n>0$ we have $$\hat{\lambda} = \frac{n}{T}$$ and $$\hat{c} = n\left(1 - \log\left(\frac{n}{T}\right)\right)$$ and for $n=0$ we have $\hat{c} = \hat{\lambda} = 0$.


For the $K$-segment case, let $c_{i,j}$ be the cost to group events $t_i$ through $t_j$ into a single segment. (This corresponds to $n=j-i$ and $T=t_j-t_i$ in the above formulas.)

For $N+1$ events, the cost of a segmentation $$0 = i_0 < i_1 < \ldots < i_{K-1} < i_K = N$$ is the sum of segment costs $$\sum_{k=1}^K c_{i_{k-1}, i_k}$$

To minimize this sum-over-segments error, dynamic programming uses the following idea. Given an optimum segmentation of an event sequence into $k$ segments, removing the last segment (and its events) gives an optimal segmentation of the remaining prefix sequence into $k-1$ segments.

Let $C_{k,j}$ be the minimum cost to divide events $t_0$ to $t_j$ into $k$ segments. Then the prefix-segmentation argument above means that $$ C_{k,j} = \min_{i}\left( C_{k-1,i} + c_{i,j} \right) $$ where $i$ is the last event in the prefix sequence (which is also the first event in the $k$-th segment).

This recursion allows the optimum solution, $C_{K, N+1}$, to be computed by filling in the $C_{k,i}$ table.

The details are given in the "Dynamic programming segmentation" pseudo-code on page 4 of this paper. (Note that you can ignore their "segment error computation", which is based on a Gaussian linear model. For your case this will be the $c_{i,j}$ formula I gave above.)

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ thks for your answer I'm lookin at it $\endgroup$ – hans glick Oct 23 at 9:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.