4
$\begingroup$

I am working on a programming problem of 2 dependent variables X and Y. X is made of feature vector of size [128 x 1] and Y is the observation.

My problem is that the 2 variables are dependent that is given X we should compute probability of Y i.e P(Y|X) or given Y we should compute P(X|Y).

I am uncertain as which model can capture this property of the 2 variables. Hidden Markov model I think will only capture one way. Is there any probability distribution method to capture the distribution in both ways.

$\endgroup$
  • $\begingroup$ From @dominic: Can you provide more information about the feature vectors X and Y, what their relationship is, what kind of data - ordinal, binary, categorical etc. $\endgroup$ – chl Jan 21 '14 at 14:20
  • 1
    $\begingroup$ Why is one vector longer than another? Are you asking for a "missing data" method (i.e., imputation) or are the two vectors supposed to be inputs for a probabilty model? $\endgroup$ – user31668 Jan 22 '14 at 0:53
  • $\begingroup$ Please check the question again, I made a mistake and now i corrected it. $\endgroup$ – user1965914 Jan 23 '14 at 1:39
  • $\begingroup$ Which text are you following? $\endgroup$ – Neil G Jul 3 '14 at 5:53
1
$\begingroup$

IMHO this appears to be a job for Naive Bayes. Naive Bayes Classification offers a way to determine the probability of a classification, given a set of observed feature data. Naive Bayes assumes that features of a training set are independent of each other. That is to say each feature contributes independently of other features to the probability of a given classification.

The probability model for a classifier is a conditional model. In other words the variable $C$ is dependent on features $F$. Therefore the probability of a classifier $C$ given a set of features, can be written as $P(C| F_{0..n-1})$. $C$ is a categorical variable $C = \{ c_{i} |\quad i \in \mathbb{Z^{+}} \}$.

In the real world many complex systems involve a relationship between numerous features and possible classes. In such cases basing a model on probability tables becomes intractable as the size of the feature vector grows. Instead, by using Bayes Theorem, we can reformulate $P(C| F_{0..n-1})$ in the following way:

$P(C| F_{0..n-1}) = \dfrac{P(C) \times P(F_{0..n-1}|C) }{P(F_{0..n-1})}$

This can be rewritten as:

$posterior = \dfrac{prior \times likelihood}{evidence}$

Breaking it down:

$P(C | F_{0..n})$ -- given a set of features, what is the probability of a particular classification?

$P(C)$ -- this is our prior, i.e. it is based on knowledge we have gathered beforehand.

$P(F_{0..n} | C)$ -- is the likelihood(probability) that a set of features belong to a set of classifications. Here the unfixed parameter is whether a set of features belongs to a given classification (class).

$P(F_{0..n})$ -- is the probability of the feature set itself, otherwise known as the 'evidence', and which is usually ignored.

Notice that for each class in $C$ the denominator is the same, which allows us to treat it as a constant across all posteriors, meaning we need only look at the numerator to derive meaning.

Your task it appears is to provide an algorithm (and its implementation) for calculating the posterior probabilities. $S = \{ P(c_{0} | F), P(c_{1} | F), ..., P(c_{n-1} | F) \}$

When we do this, we are of course looking for the biggest posterior probability. The classification that meets this will be the class that is most likely to occur.

While we do this, we will store each computed posterior in such a way as to be able to obtain or call the maximum in constant time (ideally) from a data structure. In other words we sort as we compute.

Here is some simple and by no means optimized pseudo code to help illustrate the ideas above:

for (i=0; i < n; i++){

   posterior[i] = prior(i) * likelihood(i) 
   if i > 0 
      if posterior[i] < posterior[i-1]{
        /* There are better ways to do this swap */
        alpha = posterior[i-1]*posterior[i]  
        posterior[i-1] = alpha/posterior[i-1]
        posterior[i] = alpha/posterior[i-1] 
      }
   }
}
$\endgroup$
0
$\begingroup$

Hidden markov models, like any generative model, encode both the generative distribution $P(Y\mid X)$ and the conditional feature distribution $P(X \mid Y)$.

These models typically have parameters for the generative distribution only. Inferring the likelihood over the features might work by, for example, calculating the probability of the observation $Y$ for each feature vector configuration $x$. Another inference technique when there are many configurations is Gibbs sampling.

$\endgroup$

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.