XCS-SL: a rule-based genetic learning system for sequence labeling
XCS-SL: a rule-based genetic learning system for sequence labeling
复制标题
DOI：
10.1007/s12065-015-0127-9
复制
发表时间：
2015-03
影响因子：
2.6
通讯作者：
Masaya Nakata;T. Kovacs;K. Takadama
中科院分区：
文献类型：
--
作者：
Masaya Nakata;T. Kovacs;K. Takadama
序列标记是一个有趣的分类领域，与普通分类一样，每个输入都有一个类标签，但与普通分类不同的是，输入标签的预测可能取决于其他输入或其类的值，因此学习器可能需要参考不同时间戳的输入和类来对当前输入进行分类。这更加困难，因为学习者不知道需要在哪里以及需要多少输入来对当前输入进行分类。我们的兴趣是学习序列标记的一般规则。 XCS 算法是一种基于规则的知识发现系统，由遗传算法提供支持，通常用于分类。在这里，我们提出了 XCS-SL，它是 XCS 分类器系统的扩展，可适用于序列标记。针对学习分类器系统（LCS）在序列标记中的应用，我们提出了一种带有记忆的新分类器条件（称为变长条件）和用于新分类器条件的规则发现系统，这使得XCS能够将其应用于序列标记。在 XCS-SL 中，分类规则（此处称为“分类器”）可以包括先前输入的额外条件，这些条件充当存储器。在序列标记中，每个输入所需的条件/记忆的数量可能不同，因此，对所有分类器使用固定数量的条件（即固定长度的条件）并不是一个好的解决方案。相反，XCS-SL 分类器具有可变长度条件来提供更多或更少的内存。遗传算法可以增长和收缩条件来找到合适的内存大小。在两个综合基准问题上，XCS-SL 学习最佳分类器，在现实世界的序列标记任务中，它获得高分类精度，并发现有趣的知识，显示不同时间输入之间的依赖关系。全面描述的系统是 LCS 在序列标记中的首次应用，我们认为它是未来工作的一个有希望的方向。
Sequence labeling is an interesting classification domain where, like normal classification, every input has a class label, but unlike normal classification, prediction of an input’s label may depend on the values of other inputs or their classes, and so a learner may need to refer to inputs and classes at different time stamps to classify the current input. This is more difficult because a learner does not know where and how many inputs are needed to classify the current input. Our interest is in learning general rules for sequence labeling. The XCS algorithm is a rule-based knowledge discovery system powered by a genetic algorithm which has often been used for classification. Here we present XCS-SL, an extension of XCS classifier system which can be applicable to sequence labeling. Towards an application of Learning Classifier System (LCS) to sequence labeling, we propose a new classifier condition with memory (called a variable-length condition) and a rule-discovery system for the new classifier condition, which enables XCS to apply it to sequence labeling. In XCS-SL, classification rules (called “classifiers” here) can include extra conditions on previous inputs, which act as memories. In sequence labeling, the number of conditions/memories needed may be different for each input, hence, using a fixed number of conditions (i.e., fixed-length condition) for all classifiers is not a good solution. Instead, XCS-SL classifiers have a variable-length condition to provide more or less memory. The genetic algorithm can grow and shrink conditions to find a suitable memory size. On two synthetic benchmark problems XCS-SL learns optimal classifiers, and on a real-world sequence labeling task it derives high classification accuracy and discovers interesting knowledge that shows dependencies between inputs at different times. The comprehensively described system is the first application of a LCS to sequence labeling and we consider it a promising direction for future work.