概念学习课件

1、概念学习PPT课件1第2章 概念学习和一般到特殊序概念学习PPT课件2主要内容概念学习简介FIND-S算法变型空间和候选消除算法归纳偏置概念学习PPT课件3概念学习简介YesChangeCoolStrongHighWarmSunny4NoChangeWarmStrongHighColdRainy3YesSameWarmStrongHighWarmSunny2YesSameWarmStrongNormalWarmSunny1EnjoySportForecastWaterWindHumidityAirTempSkyExample表2-1 目标概念EnjoySport的训练样例任务目的: 基于某天的

2、各属性，预测EnjoySport的值概念学习PPT课件4 概念学习问题的定义概念学习是指从有关某个布尔函数的输入输出概念学习是指从有关某个布尔函数的输入输出训练样例中推断出该布尔函数。训练样例中推断出该布尔函数。概念学习也可以看作是一个搜索问题的过程，概念学习也可以看作是一个搜索问题的过程，它在预定义的假设空间中搜索假设，使其与训它在预定义的假设空间中搜索假设，使其与训练样例有最佳的拟合度。练样例有最佳的拟合度。概念学习PPT课件5一个简单的形式，一个简单的形式，实例的各属性约束的合取式。实例的各属性约束的合取式。每个约束对每个约束对应一个属性可取值范围，可以为：应一个属性可取值范围，可以为：

3、 ？ 任意本属性可接受的值 特定值 明确指定的属性值 不接受任何值 表示假设的形式概念学习PPT课件6 概念学习任务已知实例集X，每个实例x由属性描述，每个属性的取值范围已确定假设集H，每个假设h描述为各个属性的值约束的合取，约束可以为“？”，“”或一特定值目标概念c：一个布尔函数，变量为实例训练样例集D，目标函数（或目标概念）的正例和反例。经常可以用序偶来描述训练样例，表示其包含了实例x以及它的目标概念值c(x)。求解H中的一假设h，使对于X中任意x，h(x)=c(x) 术语定义概念学习PPT课件7 归纳学习假设归纳学习假设：任一假设如果在足够大的训练样例集中很好地逼近目标函数，它也能在未见

4、实例中很好地逼近目标函数。训练样例与测试样例分布一致概念学习PPT课件8 作为搜索的概念学习如假设采取各属性约束的合取式，对具有n个二值属性的实例集，可能的假设有？如果假设采取其他形式呢？概念学习可以看作一个搜索的过程搜索范围：假设的表示所隐含定义的整个空间搜索目标：能够最好地拟合训练样例的假设当假设的表示形式选定后，那么就隐含地为学习算法确定了所有假设的空间搜索策略依赖于搜索空间的结构概念学习PPT课件9考虑假设：h1= ， h2=如果任何被h1划分为正例的实例都会被h2划分为正例，我们说h2比h1更一般。关系“更一般”的精确定义：令hj和hk是在X上定义的布尔函数，称hj比hk更一般，当且

5、仅当(xX)(hk(x)=1)(hj(x)=1)，记为hj more_general_than_or_equal_to hk，或hj ghk假设的一般到特殊序许多概念学习算法中，搜索假设空间的方法依赖于一种针对任何概念学习都很有效的结构：假设的一般到特殊序。概念学习PPT课件10偏序的特点（区别于全序），全序上的搜索可以是二分法，偏序的搜索比无序简单，比全序复杂。偏序关系的定义与目标概念无关概念学习PPT课件11Find-S：寻找极大特殊假设使用more_general_than偏序的搜索算法: 从H中最特殊假设开始，然后在假设覆盖正例失败时将其一般化表2-3 Find-S算法将h初始化为H中

6、最特殊假设对每个正例x对h的每个属性约束ai如果x满足ai那么不做任何处理否则将h中ai替换为x满足的另一个更一般约束输出假设h概念学习PPT课件12Example Size Color Shape Class 1 small red circle positive 2 big red circle positive 3 small red triangle negative 4 big blue circle negativeh = Encounter as positive h = Encounter as positive h = Check to ensure consistency

7、with any negative examples: Negative: Negative: Find-S算法实例1概念学习PPT课件13 Find-S算法实例2概念学习PPT课件14 Comments on Find-SFor 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

8、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概念学习PPT课件15Consider the case of

