There are two classes of strings of events. E.g. A: 0,0,1,2,2,3,4,0,3,0,0,0 B: 0,0,0,0,3,3,2,1,5,6,7,0

Both class A and B strings exhibit variability. Many (e.g. 10,000) A and B strings are collected. I collect the observations into a matrix x where columns are the value of each event (12 events in the example above) and the rows are individual strings of events. Then for each event[i] I can find: p(A|x[,i]>0) = sum(x[,i]>0 & A)/sum(x[,i]>0) where the x[,i] notation means column i (ie events i=1 to 12) sum(x[,i]>0 & A) counts the number of times A occurs when event i >0 sum(x[,i]>0) counts the number of times event i >0

If I do this for all events I can find a probability map which says how likely the string is from class A given the x value is greater than 0. e.g. pmap A: 0,0,.5,.6,.4.,.5,.9,.7,.6,.5,0,0 pmap B=1-A (since each string is either class A or class B)

Now suppose I am presented a new string of events. Does it belong to class A or B? I feel that I should be able to use my probability map to make this decision along with the new string. How likely is it that this string belongs to class A given the probability map? I am thinking: if this likelihood is bigger than some criterion, say A, else say B. Is this idea workable?

Please tell me how to proceed. Thanks very much for any help.


Assuming you came up with this, you have invented the first half of a Naive Bayes classifier. Congrats!

The traditional next step is to assume that events $X_i$ and $X_j$ are independent, so that $$\frac{P(A\mid X_i, X_j)}{P(B\mid X_i, X_j)} = \frac{P(X_i, X_j \mid A)}{P(X_i, X_j \mid B)} = \frac{P(X_i \mid A)}{P(X_i \mid B)} \cdot \frac{P(X_j \mid A)}{P(X_j \mid B)}.$$ (I'm using the more traditional math notation $X_i$ to denote your event x[,i] > 0.)

Once you have this, you know that $P(A)/P(B) = \prod_{i=1}^p P(A \mid X_i) / P(B \mid X_i)$ and, since $P(A) + P(B) = 1$, you can solve for $P(A)$.

There are a couple caveats with this approach:

  • If any entry $P(A \mid X_i)$ is zero then your algorithm will say that the instance must be of class $B$, regardless of the evidence of the other columns. If you have both $P(A \mid X_i) = 0$ and $P(B \mid X_j) = 0$ then your answer is undefined! A "hack" to get around this is to pretend you've seen one extra instance in all categories (in other words, use p(A|x[,i]>0) = (sum(x[,i]>0 & A) + 1)/(sum(x[,i]>0) + 2) in your pseudocode above).

  • A primary strength of Naive Bayes is that it has no parameters to learn, so it works well on small datasets. If you have enough sequences of events compared to their length (say, 10 times as many strings as the length of the string), you may get better results from a different kind of algorithm like logistic regression.

  • $\begingroup$ Thanks Ben! Yes I did come up with this idea on my own. My way of handling the problem you describe was just to ignore the events i where sum(x[,i]>0) == 0. Maybe that is not legit? $\endgroup$ – stan Mar 24 '15 at 8:01
  • $\begingroup$ As with many machine learning algorithms, the gold standard for an answer is to try it both ways and see which one works better! Since those events do carry some information, I imagine it might be sub-optimal to throw them away, but it depends on your data. $\endgroup$ – Ben Kuhn Mar 24 '15 at 19:00

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.