Confused on question 6.

[zhou_jinyuan]

I just started. Not sure if forum is closed or not. I have confusion too. As I understand hypothesis set is associated with a learning algorithm. does g in choice from a to d come from same learning algorithm or description represents different algorithm? Since we have 256 possible hypothesis, I can conceptually call my learning algorithm "try all" which have all 256 possible functions as its hypothesis. Does this exercise assume we are working with "try all" algorithm?.
Thanks,

[yaser]

Originally Posted by zhou_jinyuan

I have confusion too. As I understand hypothesis set is associated with a learning algorithm. does g in choice from a to d come from same learning algorithm or description represents different algorithm? Since we have 256 possible hypothesis, I can conceptually call my learning algorithm "try all" which have all 256 possible functions as its hypothesis. Does this exercise assume we are working with "try all" algorithm?

A hypothesis set is just that; a set of hypotheses. The algorithm is a separate entity that chooses the final hypothesis from this set. It can in principle make that choice any way it wants (some algorithms may be better than others for the same hypothesis set).

To answer your question, the algorithm can try all hypotheses (in the hypothesis set), but it will have to choose one and only one as the final hypothesis that it reports. When we grade the algorithm, what matters is the performance of the final hypothesis it arrived at, regardless of how it arrived at it.

[royal]

It's taking me a while to get my head around whats going on in this question and how I am supposed to calculate the scores.

For a) , the hypothesis g returns 1 for all three points. So does this mean that for each of the points 101,110 and 111 as x_n, then y_n is 1 ?

If so then I am not sure what I am then supposed to compare this to?

Thanks for any help.

[yaser]

Originally Posted by royal

For a) , the hypothesis g returns 1 for all three points. So does this mean that for each of the points 101,110 and 111 as x_n, then y_n is 1 ?

If so then I am not sure what I am then supposed to compare this to?

Correct. In this problem, we are considering different target functions (an unusual consideration that is meant to underline the difficulty of learning). You compare the values of to the values of each on these 3 points, and compute the score based on the different 's that can be the target function.

[royal]

Thanks for the quick reply.

I've only just realised that the fact I've done very little Boolean other than knowing what the basic gates are is making this confusing for me? I did some further reading, but it's hard to find a quick summary? Sorry to be asking dumb questions but using AND, OR and NOT I get 9 possible functions instead of 8:

a+b+c
a+b*c
a*b*c
a*b+c

a'b'c
a'b+c
a+b'c

a*b'c
a'b*c

Is there something straight forward thats wrong about this or do I need to go and spend an evening learning these before moving on?!

[yaser]

Originally Posted by royal

Thanks for the quick reply.

I've only just realised that the fact I've done very little Boolean other than knowing what the basic gates are is making this confusing for me? I did some further reading, but it's hard to find a quick summary? Sorry to be asking dumb questions but using AND, OR and NOT I get 9 possible functions instead of 8:

a+b+c
a+b*c
a*b*c
a*b+c

a'b'c
a'b+c
a+b'c

a*b'c
a'b*c

Is there something straight forward thats wrong about this or do I need to go and spend an evening learning these before moving on?!

No need to go through AND/OR implementation in this case. All you need is to list the all possible target functions (by values) on these three points exhaustively. That would be the possible binary combinations of of 3 bits.

[yaser]

Could you post the question in an *ANSWER* thread (see above "BEFORE posting answers - please read").

[henry2015]

Sorry, deleted.

Will post under the correct thread.

[robbinsleep]

This is exactly what I am going to ask also