9、 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 a

10、nd 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概念学习PPT课件16 Issues with FIND-SHas the learner converged to the correct target concept? Is the most specific hypothesis the o

11、nly 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 exa

12、mples 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?概念学习PPT课件17变型空间和候选消除算法v Find-S算法的不足，输出的假设只是H中能够拟合训练样例的多个假设中的一个；候选消除算法输出与训练样例一致

13、的所有假设的集合v 候选消除算法在描述这一集合时不需要明确列举所有成员，利用more_general_than偏序结构，可以维护一个一致假设集合的简洁表示v 候选消除算法和FIND-S算法都具有容错性能差的缺点概念学习PPT课件18 变型空间（Version Space）的定义一个假设h与训练样例集合D一致，当且仅当对D中每一个样例都有h(x)=c(x)关于假设空间H和训练样例集D的变型空间，记为VSH,D，是H中与训练样例D一致的所有假设构成的子集VSH,DhH|Consistent(h,D)变型空间表示了与训练样例一致的所有假设组成的集合，目标概念的所有合理的变型概念学习PPT课件19 变

14、型空间表示可以证明变型空间的确切组成是：G中包含的假设，S中包含的假设以及G和S之间偏序结构所规定的假设在H中与D相一致的极大特殊成员的集合在H中与D相一致的极大一般成员的集合概念学习PPT课件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的某个成员

15、比h更特殊从G中移去所有这样的假设：它比G中另一个假设更特殊 候选消除学习算法概念学习PPT课件21Procedures 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-SMinimal specialization involves converting each “?” to one of t

16、he possible alternative values for this feature. g = d = , 0 minimal specializations: Minimum Specialization and Generalization概念学习PPT课件22Properties of Candidate Elimination AlgorithmS summarizes the information in the positive examples relative to the hypothesis space so that the positive examples

17、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

18、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 consiste

19、nt with the data.概念学习PPT课件23 候选消除学习算法实例1概念学习PPT课件24S0:S1:G0, G1, G2:S2:训练样例：，EnjoySport yes1.，EnjoySport yes图图2-4 2-4 候选消除法步骤候选消除法步骤1 1 候选消除学习算法实例2概念学习PPT课件25S2, S3 ： G2 :G3:训练样例：3.，EnjoySport no图图2-5 2-5 候选消除法步骤候选消除法步骤2 2，EnjoySport yes，EnjoySport yes概念学习PPT课件26S3:S4:G4: 训练样例：4.，EnjoySport yes图图2-6

20、 2-6 候选消除法步骤候选消除法步骤3 3 G3:概念学习PPT课件27 VS TracesExample: + S= G= Example: - S= G= Example: + S= G= Example: - S= G= Did not converge S= G= 概念学习PPT课件28 VS TracesExample: + S= G= Example: - S= G= Example: + S= NIL G= NILLanguage is insufficient to describe the concept概念学习PPT课件29 Convergence Property候选消

21、除算法收敛到正确的假设训练样例中没有错误H中确实包含描述目标概念的正确假设如果样例中存在错误，或者目标概念不能由假设表示方式所描述，给定足够的训练数据，我们会发现S和G边界收敛得到一个空的变型空间Convergence is indicated by a single hypothesis G=S=h概念学习PPT课件30 Computational ComplexityComputing the S set for conjunctive feature vectors is linear in the number of attributes and number of examples.

22、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.概念学习PPT课件31 Query Generat

23、ionKnowing 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 h

24、alf 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.概念学习PPT课件32 Using P

25、artially Learned ConceptsIf 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

26、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 ver

27、sion 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.概念学习PPT课件33 Learning for Multiple Categories概念学习PPT课件3

28、4 Inductive BiasA 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

29、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.

30、g. disjunctive normal form) but the search algorithm embodies a preference for certain consistent functions over others (e.g. syntactic simplicity).概念学习PPT课件35 Unbiased LearningFor instances described by n attributes each with m values, there are mn instances and therefore 2mn possible binary functi

31、ons. 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.W

32、ithout 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 =概念学习PPT课件36 Futility of Bias-Free LearningA learner that

33、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 l

34、earner. Training-data + inductive-bias | novel-classificationsThe 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概念学习PPT课件37归纳偏置有关候选消除算法的几个问题如