algorithm - 理解候选淘汰算法

Question

我正在尝试掌握如何手动执行候选消除算法。我知道答案，但我不知道如何到达那里的步骤。任何人都可以指导我或指出我正确的方向。这是我正在研究的问题:

Consider a concept description language with three attributes predened as follows:

attribute1      attribute2       attribute3
----------      ------------     ------------
|        |      |    |     |     |          |
a        b      c    d     e     f          g

Demonstrate version space learning using the following positive and negative training     examples:

1. ( a c f ) +)
2. ( b c f ) +)
3. ( a e g ) -)
4. ( a c g ) -)
5. ( b d f ) -)

Show how the candidate elimination algorithm changes the boundary sets after
processing each example.

这是我目前所拥有的:

1. ( a c f ) +) Generalize..
G:(???)
S:(acf)

2. ( b c f ) +) Generalize...
G:(a??), (?e?), (?d?), (??g) - Not even sure if this is correct
S:(?cf)

有人可以指导我或给我建议吗？谢谢

Answer 1

此处:http://www2.cs.uregina.ca/~dbd/cs831/notes/ml/vspace/vs_prob1.html这个网站真的很有帮助!

我为这个练习做了树，我得到的答案是 G=S= (?cf)

它是这样的:

1. >G: (？？？)小号:(acf)

2。G: (？？？)S: (?cf)

1. >G: (？？？)成为(b??),(?c?),(?d?),(??f)修剪后=(?c?),(??f)S: (?cf)

4.G: (?c?),(??f)变成 (?cf),(??f)(因为 (?c?) 不再适用于此示例)S: (?cf)

5.G: (?cf),(??f)变成 (?cf),(?cf)(因为 < ??f > 不再适用于此示例)S: (?cf)

最终答案是:G: (?cf),(?cf) = (?cf)S: (?cf)

最终的假设是(?cf)

希望这对您有所帮助。