We describe an algorithm for converting linear support vector machines and any other arbitrary hyperplane-based linear classifiers into a set of non-overlapping rules that, unlike the original classifier, can be easily interpreted by humans. Each iteration of the rule extraction algorithm is formulated as a constrained optimization problem that is computationally inexpensive to solve. We discuss various properties of the algorithm and provide proof of convergence for two different optimization criteria We demonstrate the performance and the speed of the algorithm on linear classifiers learned from real-world datasets, including a medical dataset on detection of lung cancer from medical images. The ability to convert SVM's and other "black-box" classifiers into a set of human-understandable rules, is critical not only for physician acceptance, but also to reducing the regulatory barrier for medical-decision support systems based on such classifiers.

We describe a method for sparse feature selection for a class of problems motivated by our work in Computer-Aided Detection (CAD) systems for identifying structures of interest in medical images. We propose a sparse formulation for Fisher Linear Discriminant (FLD) that scales well to large datasets; our method inherits all the desirable properties of FLD, while improving on handling large numbers of irrelevant and redundant features. We demonstrate that our sparse FLD formulation outperforms conventional FLD and two other methods for feature selection from the literature on both an artificial dataset and a real-world Colon CAD dataset.

Inference from hospital patient records is difficult because data collection is done at arbitrary (not evenly-spaced) time intervals, and key clinical information is recorded only in unstructured form (as free text in doctors’ notes). We present REMIND, a framework for performing inference from patient records based upon continuous-time Markov models and Bayesian networks. We empirically justify the need for such a complex model. REMIND only uses easily-available domain knowledge which we obtain from physicians and medical literature, which may be inaccurate. We also demonstrate the robustness of our approach to parameter assignment.

Existing patient records are a valuable resource for automated outcomes analysis and knowledge discovery. However, key clinical data in these records is typically recorded in unstructured form as free text and images, and most structured clinical information is poorly organized. Time-consuming interpretation and analysis is required to convert these records into structured clinical data. Thus, only a tiny fraction of this resource is utilized. We present REMIND, a Bayesian Framework for Reliable Extraction and Meaningful Inference from Nonstructured Data. REMIND integrates and blends the structured and unstructured clinical data in patient records to automatically created high-quality structured clinical data. This structuring allows existing patient records to be mined for quality assurance, regulatory compliance, and to relate financial and clinical factors. We demonstrate REMIND on two medical applications: (a) Extract "recurrence", the key outcome for measuring treatment effectiveness, for colon cancer patients (ii) Extract key diagnoses and complications for acute myocardial infarction (heart attack) patients, and demonstrate the impact of these clinical factors on financial outcomes.

Let X/sub 1/, X/sub 2/,... be an arbitrary random process taking values in a totally bounded subset of a separable metric space. Associated with X/sub i/ we observe Y/sub i/ drawn from an unknown conditional distribution F(y|X/sub i/=x) with continuous regression function m(x)=E[Y|X=x]. The problem of interest is to estimate Y/sub n/ based on X/sub n/ and the data {(X/sub i/, Y/sub i/)}/sub i=1//sup n-1/. We construct appropriate data-dependent nearest neighbor and kernel estimators and show, with a very elementary proof, that these are consistent for every process X/sub 1/, X/sub 2/,.

Principal curves, like principal components, are a tool used in multivariate analysis for ends like feature extraction. Defined in their original form, principal curves need not exist for general distributions. The existence of principal curves with bounded length for any distribution that satisfies some minimal regularity conditions has been shown. We define principal curves with bounded turn, show that they exist, and present a learning algorithm for them. Principal components are a special case of such curves when the turn is zero.