2
$\begingroup$

I'm working on a problem where I need to find the probability of a given data sample belonging to a give class using the Bayes Theorem for classification.

From everything I've been able to find so far the way to do this would be to first calculate the conditional probabilities using multivariate Gaussians (shown below), then apply Bayes Theorem to get the desired posterior probability.

$$P(x|k)=\frac{1}{\sqrt{(2\pi)^{p/2}|\boldsymbol\Sigma|^{1/2}}} \exp\left(-\frac{1}{2}({x}-{\mu_k})^T{\boldsymbol\Sigma}^{-1}({x}-{\mu_k}) \right)$$

The problem I'm having is that the Mahalanobis distance in the exponent term is consistently coming to extremely large values, making the conditionally probabilities far too small to work with programmatically. I've determined this is almost entirely due to the covariance matrix, which is populated with values that are incredibly small. Furthermore, when I just ignore the covariance matrix and solve using the Euclidean distance instead, I arrive at reasonable probability estimates with distances that appear to more accurately reflect what I would expect in classification.

So I was wondering:

  1. If there was a way to calculate these conditional probabilities or the overall posterior probability without direct exposure to the exponent, so they become feasible to work with programmatically.
  2. If there is any statistical justification for using the Euclidean distances over the Mahalanobis distance in this case.

[Edit] Here are a few more details regarding the derivation of the covariance matrix and the dataset:

The dataset I'm working with has been transformed into a lower dimensional space using the discriminant analysis (ULDA) technique described in this paper. In this form of discriminant analysis there is a shared pooled within-class covariance matrix corresponding to each class conditional probability (this being calculated over the reduced dimensional space). Interestingly, with this technique, if the total scatter matrix is used as the shared covariance matrix then the covariance matrix in the reduced space will be the identity matrix. This technique optimizes with respect to the total scatter matrix rather than the within-class scatter matrix, so maybe I'm misunderstanding what the covariance matrix should be in this case. Also, as mentioned in the paper, the ULDA technique produces features in the reduced space are uncorrelated to each other. I suppose another possibility would be that this particular dimensionality reduction reduces the usefulness of the within-class scatter matrix to the point that it gives worse results than just using the plain identity matrix as the covariance.


Any help or advice would be greatly appreciated, thanks in advance.

$\endgroup$
4
$\begingroup$

Avoiding the numeric problem via logarithms

Usually the computations are done using logarithms to avoid underflow problems. Your posterior probability $P(k|x)$ is proportional to $P(k)p(x\mid k)$ - the denominator of Bayes theorem acts to normalize the sum of the probabilities to 1, but it is easy to see that it does not actually change the result if you multiply all $P(k)p(x\mid k)$s by a constant, equivalently, add a constant to their logarithms. So,

  1. Compute log-posterior: $\log P(k) + \log p(x \mid k)$ for all $k$.
  2. Add a suitable constant to all the log-posterior values (e.g., subtract the maximum so that the new maximum is 0) to bring them to reasonable scale.
  3. Exponentiate the $\log $s and normalize.

Statistical interpretation of Euclidean distance

I assume you mean that you put $(x-\mu_k)^T(x-\mu_k)$ to the exponent instead of $(x-\mu_k)^T\Sigma^{-1}(x-\mu_k)$. This is equivalent to setting the covariance matrix as identity, which in turn means that you assume that the distance of each component of $x$ from the corresponding component of the class mean is 1, and the different components are independent. This could be justified depending on your application, but I suspect the issue stems just from the numeric problem discussed above or that you are using some covariances that do not make sense (your question did not explain how the covariance matrices are obtained).

Caveat: if you have different $\Sigma$s for different classes, the $\Sigma_k$ in the normalization constant (the factor before exponential) of your modified pdf will scale the likelihoods depending on $k$ (but not on $x$), so in the identity covariance case this acts as a strange way of changing the prior distribution over classes. However, if your $\Sigma$ is constant over all classes, the normalization constant does not impact the results, and thus this is exactly equivalent to using identity covariance.

$\endgroup$
  • $\begingroup$ Thank you very much for the quick helpful response, the log trick worked great and helped me solve the first problem. As for the second problem, yes I am referring to the distance metric in the exponent. I provided some more details in my original question. Of note, the features in my feature space are uncorrelated, would this justify using the identity matrix for the covariance? $\endgroup$ – James Apr 26 '14 at 22:27
  • 1
    $\begingroup$ @James the identity matrix implies independent identically distributed features. If you are only certain of independence, that implies a diagonal matrix, where features may have different variances. Is it possible the procedure you have used has also normalized your features? This should be easy to check, their variances should be 1. $\endgroup$ – ilir Apr 26 '14 at 22:51
  • $\begingroup$ @ilir the total variance for each feature across all classes is equal at a value around 1, while variances within individual classes differ between features/classes. They are also much smaller between x*10E-2~3 to x*10E-23~24 in a kernelized version of the algorithm. This makes sense because the algorithm involves minimizing the within class variance. But perhaps the pooled within-class covariance doesn't make much sense when calculating the probability due to the differences. $\endgroup$ – James Apr 27 '14 at 0:18
  • $\begingroup$ On closer inspection this looks like a case of overfitting on the part of the dimensionality reduction technique. So my Euclidean based technique is probably getting an increase in performance over the Mahalanobis technique due to better generalization of the decision boundaries. $\endgroup$ – James Apr 27 '14 at 5:43

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.