# How can I infer order from partially ordered discrete sequences?

A really interesting problem that I can't stop thinking about! Have run in to this a couple of times but yet to find a smart approach to either solve or frame this problem. This is my try at generalizing it:

Assume that we have an application where a user in each session can make one or many actions, each of those actions falls into the categories, say $\{a,b,c,d,e,f,g\}$.

In one of the sessions the user makes some kind of 'defining action' that leads to termination of the sequence, in most cases terminating it immediately but there are occasionaly actions even afterwards.

Aim: We want to classify users according to which their 'defining' action was

Variables

$\mathcal{O}$= the order of the actions (Unknown)

$S$= Session of the action

$\mathcal{D}$= binary, '1' indicating the 'defining action' (Unknown)

$W$= binary, '1' indicating that the 'defining' action was made in this session

$A$= Type of action

Data We have data for some large amount of $N$ users.

Example of data for a user that should be classified as type 'c', where $W=1$ marked in red:

\begin{array}{c|c|c|c} \hline \mathcal{O}& S& \mathcal{D}& W & A &\\ \hline 1&1& 0&0&a\\ \hline 2&2& 0&0&e\\ \hline \color{red}{3} &\color{red}{3} &\color{red}{0}&\color{red}{1}& \color{red}{b}\\ \hline \color{red}{4} &\color{red}{3} &\color{red}{1}&\color{red}{1}& \color{red}{c}\\ \hline 5&4& 0&0&a\\ \hline 6&5& 0&0&f\\ \hline \end{array}

Problem: We would only need $\mathcal{D}$ together with $A$ to conclude that this user is of category 'c' but $\mathcal{D}$ is not known explicitly. When there's only one action done in the session where the the determining action was taken $W$ is identically $\mathcal{D}$. This is the fact in most of the cases.

Here on the other hand we only know which session the decision was taken so for all we know the user can either be classified as a 'b'- or 'c'- user. Illustrated below

• In most cases only one action per session is made so $\mathcal{D}=W$ in each case and thus the defining action is known.
• There is some a set of unknown rules in what sequences of actions can lead to particular defining actions. For example; "b cannot be the determining action if action a followed by e has been taken'. Those rules are not followed consistently, there's some random variation. And in particular, they are unknown.
• We assume that the event that some sessions has multiple actions is randomly distributed.

How can I approach trying to infer which the defining decision is for each user based upon my observations?

Preferrably I'd get some model assigning membership scores/probabilites for each category given data.

Why is this interesting?

This is a terminating sequence of varying length wich we can only observe as a partially ordered set. Usually one can use domain knowledge/theory to infer this order. When there are no such knowledge one can sometimes use exploratory analysis to figure it out. That is not always possible due to complexity and is inherently biased and timeconsuming. I've run into this when working with large large relational databases where (by design or negligence) some attribute is missing that I need to accurately guess.

• You could use some regression or machine learning techniques to estimate the probability that user $i$ has defining action $a$ given action history (prior to last session) $H_i=(a_{i,t=1},a_{i,t=2},..)$ and a set of possible defining actions $X_i$ (all actions taken in last session, where order is not observable). That is, you estmate $P(a=x\in X_i|H_i)$. You can do this by using the data where only one action is taken in the last session (you know the defining action), and by assuming that behavior between those with identifiable defining action and with non-identifiable action is similar. – Nameless Dec 13 '14 at 17:35