Maximum margin classifier working in a set of strings

Numbers and numerical vectors account for a large portion of data. However, recently, the amount of string data generated has increased dramatically. Consequently, classifying string data is a common problem in many fields. The most widely used approach to this problem is to convert strings into numerical vectors using string kernels and subsequently apply a support vector machine that works in a numerical vector space. However, this non-one-to-one conversion involves a loss of information and makes it impossible to evaluate, using probability theory, the generalization error of a learning machine, considering that the given data to train and test the machine are strings generated according to probability laws. In this study, we approach this classification problem by constructing a classifier that works in a set of strings. To evaluate the generalization error of such a classifier theoretically, probability theory for strings is required. Therefore, we first extend a limit theorem for a consensus sequence of strings demonstrated by one of the authors and co-workers in a previous study. Using the obtained result, we then demonstrate that our learning machine classifies strings in an asymptotically optimal manner. Furthermore, we demonstrate the usefulness of our machine in practical data analysis by applying it to predicting protein–protein interactions using amino acid sequences and classifying RNAs by the secondary structure using nucleotide sequences.

数字和数值向量在数据中占很大一部分。然而，最近生成的字符串数据量急剧增加。因此，对字符串数据进行分类是许多领域中的一个常见问题。解决这个问题最广泛使用的方法是使用字符串核将字符串转换为数值向量，然后应用在数值向量空间中工作的支持向量机。然而，这种非一一对应的转换会导致信息丢失，并且考虑到用于训练和测试机器的给定数据是根据概率法则生成的字符串，无法使用概率论来评估学习机的泛化误差。在本研究中，我们通过构建一个在字符串集合中工作的分类器来处理这个分类问题。为了从理论上评估这种分类器的泛化误差，需要字符串的概率论。因此，我们首先扩展了其中一位作者及其同事在先前研究中证明的字符串共有序列的极限定理。利用所得到的结果，我们接着证明我们的学习机以渐近最优的方式对字符串进行分类。此外，我们通过将其应用于使用氨基酸序列预测蛋白质 - 蛋白质相互作用以及使用核苷酸序列根据二级结构对RNA进行分类，证明了我们的机器在实际数据分析中的实用性。