Transformers have emerged as a preferred model for many tasks in natural langugage processing and vision. Recent efforts on training and deploying Transformers more efficiently have identified many strategies to approximate the self-attention matrix, a key module in a Transformer architecture. Effective ideas include various prespecified sparsity patterns, low-rank basis expansions and combinations thereof. In this paper, we revisit classical Multiresolution Analysis (MRA) concepts such as Wavelets, whose potential value in this setting remains underexplored thus far. We show that simple approximations based on empirical feedback and design choices informed by modern hardware and implementation challenges, eventually yield a MRA-based approach for self-attention with an excellent performance profile across most criteria of interest. We undertake an extensive set of experiments and demonstrate that this multi-resolution scheme outperforms most efficient self-attention proposals and is favorable for both short and long sequences. Code is available at \url{https://github.com/mlpen/mra-attention}.

Transformers have emerged as a powerful tool for a broad range of natural language processing tasks. A key component that drives the impressive performance of Transformers is the self-attention mechanism that encodes the influence or dependence of other tokens on each specific token. While beneficial, the quadratic complexity of self-attention on the input sequence length has limited its application to longer sequences - a topic being actively studied in the community. To address this limitation, we propose Nyströmformer - a model that exhibits favorable scalability as a function of sequence length. Our idea is based on adapting the Nyström method to approximate standard self-attention with O(n) complexity. The scalability of Nyströmformer enables application to longer sequences with thousands of tokens. We perform evaluations on multiple downstream tasks on the GLUE benchmark and IMDB reviews with standard sequence length, and find that our Nyströmformer performs comparably, or in a few cases, even slightly better, than standard self-attention. On longer sequence tasks in the Long Range Arena (LRA) benchmark, Nyströmformer performs favorably relative to other efficient self-attention methods. Our code is available at https://github.com/mlpen/Nystromformer.

Transformer-based models are widely used in natural language processing (NLP). Central to the transformer model is the self-attention mechanism, which captures the interactions of token pairs in the input sequences and depends quadratically on the sequence length. Training such models on longer sequences is expensive. In this paper, we show that a Bernoulli sampling attention mechanism based on Locality Sensitive Hashing (LSH), decreases the quadratic complexity of such models to linear. We bypass the quadratic cost by considering self-attention as a sum of individual tokens associated with Bernoulli random variables that can, in principle, be sampled at once by a single hash (although in practice, this number may be a small constant). This leads to an efficient sampling scheme to estimate self-attention which relies on specific modifications of LSH (to enable deployment on GPU architectures). We evaluate our algorithm on the GLUE benchmark with standard 512 sequence length where we see favorable performance relative to a standard pretrained Transformer. On the Long Range Arena (LRA) benchmark, for evaluating performance on long sequences, our method achieves results consistent with softmax self-attention but with sizable speed-ups and memory savings and often outperforms other efficient self-attention methods. Our code is available at https://github.com/mlpen/YOSO.

Entity matching (EM) finds data instances that refer to the same real-world entity. Most EM solutions perform blocking then matching. Many works have applied deep learning (DL) to matching, but far fewer works have applied DL to blocking. These blocking works are also limited in that they consider only a simple form of DL and some of them require labeled training data. In this paper, we develop the DeepBlocker framework that significantly advances the state of the art in applying DL to blocking for EM. We first define a large space of DL solutions for blocking, which contains solutions of varying complexity and subsumes most previous works. Next, we develop eight representative solutions in this space. These solutions do not require labeled training data and exploit recent advances in DL (e.g., sequence modeling, transformer, self supervision). We empirically determine which solutions perform best on what kind of datasets (structured, textual, or dirty). We show that the best solutions (among the above eight) outperform the best existing DL solution and the best existing non-DL solutions (including a state-of-the-art industrial non-DL solution), on dirty and textual data, and are comparable on structured data. Finally, we show that the combination of the best DL and non-DL solutions can perform even better, suggesting a new venue for research.

We present an approach for designing conversational interfaces (chatbots) that users interact with to determine whether or not a business rule applies in a context possessing uncertainty (from the point of view of the chatbot) as to the value of input facts. Our approach relies on Bayesian network models that bring together a business rule’s logical, deterministic aspects with its probabilistic components in a common framework. Our probabilistic-logic bots (PL-bots) evaluate business rules by iteratively prompting users to provide the values of unknown facts. The order facts are solicited is dynamic, depends on known facts, and is chosen using mutual information as a heuristic so as to minimize the number of interactions with the user. We have created a web-based content creation and editing tool that quickly enables subject matter experts to create and validate PL-bots with minimal training and without requiring a deep understanding of logic or probability. To date, domain experts at a well-known insurance company have successfully created and deployed over 80 PLbots to help insurance agents determine customer eligibility for policy discounts and endorsements.

In the insurance industry, timely and effective interaction with customers are at the core of everyday operations and processes that are key for a satisfactory customer experience. These interactions often result in sequences of data derived from events that occur over time. Such recurrent patterns can provide valuable information that can be used in a variety of ways to improve customer related work-flows. In this paper we demonstrate the application of a recently proposed algorithm to uncover such time patterns that takes into account the time between events to form such patterns. We use temporal customer data generated from two different use-cases (satisfaction and fraud) to show that this algorithm successfully detects patterns that occur in the insurance context.

Entity matching (EM) finds data instances that refer to the same real-world entity. In 2015, we started the Magellan project at UW-Madison, joint with industrial partners, to build EM systems. Most current EM systems are stand-alone monoliths. In contrast, Magellan borrows ideas from the field of data science (DS), to build a new kind of EM systems, which is an ecosystem of interoperable tools. \em This paper provides a progress report on the past 3.5 years of Magellan, focusing on the system aspects and on how ideas from the field of data science have been adapted to the EM context. We argue why EM can be viewed as a special class of DS problems, and thus can benefit from system building ideas in DS. We discuss how these ideas have been adapted to build \pymatcher\ and \cloudmatcher, EM tools for power users and lay users. These tools have been successfully used in 21 EM tasks at 12 companies and domain science groups, and have been pushed into production for many customers. We report on the lessons learned, and outline a new envisioned Magellan ecosystem, which consists of not just on-premise Python tools, but also interoperable microservices deployed, executed, and scaled out on the cloud, using tools such as Dockers and Kubernetes.

Ordinal regression aims to classify instances into ordinal categories. In this paper, body mass index (BMI) category estimation from facial images is cast as an ordinal regression problem. In particular, noisy binary search algorithms based on pairwise comparisons are employed to exploit the ordinal relationship among BMI categories. Comparisons are performed with Siamese architectures, one of which uses the Bradley-Terry model probabilities as target. The Bradley-Terry model describes probabilities of the possible outcomes when elements of a set are repeatedly compared with one another in pairs. Experimental results show that our approach outperforms classification and regression-based methods at estimating BMI categories.

Recommender systems have become extremely important to various types of industries where customer interaction and feedback is paramount to the success of the business. For companies that face changes that arise with ever-growing markets, providing product recommendations to new and existing customers is a challenge. Furthermore, it is important to have an algorithm which is descriptive, scalable, agnostic to missing features, and robust in providing these recommendations. Directed graphical models meet all these demands; however, if the dimensionality of the features is high, structure learning and inference can become computationally prohibitive. In this work, we propose an algorithm with some novel aspects to learn the structure of a graphical model (e.g. Bayesian network), which considerably speeds up both training (from days to minutes in some cases) and inference run-times with respect to standard Bayesian structure learning approaches, while achieving similar accuracy. We also show that this approach produces more accurate predictions than a state-of-the-art matrix factorization algorithm in the absence of complete evidence on several insurance-related datasets.

As data science applications proliferate, more and more lay users must perform data integration (DI) tasks, which used to be done by sophisticated CS developers. Thus, it is increasingly critical that we develop hands-off DI services, which lay users can use to perform such tasks without asking for help from developers. We propose to demonstrate such a service. Specifically, we will demonstrate CloudMatcher, a hands-off cloud/crowd service for entity matching (EM). To use CloudMatcher to match two tables, a lay user only needs to upload them to the CloudMatcher's Web page then iteratively label a set of tuple pairs as match/no-match. Alternatively, the user can enlist a crowd of workers to label the pairs. In either case, the lay user can easily perform EM end-to-end without having to involve any developers. Cloud-Matcher has been used in several domain science projects at UW-Madison and at several organizations, and is scheduled to be deployed in a large company in Summer 2018. In the demonstration we will show how easy it is for lay users to perform EM (either via interactive labeling or crowdsourcing), how users can easily create and experiment with a range of EM workflows, and how CloudMatcher can scale to many concurrent users and large datasets.

In this paper we describe a deployed recommender system to predict insurance products for new and existing customers. Our goal is to give our customers personalized recommendations based on what other similar people with similar portfolios have, in order to make sure they were adequately covered for their needs. Our system uses customer characteristics in addition to customer portfolio data. Since the number of possible recommendable products is relatively small, compared to other recommender domains, and missing data is relatively frequent, we chose to use Bayesian Networks for modeling our system. Experimental results show advantages of using probabilistic graphical models over the widely used low-rank matrix factorization model for the insurance domain.

Timely identification of potentially dissatisfied customers enables us to take meaningful interventions to improve customer experience. The goal of this work is to create models that can predict customer satisfaction for active insurance claims at any point in time during the claim process. In order to capture relevant temporal information, we introduce the concept of a "journey-map": a data-driven structured timeline where all the relevant events pertinent to the claim process are registered and positioned temporally with respect to each other. We also describe a machine-learning-based framework to extract and discover meaningful information relevant for the task at hand. The result of this work is a deployed system currently used during the claims process.

Medical coding or classification is the process of transforming information contained in patient medical records into standard predefined medical codes. There are several worldwide accepted medical coding conventions associated with diagnoses and medical procedures; however, in the United States the Ninth Revision of ICD(ICD-9) provides the standard for coding clinical records. Accurate medical coding is important since it is used by hospitals for insurance billing purposes. Since after discharge a patient can be assigned or classified to several ICD-9 codes, the coding problem can be seen as a multi-label classification problem. In this paper, we introduce a multi-label large-margin classifier that automatically learns the underlying inter-code structure and allows the controlled incorporation of prior knowledge about medical code relationships. In addition to refining and learning the code relationships, our classifier can also utilize this shared information to improve its performance. Experiments on a publicly available dataset containing clinical free text and their associated medical codes showed that our proposed multi-label classifier outperforms related multi-label models in this problem.

A popular approach for dimensionality reduction and data analysis is principal component analysis (PCA). A limiting factor with PCA is that it does not inform us on which of the original features are important. There is a recent interest in sparse PCA (SPCA). By applying an L1 regularizer to PCA, a sparse transformation is achieved. However, true feature selection may not be achieved as non-sparse coefficients may be distributed over several features. Feature selection is an NP-hard combinatorial optimization problem. This paper relaxes and re-formulates the feature selection problem as a convex continuous optimization problem that minimizes a mean-squared-reconstruction error (a criterion optimized by PCA) and considers feature redundancy into account (an important property in PCA and feature selection). We call this new method Convex Principal Feature Selection (CPFS). Experiments show that CPFS performed better than SPCA in selecting features that maximize variance or minimize the mean-squared-reconstruction error.

Missing data is a given in the medical domain, so machine learning models should have satisfactory performance even when missing data occurs. Our previous work has focused on support vector machines (SVM), but we hypothesize that Bayesian networks (BN) can handle missing data better. To test the hypothesis, we trained a BN and SVM model for 2 year survival on 322 lung cancer patients and compared their performance in three separate external datasets (35, 47, 33 patients), each with their own characteristics in terms of missing data. The models used tumor size, clinical T and N stage, involved lymph nodes and WHO performance as prognostic features. We found that the BN model performed better than SVM (AUC 0.77, 0.72. 0.70 vs. 0.71, 0.68, 0.69), especially if tumor size was missing. We conclude that BN models are better suited for the medical domain, as they can handle missing data better.

Coronary Heart Disease can be diagnosed by assessing the regional motion of the heart walls in ultrasound images of the left ventricle. Even for experts, ultrasound images are difficult to interpret leading to high intra-observer variability. Previous work indicates that in order to approach this problem, the interactions between the different heart regions and their overall influence on the clinical condition of the heart need to be considered. To do this, we propose a method for jointly learning the structure and parameters of conditional random fields, formulating these tasks as a convex optimization problem. We consider block-L1 regularization for each set of features associated with an edge, and formalize an efficient projection method to find the globally optimal penalized maximum likelihood solution. We perform extensive numerical experiments comparing the presented method with related methods that approach the structure learning problem differently. We verify the robustness of our method on echocardiograms collected in routine clinical practice at one hospital.

Privacy-preserving data mining (PPDM) is an emergent research area that addresses the incorporation of privacy preserving concerns to data mining techniques. In this paper we propose a privacy-preserving (PP) Cox model for survival analysis, and consider a real clinical setting where the data is horizontally distributed among different institutions. The proposed model is based on linearly projecting the data to a lower dimensional space through an optimal mapping obtained by solving a linear programming problem. Our approach differs from the commonly used random projection approach since it instead finds a projection that is optimal at preserving the properties of the data that are important for the specific problem at hand. Since our proposed approach produces an sparse mapping, it also generates a PP mapping that not only projects the data to a lower dimensional space but it also depends on a smaller subset of the original features (it provides explicit feature selection). Real data from several European healthcare institutions are used to test our model for survival prediction of non-small-cell lung cancer patients. These results are also confirmed using publicly available benchmark datasets. Our experimental results show that we are able to achieve a near-optimal performance without directly sharing the data across different data sources. This model makes it possible to conduct large-scale multi-centric survival analysis without violating privacy-preserving requirements.

Cross validation allows models to be tested using the full training set by means of repeated resampling; thus, maximizing the total number of points used for testing and potentially, helping to protect against overfitting. Improvements in computational power, recent reductions in the (computational) cost of classification algorithms, and the development of closed-form solutions (for performing cross validation in certain classes of learning algorithms) makes it possible to test thousand or millions of variants of learning models on the data. Thus, it is now possible to calculate cross validation performance on a much larger number of tuned models than would have been possible otherwise. However, we empirically show how under such large number of models the risk for overfitting increases and the performance estimated by cross validation is no longer an effective estimate of generalization; hence, this paper provides an empirical reminder of the dangers of cross validation. We use a closed-form solution that makes this evaluation possible for the cross validation problem of interest. In addition, through extensive experiments we expose and discuss the effects of the overuse/misuse of cross validation in various aspects, including model selection, feature selection, and data dimensionality. This is illustrated on synthetic, benchmark, and real-world data sets.

We propose a novel privacy-preserving support vector machine (SVM) classifier for a data matrixAwhose input feature columns are divided into groups belonging to different entities. Each entity is unwilling to share its group of columns or make it public. Our classifier is based on the concept of a reduced kernelK(A,B′), whereB′ is the transpose of a random matrixB. The column blocks ofBcorresponding to the different entities are privately generated by each entity and never made public. The proposed linear or nonlinear SVM classifier, which is public but does not reveal any of the privately held data, has accuracy comparable to that of an ordinary SVM classifier that uses the entire set of input features directly.

In biology and medical sciences, highly parallel biological assays spurred a revolution leading to the emergence of the '-omics' era. Dimensionality reduction techniques are necessary to be able to analyze, interpret, validate and take advantage of the tremendous wealth of highly dimensional data they provide. This paper is based on a DNA microarray study providing gene signatures for hypoxia. These gene signatures were tested on a large breast cancer data set for assessing their prognostic power by means of Kaplan-Meier survival, univariate, and multivariate analyses. We explore the use of several mathematical programming-based techniques that aim to reduce the gene signature sizes as much as possible while maintaining the key characteristics of the original signature, more precisely: the signature prognostic and diagnostic significance. The proposed signature reduction techniques have very interesting potential uses. Indeed, by downsizing the relevant data to a manageable size, one can then patent the core set of biomarkers and also create a dedicated assay (e.g.: on a customized array) for routine applications (e.g.: in the clinical set up) leading to individualized medicine capabilities. Our experiments show that the reduced hypoxia signatures reproduced qualitatively and quantitatively in a similar way that of the original ones.

We present LungCAD, a computer aided diagnosis (CAD) system that employs a classification algorithm for detecting solid pulmonary nodules from CT thorax studies. We briefly describe some of the machine learning techniques developed to overcome the real world challenges in this medical domain. The most significant hurdle in transitioning from a machine learning research prototype that performs well on an in-house dataset into a clinically deployable system, is the requirement that the CAD system be tested in a clinical trial. We describe the clinical trial in which LungCAD was tested: a large scale multi-reader, multi-case (MRMC) retrospective observational study to evaluate the effect of CAD in clinical practice for detecting solid pulmonary nodules from CT thorax studies. The clinical trial demonstrates that every radiologist that participated in the trial had a significantly greater accuracy with LungCAD, both for detecting nodules and identifying potentially actionable nodules; this, along with other findings from the trial, has resulted in FDA approval for LungCAD in late 2006.

This paper describes a novel classification method for computer aided detection (CAD) that identifies structures of interest from medical images. CAD problems are challenging largely due to the following three characteristics. Typical CAD training data sets are large and extremely unbalanced between positive and negative classes. When searching for descriptive features, researchers often deploy a large set of experimental features, which consequently introduces irrelevant and redundant features. Finally, a CAD system has to satisfy stringent real-time requirements.This work is distinguished by three key contributions. The first is a cascade classification approach which is able to tackle all the above difficulties in a unified framework by employing an asymmetric cascade of sparse classifiers each trained to achieve high detection sensitivity and satisfactory false positive rates. The second is the incorporation of feature computational costs in a linear program formulation that allows the feature selection process to take into account different evaluation costs of various features. The third is a boosting algorithm derived from column generation optimization to effectively solve the proposed cascade linear programs.We apply the proposed approach to the problem of detecting lung nodules from helical multi-slice CT images. Our approach demonstrates superior performance in comparison against support vector machines, linear discriminant analysis and cascade AdaBoost. Especially, the resulting detection system is significantly sped up with our approach.

Calculation of object similarity, for example through a distance function, is a common part of data mining and machine learning algorithms. This calculation is crucial for efficiency since distances are usually evaluated a large number of times, the classical example being query-by-example (find objects that are similar to a given query object). Moreover, the performance of these algorithms depends critically on choosing a good distance function. However, it is often the case that (1) the correct distance is unknown or chosen by hand, and (2) its calculation is computationally expensive (e.g., such as for large dimensional objects). In this paper, we propose a method for constructing relative-distance preserving low-dimensional mapping (sparse mappings). This method allows learning unknown distance functions (or approximating known functions) with the additional property of reducing distance computation time. We present an algorithm that given examples of proximity comparisons among triples of objects (object i is more like object j than object k), learns a distance function, in as few dimensions as possible, that preserves these distance relationships. The formulation is based on solving a linear programming optimization problem that finds an optimal mapping for the given dataset and distance relationships. Unlike other popular embedding algorithms, this method can easily generalize to new points, does not have local minima, and explicitly models computational efficiency by finding a mapping that is sparse, i.e. one that depends on a small subset of features or dimensions. Experimental evaluation shows that the proposed formulation compares favorably with a state-of-the art method in several publicly available datasets.

Many computer aided diagnosis (CAD) problems can be best modelled as a multiple-instance learning (MIL) problem with unbalanced data: i.e. , the training data typically consists of a few positive bags, and a very large number of negative instances. Existing MIL algorithms are much too computationally expensive for these datasets. We describe CH, a framework for learning a Convex Hull representation of multiple instances that is significantly faster than existing MIL algorithms. Our CH framework applies to any standard hyperplane-based learning algorithm, and for some algorithms, is guaranteed to find the global optimal solution. Experimental studies on two different CAD applications further demonstrate that the proposed algorithm significantly improves diagnostic accuracy when compared to both MIL and traditional classifiers. Although not designed for standard MIL problems (which have both positive and negative bags and relatively balanced datasets), comparisons against other MIL methods on benchmark problems also indicate that the proposed method is competitive with the state-of-the-art.

We propose an algorithm to construct classification models with a mixture of kernels from labeled and unlabeled data. The derived classifier is a mixture of models, each based on one kernel choice from a library of kernels. The sparse-favoring 1-norm regularization method is employed to restrict the complexity of mixture models and to achieve the sparsity of solutions. By modifying the column generation boosting algorithm LPBoost to a more general linear programming formulation, we are able to efficiently solve mixture-of-kernel problems and automatically select kernel basis functions centered at labeled data as well as unlabeled data. The effectiveness of the proposed approach is proved by experimental results on benchmark datasets.

Alzheimer's disease is the most frequent type of dementia for elderly patients. Due to aging populations the occurrence of this disease will increase in the next years. Early diagnosis is crucial to be able to develop more powerful treatments. Brain perfusion changes can be a marker for Alzheimer's disease. In this article we study the use of SPECT perfusion imaging for the diagnosis of Alzheimer's disease differentiating between images from healthy subjects and images from Alzheimer's disease patients. Our classification approach is based on a linear programming formulation similar to the 1-norm support vector machines. In contrast with other linear hyperplane-based methods that perform simultaneous feature selection and classification, our proposed formulation incorporates proximity information about the features and generates a classifier that does not just select the most relevant voxels but the most relevant "areas" for classification resulting in more robust classifiers that are better suitable for interpretation. This approach is compared with the classical Fisher linear discriminant (FLD) classifier as well as with statistical parametric mapping (SPM). We tested our method on data from four European institutions. Our method achieved sensitivity of 84.4% at 90.9% specificity, this is considerable better the human experts. Our method also outperformed the ELD and SPM techniques. We conclude that our approach has the potential to be a useful help for clinicians.

Coronary Heart Disease is the single leading cause of death world-wide, with lack of early diagnosis being a key contributory factor. This disease can be diagnosed by measuring and scoring regional motion of the heart wall in echocardiography images of the left ventricle (LV) of the heart. We describe a completely automated and robust technique that detects diseased hearts based on automatic detection and tracking of the endocardium and epicardium of the LV. We describe a novel feature selection technique based on mathematical programming that results in a robust hyperplane-based classifier. The classifier depends only on a small subset of numerical feature extracted from dualcontours tracked through time. We verify the robustness of our system on echocardiograms collected in routine clinical practice at one hospital, both with the standard crossvalidation analysis, and then on a held-out set of completely unseen echocardiography images.

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 propose efficient algorithms for learning ranking functions from or- der constraints between sets—i.e. classes—of training samples. Our al- gorithms may be used for maximizing the generalized Wilcoxon Mann Whitney statistic that accounts for the partial ordering of the classes: spe- cial cases include maximizing the area under the ROC curve for binary classification and its generalization for ordinal regression. Experiments on public benchmarks indicate that: (a) the proposed algorithm is at least as accurate as the current state-of-the-art; (b) computationally, it is sev- eral orders of magnitude faster and—unlike current methods—it is easily able to handle even large datasets with over 20,000 samples.

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.

We propose a fast iterative classification algorithm for Kernel Fisher Discriminant (KFD) using heterogeneous kernel models. In contrast with the standard KFD that requires the user to predefine a kernel function, we incorporate the task of choosing an appropriate kernel into the optimization problem to be solved. The choice of kernel is defined as a linear combination of kernels belonging to a potentially large family of different positive semidefinite kernels. The complexity of our algorithm does not increase significantly with respect to the number of kernels on the kernel family. Experiments on several benchmark datasets demonstrate that generalization performance of the proposed algorithm is not significantly different from that achieved by the standard KFD in which the kernel parameters have been tuned using cross validation. We also present results on a real-life colon cancer dataset that demonstrate the efficiency of the proposed method.

Prior knowledge in the form of multiple polyhedral sets, each be(cid:173) longing to one of two categories, is introduced into a reformulation of a linear support vector machine classifier. The resulting formu(cid:173) lation leads to a linear program that can be solved efficiently. Real world examples, from DNA sequencing and breast cancer prognosis, demonstrate the effectiveness of the proposed method. Numerical results show improvement in test set accuracy after the incorpo(cid:173) ration of prior knowledge into ordinary, data-based linear support vector machine classifiers. One experiment also shows that a lin(cid:173) ear classifier, based solely on prior knowledge, far outperforms the direct application of prior knowledge rules to classify data. Keywords: use and refinement of prior knowledge, sup(cid:173) port vector machines, linear programming

Using a recently introduced proximal support vector machine classifier [4], a very fast and simple incremental support vector machine (SVM) classifier is proposed which is capable of modifying an existing linear classifier by both retiring old data and adding new data. A very important feature of the proposed single-pass algorithm, which allows it to handle massive datasets, is that huge blocks of data, say of the order of millions of points, can be stored in blocks of size (n + 1)2, where n is the usually small (typically less than 100) dimensional input space in which the data resides. To demonstrate the effectiveness of the algorithm we classify a dataset of 1 billion points in 10-dimensional input space into two classes in less than 2.5 hours on a 400 MHz Pentium II processor.

Instead of a standard support vector machine (SVM) that classifies points by assigning them to one of two disjoint half-spaces, points are classified by assigning them to the closest of two parallel planes (in input or feature space) that are pushed apart as far as possible. This formulation, which can also be interpreted as regularized least squares and considered in the much more general context of regularized networks [8, 9], leads to an extremely fast and simple algorithm for generating a linear or nonlinear classifier that merely requires the solution of a single system of linear equations. In contrast, standard SVMs solve a quadratic or a linear program that require considerably longer computational time. Computational results on publicly available datasets indicate that the proposed proximal SVM classifier has comparable test set correctness to that of standard SVM classifiers, but with considerably faster computational time that can be an order of magnitude faster. The linear proximal SVM can easily handle large datasets as indicated by the classification of a 2 million point 10-attribute set in 20.8 seconds. All computational results are based on 6 lines of MATLAB code.

The problem of extracting a minimal number of data points from a large dataset, in order to generate a support vector machine (SVM) classifier, is formulated as a concave min-imization problem and solved by a finite number of linear programs. This minimal set of data points, which is the smallest number of support vectors that completely char-acterize a separating plane classifier, is considerably smaller than that required by a standard 1-norm support vector ma-chine with or without feature selection. The proposed ap-proach also incorporates a feature selection procedure that results in a minimal number of input features used by the classifier. Tenfold cross validation gives as good or better test results using the proposed minimal support vector ma-chine (MSVM) classifier based on the smaller set of data points compared to a standard 1-norm support vector ma-chine classifier. The reduction in data points used by an MSVM classifier over those used by a 1-norm SVM classifier averaged 66 % on seven public datasets and was as high as 81%. This makes MSVM a useful incremental classification tool which maintains only a small fraction of a large dataset before merging and processing it with new incoming data. Keywords support vector machines, data classification, data selection, concave minimization, linear programming 1.