Slide2-归类公理.ppt

归类公理 于剑交通数据分析与挖掘北京市重点实验室北京交通大学Email jianyu 1 一对情侣在山东省济南市经十东路附近游玩 小伙子凝视着一个高大建筑的大门 感叹书法写的不错 并大声念道 心在情妇那 女孩子说 你个大傻 明明是山东情妇馆 贪官的情妇都关在这里 一路人经过这里 心想 两个不学无术的东西 不认得还在这里充学问 明明是心系情妇波 这时走过来一个看起来很斯文的学者说 都别争了 这不是很清楚吗 这是 山东情妇报 办公大楼 2 提要 1 引言2 类表示与类表示公理3 归类公理 3 1 引言 人接触世界 会将各种对象自动呈现为心智中的各种概念 即人具有归类能力 自然希望计算机也具有这种能力 为此 机器学习作为一门学科应运而生 一个六七岁的小孩可以正确归类各种对象 4 人如何归类 直观观察 每个对象应该归为与其最相似的类 更简单的归纳为 归哪类 像哪类 像哪类 归哪类 5 2 类表示与类表示公理 人是机器人的上帝 人至少机器人制造者必须知道机器人的思考机理 人的归类机理是归哪类 像哪类 像哪类 归哪类 本书所有的研究内容围绕这四句话展开 6 归哪类 像哪类的语义分析 归哪类对外可见 是类的外显表示 像哪类主观内在 不一定外显 属于类的内部表示 人表示类 既有外显表示 也由内部表示 机器如何表示类 应该也像人一样 有类的内部表示和外显表示 7 归类问题的挑战 只给予概念的外延子集 希望得到概念的内涵表示 8 归类 Categorization 数据表示归类判据归类算法 9 数据表示 外显归类表示 外显归类输入 外显归类输出 10 外显归类输入 抽样对象的特性表示 11 外显归类输入 输入类外显表示 每个对象的归类情况由划分矩阵表示划分矩阵 硬划分 软划分 模糊划分 概率划分可能性划分 12 外显归类输出 抽样对象的特性表示 13 外显归类输出 输出类外显表示 每个对象的归类情况由划分矩阵表示划分矩阵 硬划分 软划分 模糊划分 概率划分 14 归类算法的外显表示 外显归类输入与输出 15 内部表示 类的认知表示 主观内在 经典理论 亚里士多德 类有一个命题表示原型理论 Rosch 1978 类有一个原型表示样例理论 Medin Schaffer 1978 类有多个样本表示知识理论 Murphy Medin 1985 类是一个知识框架的组成部分 16 指派算子 归 assignmentoperator 17 抽样输入的类相似性映射 类的认知表示也具有归类能力 可以根据与类的相似度将对象归类 18 抽样输出的类相似性映射 类的认知表示也具有归类能力 可以根据与类的相似度将对象归类 19 类表示存在公理 ExistenceAxiomofCategoryRepresentation 如果一个归类算法的归类外显输入输出给定 则其对应的类内部表示存在 20 类内在表示 21 相似算子 像 similarityoperator 22 归类输入 23 归类结果 24 白箱算法与黑箱算法 IfY被归类算法显式输出 则算法称为白箱算法 在白箱算法中 Y对于使用者和设计者都是可见的 IfY不被归类算法显式输出 则算法称为黑箱算法 在黑箱算法中 Y对于使用者是不可见的 但对于设计者可见 25 类表示唯一公理 UniquenessAxiomofCategoryRepresentation 对一个归类算法 其输入输出对应的类表示 语义 应该相同 26 类表示唯一公理的讨论 如果归类输入输出相同 其类表示唯一公理当然成立如果归类输入输出的的特征描述不同时 类表示唯一公理是学习算法能够成功学习的先验假设 27 类相似性与归类 丑小鸭定理 UglyducklingTheorem 如果特征选取不合适 丑小鸭与白天鹅之间的相似性与白天鹅之间的相似性是一样的 SatosiWatanable 1969 28 类相似性映射是任务依赖的 主观的 CitedfromEamonnKeogh clusteringtutortial UniversityofCalifornia Riverside 29 类相似性映射设计中的挑战性问题 相似性悖论 输入类相似性映射与输出类相似性映射在归类意义下不等价 在图像检索中经常发生此类情形 30 3 归类公理 无论看到什么 人们都能自动将其归类 归类包括回归 分类 聚类和特征降维 31 样本可分性公理 SS 不重 一个对象总有唯一一个类与其最相似 32 类内非空 一个类至少有一个对象与其最相似 类可分性公理 CS 33 归类等价公理 CE 归类等价 对于任意一个类 其对应的算法内部表示与外显表示的归类能力等价 直心是道场 知行合一 34 类相异函数描述下的归类公理 35 归类公理讨论 SS任何对象属于且仅属于一个类 CS任意一个类非空 CE内外一致 外延表示与主观表示一致 36 类可分性公理的性质 定理1 如果一个归类结果有c个类 并满足类可分性公理 则有1 每个类的表示都不同 2 至少存在c个不同的对象 37 样本可分性公理与归类理论 原型理论 一个对象归为A类而不是其它类仅仅因为该对象更像A类的原型表示而不是其它类的原型表示样例理论 一个对象归为A类而不是其它类仅仅因为该对象更像A类的样例表示而不是其它类的样例表示 上述归类理论与样本可分性公理一致 38 归类结果分类 正则归类结果重叠归类结果非正则归类结果 39 正则归类结果 正则归类结果 如果一个归类结果满足样本可分性公理和类可分性公理 则该归类结果是正则的 40 重叠归类结果 重叠归类结果 如果一个归类结果满足类可分性公理但不满足样本可分性公理 则该归类结果是重叠归类结果 41 非正则归类结果 非正则归类结果 如果一个归类结果不满足类可分性公理 则该归类结果是非正则归类结果 42 正则划分 43 重叠划分 44 非正则划分 45 边界集 46 归类判据设计原则 可分性公理要求低 归类结果应该尽量远离违反可分性公理的情形 由此 有两个设计原则类紧致性原则类分离性原则类表示唯一公理要求高 因此 归类结果应该尽量使得类表示唯一公理近似成立 由此 有设计原则 归类一致性原则 47 类紧致性原则 类紧致性原则 每个对象的最相似类与其次相似类的相似程度差别要大 48 类紧致性原则 类内相似度最大类内方差最小 49 类分离性准则 50 类一致性准则 51 总结与展望 1 提出了归类的基本规则 归哪类 像哪类 像哪类 归哪类 建立了从认知科学到机器学习或者模式识别的理论桥梁 2 将归类结果进行了分类 3 提出了三条归类设计准则 52 归类公理框架图 PAC 归类公理 样本可分 类可分 归类等价 类表示公理 存在性 唯一性 类紧致性 类分离性 类一致性 归类方法设计 53 参考文献 YuJ XuZ CategorizationAxiom J arXivpreprintarXiv 14