2.1　类表示公理

那么什么是归类问题呢？简单地说，归类问题就是这样一个问题：当已经知道一个概念（或者概念集）的有限外延子集，如何计算其对应的概念（或者概念集）表示？归类算法就是解决归类问题的算法。显然，归类算法都有输入和输出，归类输入体现了人们希望算法学到的类信息，归类输出反映了算法实际学到的类信息，因此都应该对应着各自的类表示。根据上一节的分析，类表示有外部表示和内蕴表示。故归类输入有内蕴表示和外部表示，归类输出也有内蕴表示和外部表示。我们首先讨论归类输入。

归类输入的外部表示由一个有限抽样对象集合O=｛o1，o2，…，oN｝的归类输入外部信息组成，包括对象的特性输入表示和对应的类外延表示。对象特性输入表示X=｛x1，x2，…，xN｝归为c个子集｛X1，X2，…，Xc｝，其中xk代表对象ok的特性输入，Xi是X中属于第i输入类的对象子集，其对应的归类输入的类外延表示由划分矩阵U=［uik］c×N表示，其中uik表示对象ok属于第i个输入类的隶属度，uik≥0。U有时也称为隶属矩阵。不同的划分约束，产生不同的划分矩阵，3种典型的划分矩阵如下：

•　硬划分：;

•　软划分;

•　可能性划分。

因此，归类输入的外部表示可以表示为（X，U）。当U已知，一个对象总是被指派到具有最大隶属度的类中，由此可以定义指派算子→如下：=，其中，

可以读作xk外部指称为第类，也可以读作对象ok在归类输入端被外部指称为第类。

归类输出的外部表示可以表示为（Y，V），其中对象特性输出表示Y=｛y1，y2，…，yN｝归为c个子集｛Y1，Y2，…，Yc｝，其中yk代表对象ok的特性输出，Yi是Y中属于第i输出类的对象子集，其对应的归类输出的类外延表示由划分矩阵V=［vik］c×N表示，其中vik表示对象ok对第i个输出类的隶属度。当V已知，一个对象也总是被指派到具有最大隶属度的类中，由此可以定义指派算子→如下：，其中，可以读作yk外部指称为第类，也可以读作对象ok在归类输出端被外部指称为第类。指派算子→明确定义了什么是归。

根据输出划分矩阵的类型，归类方法可分为硬归类方法和软归类方法，硬归类方法的输出划分矩阵为硬划分矩阵，软归类方法的输出划分矩阵为软划分矩阵或可能性划分矩阵。在硬归类方法中，一个对象只属于一个类，划分矩阵直接说明了各个对象属于哪一类。只有该对象明确属于该类时，其对应的元素为1；如该对象不属于该类，其对应的元素为0。在软归类方法中，划分矩阵说明了各个对象属于各类的可能性，对象的具体归类由指派算子决定。显然，指派算子是归类对象的外显指称，表现了对象与类之间的外显对应关系。

假设∀i，第i类的输入认知表示为，第i类的输出认知表示为。正如前面分析，类的认知表示也有归类能力。当类的认知表示已知时，一般是对象像哪类便归哪类。因此，需要定义类与对象的相似度。考虑到输出输入表示不一定相同，下面分别定义输入类相似性映射和输出类相似性映射。

输入类相似性映射：

是输入类相似性映射，满足条件：函数值增加表示xk和相似性增大，函数值减少表示xk和的相似性减少。

输出类相似性映射：

是输出类相似性映射，满足条件：函数值增加表示yk和相似性增大，函数值减少表示yk和的相似性减少。

知道了输入类相似性映射，同样可以根据相似度将对象进行归类，其原则也非常简单，对象ok的特性输入xk与哪个输入类的认知表示最相似，即归为哪一类。由此定义相似算子～如下：，其中，。可以读作xk内蕴指称为第类，也可以读作对象ok在归类输入端被内蕴指称为第类。

同样，知道了输出类相似性映射，同样可以根据相似度将对象进行归类，即对象ok的特性输出yk与哪个输出类的认知表示最相似，就归为哪一类。由此定义相似算子～如下：，其中，可以读作yk内蕴指称为第类，也可以读作对象ok在归类输出端被内蕴指称为第类。相似算子～明确定义了什么是像。

