Finally uploaded solution to 12.1

Master / Vertiefung Künstliche Intelligenz II
1

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

2

Finally uploaded solution to 12.1
I apologise for the delay - I finally updated https://kwarc.info/teaching/AI/assignments.pdf with the solution to the decision list problem (12.1).

3

Correct me if I’m wrong, but when we for instance look at example 7 in this task

A1 A2 A3 A4 y
0 0 1 1 1

and at the decision list provided in the solution, I don’t think the DL is correctly classifying this example.

A1 = 0, so first test returns “no”
A3 = 1 and A4 = 1, so the second test returns “no”.
A2 = 0, so the third test returns “yes”.

We get y = 0 from the DL, but in fact, it is 1.

4

Hi,
I came to the same problem when going through the algorithm.

First, we do [A1(x,1)]

this leaves you with the following list:

A2|A3|A4|y
1 0 0 1
1 1 0 0
1 0 1 0
0 1 1 1
0 1 0 0

Now we do [A3(x,1) & A4(x,0)]

This leaves us with

A2|y
1 1
1 0
0 1

I don’t see a way to split this so that we get a deterministic result.

As I looked up the solution Russel & Norvig (2nd Edition) for this task. It states :
Test If yes If no
A1 = 1 1 next test
A3 =1∧A4 =0 0 nexttest
A2=0 0 1

As I don’t have the 2nd edition but the third, I can’t look up the matrix for the task.
The fact that this task was removed in the 3rd Edition makes me think that this might not have been the correct solution though.

Hope some tutor can either prove I am wrong or verify my(our) result.

Thanks in advance.

5

Disclaimer: I’m not a TA.

I think if you check [A3(x,1) & A4(x,0)], you cannot throw away the whole attributes (columns) A3 and A4, but instead you have to throw away the examples in which A3 = 1 and A4 = 0.

In the first check (A1 = 1?) we can throw away the whole attribute since we know for all remaining examples, that A1 = 0 anyway, so we don’t need to look at A1 anymore.

I tried it again myself:

First check:
A1 = 1?
If yes: 1
If no: second check with all remaining examples (i.e. all examples in which A1 = 1 is false)

Second check:
A3 = 1 and A4 = 0? (<-- this test is chosen because it classifies 2 examples at once, this is not the case for any other check I think)
If yes: 0
If no: third check with all remaining examples (i.e. all examples in which A1 = 1 is false and (A3 = 1 and A4 = 0) is false)

Third check:
A2 = 0?
If yes: 1
If no: Fourth check with all remaining examples (i.e. all examples in which A1 = 1 is false and (A3 = 1 and A4 = 0) is false and A2 = 0 is false)

Fourth check:
A4 = 0?
If yes: 1
If no: 0

6

The solution of the assignment is definitly not correct!

@sonnenblume your solution is one of them that works…

Mine would be:
A1=1 => 1 else next test
A3=1 & A4=0 => 0 else next test
A3=0 & A4=1 => 0 else 1

You don‘t even need A2.

7

Wouldn’t this work too? Then we would only have two tests:
A1 = 1 => 1 else next test
A3 != A4 => 0 else 1

8

yep… didn’t see this yesterday evening :smiley: