编码矩阵是什么？纠错输出码中规定如何拆分类别的表格

编码矩阵（Coding Matrix）是纠错输出码方法中用来规定如何把多分类问题拆分成多个二分类问题的一张表格。它决定了要训练哪些二分类器，以及每个类别对应什么样的编码。

它的结构

编码矩阵的每一行对应一个类别，这一行的内容就是该类别的“码字”；每一列对应一个二分类器，这一列规定了在训练这个分类器时，哪些类别作为正类，哪些作为负类。比如有四个类别、五个分类器，编码矩阵就是四行五列。第一列可能规定类别 1 和类别 3 为正类、类别 2 和类别 4 为负类，于是用这种划分训练第一个分类器；第二列再规定另一种划分，以此类推。

二元码与三元码

二元编码矩阵中，每个元素只有两种取值，通常记为 +1 和 −1，表示该类别在这个分类器中是正类还是负类，每个分类器都会用到所有类别的样本。三元编码矩阵由 Erin Allwein、Robert Schapire 和 Yoram Singer 在 2000 年提出，增加了第三种取值 0，表示这个类别不参与该分类器的训练。三元码让编码更加灵活：常见的“一对一”拆分在三元码中就可以直接表示，每一列只有两个类别分别是 +1 和 −1，其余都是 0；而“一对其余”则对应每列只有一个 +1、其余都是 −1 的编码矩阵。

解码

预测时，让所有分类器对新样本给出判断，得到一个预测编码，再与编码矩阵中每一行的码字比较，选择距离最近的类别。常用的距离有海明距离（统计不同的位数）和欧氏距离；使用三元码时，值为 0 的位置通常不计入距离。如果分类器输出的是连续的分数而不只是正负，还可以使用基于损失的解码，效果往往更好。

什么样的编码矩阵是好的

行与行之间的距离要大：不同类别的码字差别越大，即使有几个分类器判断错了，预测编码仍然离正确类别最近，纠错能力越强。在海明距离意义下，如果任意两行之间至少相差 d 位，就能纠正大约 d 的一半以内的错误。列与列之间的差异也要大：如果两列几乎相同，或者一列正好是另一列取反，对应的两个分类器其实在做同一件事，犯的错误也相同，失去了冗余纠错的意义。每一列不能全是同一个值，否则无法训练分类器。此外，列的划分方式还要让二分类问题容易学习：把本来就很相似的类别分到两边，分类器会很难学好，错误率上升会抵消纠错的好处。

如何构造

对于类别不多的情况，可以穷举所有可能的列；类别较多时，常用随机生成大量候选矩阵、再挑选行间距离最大的那一个；也可以根据数据的特点，比如类别之间的混淆程度，设计数据相关的编码矩阵。码字越长，纠错能力越强，但需要训练的分类器越多，计算开销越大，需要权衡。