候选消除算法

Question

候选消除算法

36

考虑以下训练数据集...

+-------+-------+----------+-------------+
| Size  | Color | Shape    | Class/Label |
+=======+=======+==========+=============+
| big   | red   | circle   | No          |
| small | red   | triangle | No          |
| small | red   | circle   | Yes         |
| big   | blue  | circle   | No          |
| small | blue  | circle   | Yes         |
+-------+-------+----------+-------------+

我希望了解算法在以负例为起点和两个负例汇聚时的运作方式。

顺便说一句，这不是作业问题。

欢迎使用其他数据集的例子！这是为了了解算法中负面部分的内容。

- Ravi

训练集包含3个属性，最后一个是分类数据，表示为+ve或-ve。您能解释一下每个训练数据被考虑时G、S集如何扩展吗？@YvesDaoust - Ravi

2

@SeanOwen 实际上，“是”和“否”确实有一些特殊之处。一个“是”的标签会导致特定假设的概括，而“否”则导致一般假设的专业化。 - bogatron

1

@bogatron，你能解释一下为什么最小特化是 <?, ?, triangle> 而不是 <?,?,circle> 吗？ - sheldon cooper

1

为什么不将G1定义为{<big, ? , ?>, <?, red, ?>, <?, ?, triangle>}，而是{<small, ? , ?>, <?, blue, ?>, <?, ?, triangle>}？ - sheldon cooper

1

@Tim，“G”假设是最一般的假设。<?, blue, ?>在G1中，因为蓝色的对象（无论形状或大小）仍然在假设空间中（它们没有被负例排除）。 - bogatron

显示剩余7条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- bogatron · Accepted Answer

对于您的假设空间（H），您从最大一般性（G）和最大特殊性（S）假设集开始：

G0 = {<?, ?, ?>}
S0 = {<0, 0, 0>}

当您面对负面例子时，您需要从S中删除与当前观察不一致的任何假设，并用其最小专业化替换G中任何不一致的假设。这些假设与观察一致，但仍比S中的某些成员更普遍。

因此，对于您的第一个（负面）示例（big，red，circle），最小的特化将使新的假设空间变为：

G1 = {<small, ? , ?>, <?, blue, ?>, <?, ?, triangle>}
S1 = S0 = {<0, 0, 0>}

请注意，S没有改变。对于您的下一个示例(small, red, triangle)，它也是负面的，您需要进一步专门化G。请注意，G1中的第二个假设与新观察结果不匹配，因此只需要进一步专门化G1中的第一个和第三个假设。这将产生

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

然而，由于G2中的第一个和最后一个假设是中间假设（<?, blue, ?>）的细化版本，因此我们删除这两个假设，得到

G2 = {<small, ?, circle>, <?, blue, ?>, <big, ?, triangle>}
S2 = S1 = S0 = {<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

G3 = {<small, ?, circle>}
S3 = {<small, red, circle>}

(大的、蓝色的、圆形的) 是下一个负例。但由于它与 G 不一致，因此无可奈何。

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

最后，你有一个正面的例子：(small, blue, circle)，这要求你推广S以使其与示例一致，得到

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

因为 G 和 S 相等，所以你已经学会了“小圆圈”的概念。