566534
Semi-supervised Protein Classification Using Cluster Kernels
MOTIVATION
Building an accurate protein classification system depends critically upon choosing a good representation of the input sequences of amino acids. Recent work using string kernels for protein data has achieved state-of-the-art classification performance. However, such representations are based only on labeled data--examples with known 3D structures, organized into structural classes--whereas in practice, unlabeled data are far more plentiful.


RESULTS
In this work, we develop simple and scalable cluster kernel techniques for incorporating unlabeled data into the representation of protein sequences. We show that our methods greatly improve the classification performance of string kernels and outperform standard approaches for using unlabeled data, such as adding close homologs of the positive examples to the training data. We achieve equal or superior performance to previously presented cluster kernel methods and at the same time achieving far greater computational efficiency.


AVAILABILITY
Source code is available at www.kyb.tuebingen.mpg.de/bs/people/weston/semiprot. The Spider matlab package is available at www.kyb.tuebingen.mpg.de/bs/people/spider.


SUPPLEMENTARY INFORMATION
www.kyb.tuebingen.mpg.de/bs/people/weston/semiprot.
1402489
Semi-supervised Learning on Directed Graphs
Given a directed graph in which some of the nodes are labeled, we investigate the question of how to exploit the link structure of the graph to infer the labels of the remaining unlabeled nodes. To that extent we propose a regularization framework for functions defined over nodes of a directed graph that forces the classification function to change slowly on densely linked subgraphs. A powerful, yet computationally simple classification algorithm is derived within the proposed framework. The experimental evaluation on real-world Web classification problems demonstrates encouraging results that validate our approach.
2763612
Information Marginalization on Subgraphs
Real-world data often involves objects that exhibit multiple relationships; for example, ‘papers' and ‘authors' exhibit both paper-author interactions and paper-paper citation relationships. A typical learning problem requires one to make inferences about a subclass of objects (e.g. ‘papers'), while using the remaining objects and relations to provide relevant information. We present a simple, unified mechanism for incorporating information from multiple object types and relations when learning on a targeted subset. In this scheme, all sources of relevant information are marginalized onto the target subclass via random walks. We show that marginalized random walks can be used as a general technique for combining multiple sources of information in relational data. With this approach, we formulate new algorithms for transduction and ranking in relational data, and quantify the performance of new schemes on real world data—achieving good results in many problems.
16394993
Regularization on Discrete Spaces
We consider the classification problem on a finite set of objects. Some of them are labeled, and the task is to predict the labels of the remaining unlabeled ones. Such an estimation problem is generally referred to as transductive inference. It is well-known that many meaningful inductive or supervised methods can be derived from a regularization framework, which minimizes a loss function plus a regularization term. In the same spirit, we propose a general discrete regularization framework defined on finite object sets, which can be thought of as discrete analogue of classical regularization theory. A family of transductive inference schemes is then systemically derived from the framework, including our earlier algorithm for transductive inference, with which we obtained encouraging results on many practical classification problems. The discrete regularization framework is built on discrete analysis and geometry developed by ourselves, in which a number of discrete differential operators of various orders are constructed, which can be thought of as discrete analogues of their counterparts in the continuous case.
508435
Learning with Local and Global Consistency
We consider the general problem of learning from labeled and unlabeled data, which is often called semi-supervised learning or transductive inference. A principled approach to semi-supervised learning is to design a classifying function which is sufficiently smooth with respect to the intrinsic structure collectively revealed by known labeled and unlabeled points. We present a simple algorithm to obtain such a smooth solution. Our method yields encouraging experimental results on a number of classification problems and demonstrates effective use of unlabeled data.
16721854
Learning from labeled and unlabeled data on a directed graph
We propose a general framework for learning from labeled and unlabeled data on a directed graph in which the structure of the graph including the directionality of the edges is considered. The time complexity of the algorithm derived from this framework is nearly linear due to recently developed numerical techniques. In the absence of labeled instances, this framework can be utilized as a spectral clustering method for directed graphs, which generalizes the spectral clustering approach for undirected graphs. We have applied our framework to real-world web classification problems and obtained encouraging results.
20468093
A Multiplier Structure Based on a Novel Real-time CSD Recoding
Implementation of digital signal processing (DSP) algorithms in hardware, such as field programmable gate arrays (FPGAs), requires a large number of multiplications. In this paper, we introduce a novel multiplier structure that converts from 2's complement to canonical signed digit (CSD) representation in real time. The proposed algorithm increases the number of zero partial products (which can be simplified by shift operations) to approximately 66.7% compared with 50% for modified Booth's recoding. Also, the proposed hardware structure reduces the non-zero partial products to a minimum, and consequently the number of arithmetic operations in the carry-save structure is reduced. So, our proposed hardware decreases both the time required for multiplication and the power consumption of the multiplier. Furthermore, because the proposed structure uses real time CSD recoding, and does not require a fixed value for the multiplier input to be known a priori, the proposed multiplier can be used to implement digital filters with non-fixed filter coefficients, such as adaptive filters.
474823
Boosting the Feature Space: Text Classification for Unstructured Data on the Web
The issue of seeking efficient and effective methods for classifying unstructured text in large document corpora has received much attention in recent years. Traditional document representation like bag-of-words encodes documents as feature vectors, which usually leads to sparse feature spaces with large dimensionality, thus making it hard to achieve high classification accuracies. This paper addresses the problem of classifying unstructured documents on the Web. A classification approach is proposed that utilizes traditional feature reduction techniques along with a collaborative filtering method for augmenting document feature spaces. The method produces feature spaces with an order of magnitude less features compared with a baseline bag-of-words feature selection method. Experiments on both real-world data and benchmark corpus indicate that our approach improves classification accuracy over the traditional methods for both support vector machines and AdaBoost classifiers.
7316344
CLINCH: Clustering Incomplete High-Dimensional Data for Data Mining Application
Clustering is a common technique in data mining to discover hidden patterns from massive datasets. With the development of privacy-maintaining data mining application, clustering incomplete high-dimensional data has becoming more and more useful. Motivated by these limits, we develop a novel algorithm CLINCH, which could produce fine clusters on incomplete high-dimensional data space. To handle missing attributes, CLINCH employs a prediction method that can be more precise than traditional techniques. On the other hand, we also introduce an efficient way in which dimensions are processed one by one to attack the “curse of dimensionality”. Experiments show that our algorithm not only outperforms many existing high-dimensional clustering algorithms in scalability and efficiency, but also produces precise results.
206963206
Efficient adaptive Volterra filters for active nonlinear noise control with a linear secondary-path
Using a nonlinear filter to control a linear device has been studied in Strauch and Mulgrew (1998), and been proved to be effective in active noise control (ANC) when: i) the secondary path has a linear and nonminimum phase transfer function, and the reference noise is a nonlinear, predictable noise or non-Gaussian noise; ii) the primary path has a nonlinear effect. Tan et al. (2001) reinforced these statements and successfully implemented this idea with an adaptive Volterra filter, and developed an algorithm called the Volterra filtered-x LMS (VFXLMS) algorithm. However this VFXLMS suffers from a heavy computational burden as well as stability problems. In this paper, we provide several alternatives to VFXLMS: the modified Volterra LMS algorithm that increases the convergence rate by slightly increasing the computational burden, the filtered-error Volterra LMS algorithms (including the adjoint Volterra LMS algorithm and the secondary-path equalization Volterra LMS algorithm) that greatly reduce the computational complexity and improves the convergence rate. Analysis and simulation results prove the effectiveness of our proposed adaptive algorithms.
13242297
A clustering method for web data with multi-type interrelated components
Traditional clustering algorithms work on "flat" data, making the assumption that the data instances can only be represented by a set of homogeneous and uniform features. Many real world data, however, is heterogeneous in nature, comprising of multiple types of interrelated components. We present a clustering algorithm, K-SVMeans, that integrates the well known K-Means clustering with the highly popular Support Vector Machines(SVM) in order to utilize the richness of data. Our experimental results on authorship analysis of scientific publications show that K-SVMeans achieves better clustering performance than homogeneous data clustering.