候选消除算法 [英] Candidate Elimination Algorithm

问题描述

考虑下面的训练数据集。

Consider the following training data sets..

big,   red,  circle,   No  
small, red,  triangle, No  
small, red,  circle,   Yes  
big,   blue, circle,   No  
small, blue, circle    Yes  

我想了解的算法是如何进行时，它开始于一个反面的例子，当两个负例子走到了一起。

I would like to understand how the algorithm proceeds when it starts with a negative example and when two negative examples come together.

这是在路上没有一个分配的问题。

This is not an assignment question by the way.

与其他数据集的例子也欢迎！这是了解该算法的负部分

Examples with other data sets are also welcome! This is to understand the negative part of the algorithm.

推荐答案

有关你的假设空间（H），你开始你的套极大一般的（G）和最大特定的（S）的假设：

For your hypothesis space (H), you start with your sets of maximally general (G) and maximally specific (S) hypotheses:

G1 = {<?, ?, ?>}
S1 = {<0, 0, 0>}

当你psented有一个反面的例子$ P $，你需要从s删除与当前的观测值不符的假设，并取代G中任何不一致的假设，其最小的专业与该观察结果一致，但仍超过一般的S一些成员。

When you are presented with a negative example, you need to remove from S any hypothesis inconsistent with the current observation and replace any inconsistent hypothesis in G with its minimal specializations that are consistent with the observation but still more general than some member of S.

因此​​，对于你的第一个（负）例如，（又大又红，圈内），最小的专业化将使新的假设空间

So for your first (negative) example, (big, red, circle), the minimal specializations would make the new hypothesis space

G2 = {<small, ? , ?>, <?, blue, ?>, <?, ?, triangle>}
S2 = S1 = {<0, 0, 0>}

请注意使得S没有变化。为了您的下一个例子，（小型，红色，三角形），这也是负的，则需要进一步的专门G.注意，在G2的第二个假设不符新的观察所以只在第一和第三的是G2假设需要进行专门的。这将产生

Note that S did not change. For your next example, (small, red, triangle), which is also negative, you will need to further specialize G. Note that the second hypothesis in G2 does not match the new observation so only the first and third hypotheses in G2 need to be specialized. That would yield

G3 = {<small, blue, ?>, <small, ? circle>, <?, blue, ?>, <big, ?, triangle>, <?, blue, triangle>}

但是，由于G3的第一个和最后一个假设之上的中间假设专业（＆LT;？，蓝，＆GT; ），我们放弃这两个，让

However, since the first and last hypotheses in G3 above are specializations of the middle hypothesis (<?, blue, ?>), we drop those two, giving

G3 = {<small, ? circle>, <?, blue, ?>, <big, ?, triangle>}
S3 = {<0, 0, 0>}

对于正（小型，红色，圆）的观察，你必须概括S和删除任何东西在G中是不一致的，这给

For the positive (small, red, circle) observation, you must generalize S and remove anything in G that is inconsistent, which gives

G4 = {<small, ?, circle>}
S4 = {<small, red, circle>}

（大，蓝色圆圈）是下一个反面教材。但是，由于它不以G一致，没有什么可以做

(big, blue, circle) is the next negative example. But since it in not consistent with G, there is nothing to do so

G5 = G4 = {<small, ?, circle>}
S5 = S4 = {<small, red, circle>}

最后，你的正面例子（小蓝，圈子），这就需要你来概括S键使之与一致。例如，给

Lastly, you have the positive example of (small, blue, circle), which requires you to generalize S to make it consistent with the example, giving

G5 = {<small, ?, circle>}
S5 = {<small, ?, circle>}

由于g和S是平等的，你已经学会了小圈的概念。

Since G and S are equal, you have learned the concept of "small circles".

这篇关于候选消除算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！