《概念学习》PPT课件.ppt

1,第2章 概念学习和一般到特殊序,2,主要内容,概念学习简介 FIND-S算法 变型空间和候选消除算法 归纳偏置,3,概念学习简介,任务目的: 基于某天的各属性，预测EnjoySport的值,4, 概念学习问题的定义,概念学习是指从有关某个布尔函数的输入输出训练样例中推断出该布尔函数。 概念学习也可以看作是一个搜索问题的过程，它在预定义的假设空间中搜索假设，使其与训练样例有最佳的拟合度。,5,一个简单的形式，实例的各属性约束的合取式。每个约束对应一个属性可取值范围，可以为： ？ 任意本属性可接受的值 特定值 明确指定的属性值 不接受任何值, 表示假设的形式,6,概念学习任务 已知 实例集X，每个实例x由属性描述，每个属性的取值范围已确定 假设集H，每个假设h描述为各个属性的值约束的合取，约束可以为“？”，“”或一特定值 目标概念c：一个布尔函数，变量为实例 训练样例集D，目标函数（或目标概念）的正例和反例。经常可以用序偶来描述训练样例，表示其包含了实例x以及它的目标概念值c(x)。 求解 H中的一假设h，使对于X中任意x，h(x)=c(x), 术语定义,7, 归纳学习假设,归纳学习假设：任一假设如果在足够大的训练样例集中很好地逼近目标函数，它也能在未见实例中很好地逼近目标函数。 训练样例与测试样例分布一致,8, 作为搜索的概念学习,如假设采取各属性约束的合取式，对具有n个二值属性的实例集，可能的假设有？ 如果假设采取其他形式呢？,概念学习可以看作一个搜索的过程 搜索范围：假设的表示所隐含定义的整个空间 搜索目标：能够最好地拟合训练样例的假设 当假设的表示形式选定后，那么就隐含地为学习算法确定了所有假设的空间 搜索策略依赖于搜索空间的结构,9,考虑假设：h1= ， h2= 如果任何被h1划分为正例的实例都会被h2划分为正例，我们说 h2比h1更一般。,关系“更一般”的精确定义： 令hj和hk是在X上定义的布尔函数，称hj比hk更一般，当且仅当 (xX)(hk(x)=1)(hj(x)=1)， 记为hj more_general_than_or_equal_to hk，或hj ghk,假设的一般到特殊序,许多概念学习算法中，搜索假设空间的方法依赖于一种针对任何概念学习都很有效的结构：假设的一般到特殊序。,10,偏序的特点（区别于全序），全序上的搜索可以是二分法，偏序的搜索比无序简单，比全序复杂。 偏序关系的定义与目标概念无关,11,Find-S：寻找极大特殊假设,使用more_general_than偏序的搜索算法: 从H中最特殊假设开始，然后在假设覆盖正例失败时将其一般化,表2-3 Find-S算法,将h初始化为H中最特殊假设 对每个正例x 对h的每个属性约束ai 如果x满足ai 那么不做任何处理 否则将h中ai替换为x满足的另一个更一般约束 输出假设h,12,h = Encounter as positive h = Encounter as positive h = Check to ensure consistency with any negative examples: Negative: Negative: , Find-S算法实例1,13, Find-S算法实例2,14, Comments on Find-S,For conjunctive feature vectors, the most specific hypothesis that covers a set of positives is unique and found by FIND-S. If the most specific hypothesis consistent with the positives is inconsistent with a negative training example, then there is no conjunctive hypothesis consistent with the data since by definition it cannot be made any more specific and still cover all of the positives. Example: Positives: , Negatives: FIND-S - which matches negative,15,Consider the case of two unordered objects described by attributes. , What is the most-specific generalization of: Positive: , Positive: , It is not unique, could be either: , or , neither of which is more general than the other. In this case, need to maintain a continually growing set of most-specific generalizations and eliminate those that cover negative examples, or search the space of most specific generalizations for one that is consistent with the negatives., Another Hypothesis Language,16, Issues with FIND-S,Has the learner converged to the correct target concept? Is the most specific hypothesis the only hypothesis consistent with the training data? Given sufficient training examples, will FIND-S eventually converge to the correct target concept? Why prefer the most specific hypothesis? What about the most-general or other hypotheses? What if there is noise in the training data and some of the examples are labelled incorrectly? If there are multiple most-specific hypotheses, which should be chosen? If there are a combinatorially large number of most-specific hypotheses, how can a consistent one be efficiently found?,17,变型空间和候选消除算法,Find-S算法的不足，输出的假设只是H中能够拟合训练样例的多个假设中的一个；候选消除算法输出与训练样例一致的所有假设的集合 候选消除算法在描述这一集合时不需要明确列举所有成员，利用more_general_than偏序结构，可以维护一个一致假设集合的简洁表示 候选消除算法和FIND-S算法都具有容错性能差的缺点,18, 变型空间（Version Space）的定义,一个假设h与训练样例集合D一致，当且仅当 对D中每一个样例都有h(x)=c(x),关于假设空间H和训练样例集D的变型空间，记为VSH,D，是H中与训练样例D一致的所有假设构成的子集VSH,DhH|Consistent(h,D) 变型空间表示了与训练样例一致的所有假设组成的集合，目标概念的所有合理的变型,19, 变型空间表示,可以证明变型空间的确切组成是： G中包含的假设，S中包含的假设以及G和S之间偏序结构所规定的假设,在H中与D相一致的极大特殊成员的集合,在H中与D相一致的极大一般成员的集合,20,初化G和S 如果d是一个正例 从G中移去所有与d不一致的假设 对S中每个与d不一致的假设s 从S中移去s 把s的所有的极小一般化式h加入到S中，其中h满足 h与 d一致，而且G的某个成员比h更一般 从S中移去所有这样的假设：它比S中另一个假设更一般 如果d是一个反例 从S中移去所有与d不一致的假设 对G中每个与d不一致的假设g 从G中移去g 把g的所有的极小特殊化式h加入到G中，其中h满足 h与d一致，而且S的某个成员比h更特殊 从G中移去所有这样的假设：它比G中另一个假设更特殊, 候选消除学习算法,21,Procedures for minimally specializing and generalizing hypotheses will vary from one hypothesis language to the next. For conjunctive feature vectors: Minimal generalization is as in FIND-S Minimal specialization involves converting each “?” to one of the possible alternative values for this feature. g = d = , 0 minimal specializations: ,Minimum Specialization and Generalization,22,Properties of Candidate Elimination Algorithm,S summarizes the information in the positive examples relative to the hypothesis space so that the positive examples do not need to be retained explicitly. G summarizes the information in the negative examples relative to the hypothesis space so that the negative examples do not need to be retained explicitly. Result not effected by the order in which examples are processed but computational efficiency may. Positive examples move the S boundary up; Negative examples move the G boundary down. If S and G converge to the same hypotheses, then they are the only ones in the language consistent with the data. If S and G become empty (if one does the other must also), then there is no hypothesis in the language consistent with the data.,23, 候选消除学习算法实例1,24,S0:,S1:,G0, G1, G2:,S2:,训练样例： ，EnjoySport yes ，EnjoySport yes,图2-4 候选消除法步骤1, 候选消除学习算法实例2,25,S2, S3 ：, ,G2 :,G3:,训练样例： ，EnjoySport no,图2-5 候选消除法步骤2,，EnjoySport yes ，EnjoySport yes,26,S3:,S4:,G4:, ,训练样例： ，EnjoySport yes,图2-6 候选消除法步骤3, ,G3:,27, VS Traces,Example: + S= G= Example: - S= G= Example: + S= G= Example: - S= G= Did not converge S= G= ,28, VS Traces,Example: + S= G= Example: - S= G= Example: + S= NIL G= NIL Language is insufficient to describe the concept,29, Convergence Property,候选消除算法收敛到正确的假设 训练样例中没有错误 H中确实包含描述目标概念的正确假设 如果样例中存在错误，或者目标概念不能由假设表示方式所描述，给定足够的训练数据，我们会发现S和G边界收敛得到一个空的变型空间,Convergence is indicated by a single hypothesis G=S=h,30, Computational Complexity,Computing the S set for conjunctive feature vectors is linear in the number of attributes and number of examples. However, for conjunctive feature vectors, the G set can grow exponentially in the number of examples. In more expressive languages, both the S and G set can grow exponentially. The order in which examples are processed can have a significant effect on computational complexity.,31, Query Generation,Knowing the version space is useful for selecting good examples if the system is able to query an oracle for the classification of specific examples. Want an example that matches half the hypotheses in the version space so one of these halfs is eliminated if the example is positive and the other half if it is negative. After , 1, , 0 version-space is: , , , , , example matches half so is a good example to query. Given the ceiling of log2|VS|, such examples will result in convergence, if such a sequence is possible. In any case, this is the minimum number of examples needed.,32, Using Partially Learned Concepts,If the version space has not converged, then how is a novel test instance classified? If all elements of S match the instance then the entire version space must (since each element is more general than some element in S) and it can be classified as positive as confidently as in the converged case. If no element in G matches the instance then the entire version space must not match (since each element is more specific than some element in G) and it can be classified as negative as confidently as in the converged case. Otherwise, can take a vote of the hypotheses in the version space (or more tractably just the elements of S and G) to give a classification with an associated confidence value. Voting the entire version space is probabilistically optimal if one assumes that each hypothesis is equally likely a priori.,33, Learning for Multiple Categories,34, Inductive Bias,A hypothesis space that does not not include every possible binary function on the instance space incorporates a bias in the type of concepts it can learn. Any means that a concept learning system uses to choose between two functions that are both consistent with the training data is called inductive bias. Inductive bias can take two forms: Language bias: The language for representing concepts defines a hypothesis space that does not include all possible functions (e.g. conjunctive descriptions). Search bias: The language is expressive enough to represent all possible functions (e.g. disjunctive normal form) but the search algorithm embodies a preference for certain consistent functions over others (e.g. syntactic simplicity).,35, Unbiased Learning,For instances described by n attributes each with m values, there are mn instances and therefore 2mn possible binary functions. For m=2, n=10, there are 3.4 x 1038 functions, of which only 59,049 can be represented by conjunctions (a small percentage indeed!). However unbiased learning is futile since if we consider all possible functions then simply memorizing the data without any effective generalization is an option. Without bias the version space is always trivial, the unique most-specific hypothesis is a disjunction of the specific positive examples and the unique most-general hypothesis is the negation of the disjunction of the negative examples. S = G =,36, Futility of Bias-Free Learning,A learner that makes no a priori assumptions about the identity of the target concept has no rational basis for classifying any unseen instances. Inductive bias can be defined as the assumptions that when combined with the observed training data logically entail the subsequent instance classifications made by the learner. Training-data + inductive-bias | novel-classifications The inductive bias of the candidate elimination algorithm (assuming that it only agrees to classify test instances if they are classified the same by all hypotheses in the version space) is simply that the hypothesis space contains the target concept. Different learners can be more or less biased: Rote-learner Candidate-Elimination Find-S,37,归纳偏置,有关候选消除算法的几个问题 如果目标概念不在假设空间中怎么办？ 是否可设计一个包含所有假设的空间来解决这一困难？ 假设空间的大小对于算法推