理论上，如果单值，值越大，SimY越好。类似地，单值，值越大，SimX越好。

类似地，可以定义输入类相异性映射和输出类相异性映射。

输入类相异性映射：

是类相异性映射，满足条件：函数值增加表示xk和相似性减少，函数值减少表示xk和的相似性增加。

输出类相异性映射：

是类相异性映射，满足条件：函数值增加表示yk和相似性减少，函数值减少表示yk和的相似性增加。

输入类相异性映射同样可以将对象进行归类，其原则也非常简单，对象ok的特性输入xk与哪个输入类的认知表示相异度最小，即归为哪一类。由此定义相似算子～如下：，其中，。同样，知道了输出类相异性映射，同样可以根据相似度将对象进行归类，即对象ok的特性输出yk与哪个输出类的认知表示相异度最小，就归为哪一类。由此定义相似算子～如下：，其中，。理论上，如果单值，值越小，DsY越好。类似地，单值，值越小，DsX越好。相似算子是归类对象的内在指称，以内蕴的方式反映了客观对象与认知类表示之间的潜在对应关系。

根据以上分析，如果归类输入的外部表示为（X，U），则其对应的归类输入内部表示为或者，其中。简单地说，可称或为归类输入，（X，U）为外显输入，或为内在输入。同样地，归类输出的外部表示为（Y，V），则其对应的归类输出内部表示为或者，其中。简单地说，可称或为归类输出，（Y，V）为外显输出，或为内在输出。显然归类输出即归类结果。今后，如果不特别指出，我们将不区分归类输出与归类结果。

理论上，对任意一个归类算法而言，其外显输入和外显输出一定存在对应的内在输入和内在输出。只有在这种假设下，我们才能说归类算法确实学习到了概念。这个假设，我们称之为类表示存在公理。

类表示存在公理：

对一个归类算法，如果其外显输入为（X，U），其外显输出为（Y，V），则一定存在对应的内在输入和内在输出。

更进一步，对一个归类算法，我们通常期望其对于一个对象的输入表示、输出表示有相同的类指称。更加明确地说，由于内在输入和其对应的内在输出描述的是同一组外在对象，因此一个对象类的输入输出内蕴指称应该相同，故必有，这里被定义为。由于外显输入（X，U）和其对应的外显输出（Y，V）描述的是同一组外在对象，因此任一个对象其类的输入输出外部指称也应该相同，故必有，这里被定义为。同理。这样的一个假设，我们称之为类表示唯一性公理。其形式化表示如下。

类表示唯一公理：

对一个归类算法，如果其输入为，其输出为则

注意到，特性输入xk与其对应的特性输出yk都表示对象ok。更一般地，设特性输入x与其对应的特性输出y都表示同一对象o，则可以假设存在从x～y的一个映射θ，使得y=θ（x）。如果，则有。因此，如果类表示唯一公理成立，可以被定义。如果可以被定义，则必然保证。更进一步，如果X=Y，则易知此时θ为恒同映射，前面的分析说明。

类表示存在公理和类表示唯一公理统称为类表示公理。是期望学到的，是实际学到的。通常，所在的空间称为对应学习算法的目标空间，所在的空间称为对应学习算法的假设空间。类表示唯一公理给出了学习完全成功的条件：输入输出应该具有相同的类表示语义。在机器学习中，学习算法的一个基本假设是要求目标空间与假设空间的交集至少不为空集，这实际上是类表示唯一公理的一个弱化描述。而一个理想的学习算法，信息输入者的归类信息应该与算法学到的归类信息在归类意义下相同。需要注意的是，在学习过程中，虽然假设和同时存在，但二者通常不能被学习算法同时得到。

尤其有趣的是，类表示公理也是人们日常生活正确对话的必要条件。否则，如果两个人的对话对同一个对象归类不一致，就会变成“鸡同鸭讲”，轻则闹笑话，重则严重误事，甚至危及自身。