We present results from a comparative empirical study of two methods for constructing support vector machines (SVMs). The first method is the conventional one based on the quadratic programming approach, which builds the optimal separating hyperplane maximizing the margin between two classes (SVM-Q). The second method is based on the linear programming approach suggested by Vapnik to build a separating hyperplane with the minimum number of support vectors (SVM-L). Using synthetic data from two classes, we compare the classification performance of these SVMs, with a geometrical comparison of their separating hyperplanes and support vectors. We show that both classifiers achieve practically identical classification accuracy and generalization performance. However, SVM-L has many fewer support vectors than SVM-Q. We also prove that, in contrast to SVM-Q, which selects support vectors from the margin between two classes, support vectors of SVM-L lie on the furthermost borders of the classes, at the maximum distance from the opposite class.

Graph clustering partitions a graph into subgraphs with strongly interconnected nodes, while nodes belonging to different subgraphs are weakly connected. In this paper, we propose a new clustering method applicable to either weighted or unweighted graphs in which each cluster consists of a highly dense core region surrounded by a region with lower density. We have developed a highly efficient and robust method to identify nodes belonging to dense cores of clusters. The set of the nodes is then divided into groups, each of which is the representative of one cluster. These groups are finally expanded into complete clusters covering all the nodes of the graph. Experiments with both synthetic and real datasets for gene expression analysis and image segmentation yield very encouraging results.

We present a method for automatically extracting groups of orthologous genes from a large set of genomes by a new clustering algorithm on a weighted multipartite graph. The method assigns a score to an arbitrary subset of genes from multiple genomes to assess the orthologous relationships between genes in the subset. This score is computed using sequence similarities between the member genes and the phylogenetic relationship between the corresponding genomes. An ortholog cluster is found as the subset with the highest score, so ortholog clustering is formulated as a combinatorial optimization problem. The algorithm for finding an ortholog cluster runs in time O(absolute value(E) + absolute value(V) log absolute value(V)), where V and E are the sets of vertices and edges, respectively, in the graph. However, if we discretize the similarity scores into a constant number of bins, the runtime improves to O(absolute value(E) + absolute value(V)). The proposed method was applied to seven complete eukaryote genomes on which the manually curated database of eukaryotic ortholog clusters, KOG, is constructed. A comparison of our results with the manually curated ortholog clusters shows that our clusters are well correlated with the existing clusters.

We have developed a method for distinguishing between correctly labeled and mislabeled data sampled from video sequences and used in the construction of a facial expression recognition classifier. The novelty of our approach lies in training a single, optimal classifier type (a support vector machine, or SVM) on multiple representations of the data, involving different "discriminating" subspaces. Results of a preliminary study on the discrimination of "high stress" vs. "low stress" facial expression data by this method confirms that our novel approach is able to distinguish subproblems where labeling is highly reliable from those where mislabeling can lead to high error rates. In helping detect data subsamples which yield misleading classification results, the method is also a rapid, highly efficient cross-validated approach for eliminating outliers.

The problem of prospecting oil and gas reserves in the crystalline basement of the Earth mantle by way of a combined interpretation of seismic data registered on the daylight surface and direct information from a sparse net of exploratory wells is considered as pattern recognition problem in which the role of objects whose class membership is to be recovered is played by points of the three-dimensional underground medium. Local properties of reflected seismic signals serve as features of the membership of the respective rock mass zones in the class of collectors, i.e. spatial areas capable of accumulating fluids, whereas direct data obtained from exploratory wells serve as trainer's information. A new spatial approach to supervised pattern recognition is proposed which makes use of the fact that objects to be recognized are arranged in an array in space. Along with the additional assumption that immediately adjacent points offer a tendency to belong to the same class, this fact allows for drawing reliable decisions from relatively unreliable features.

Describes a new, logic-based methodology for analyzing observations. The key features of this “logical analysis of data” (LAD) methodology are the discovery of minimal sets of features that are necessary for explaining all observations and the detection of hidden patterns in the data that are capable of distinguishing observations describing “positive” outcome events from “negative” outcome events. Combinations of such patterns are used for developing general classification procedures. An implementation of this methodology is described in this paper, along with the results of numerical experiments demonstrating the classification performance of LAD in comparison with the reported results of other procedures. In the final section, we describe three pilot studies on applications of LAD to oil exploration, psychometric testing and the analysis of developments in the Chinese transitional economy. These pilot studies demonstrate not only the classification power of LAD but also its flexibility and capability to provide solutions to various case-dependent problems.

A class of signal and image processing problems is considered from the standpoint of treating them as those of coordinating the local data-dependent information and model-based smoothness constraints. Such a generalized problem is set as the formal problem of minimization of a separable objective function defined on an appropriate neighborhood graph of data array elements.

Four problems of image processing, namely, those of smoothing. texture image segmentation, matching two images of similar structure, and building the local texture orientation map, are considered jointly as problems which can be treated as those of transforming the original image into another function on the image plane. We generalized statistical image processing procedure is aimed at finding a compromise between the local image-dependent information on the values of the hidden function at each pixel and the a priori information expressed in the form of some Markov smoothness constraints. For attaining a higher computation speed, instead of a full unitary prior Markov model of the hidden field, a compromise composite model is used which consists of a set of independent identical tree-like Markov neighborhood graphs.