In the past decades Machine Learning tools have been successfully used in several medical diagnostic problems. While they often significantly outperform expert physicians (in terms of diagnostic accuracy, sensitivity, and specificity), they are mostly not being used in practice. One reason for this is that it is difficult to obtain an unbiased estimation of diagnosis? reliability. We discuss how reliability of diagnoses is assessed in medical decision making and propose a general framework for reliability estimation in Machine Learning, based on transductive inference. We compare our approach with the usual Machine Learning probabilistic approach as well as with classical stepwise diagnostic process where the reliability of diagnosis is presented as its post-test probability. The proposed transductive approach is evaluated in a practical problem of clinical diagnosis of the coronary artery disease. Significant improvements over existing techniques are achieved.