I'm taking a course on machine learning this semester, and a short prerequisites self-assessment test was posted to the course web page; it's pretty much about maths. Now, I'm not stupid, but I don't have much faith in my math skills and the test doesn't come with correct answers, so I thought I'd ask the sharp minds of GDNet about my answers. I know the questions are supposed to be simple, but when you find something simple you're either usually completely right or completely wrong.

The test with questions is here (very short), if any kind soul wants to help.

1. There are kn different assignments; there are k possibilities for the first variable, then for each of those valuations there are k possibilities for the second variable, etc. This assumes that the variables are distinguishable; that is, {x1 = 0, x2 = 1} =/= {x1 = 1, x2 = 0}.

2. There are 2n subsets, including the empty set. We can view each subset as a binary string of length n, where the nth binary digit denotes whether the nth element in the set is in the subset or not.

3. Half of the possible subsets contain a fixed element a, so 2n-1; to use the binary string reasoning from #2, it's all binary strings where the ath bit is 1.

4. We can create 22n set families. The set of set families is just the set of all subsets of the set of all subsets of the original set. Perhaps easier to read in pseudocode:
$set := a set with n elements
$subsets := all subsets of $set
set_families := all subsets of $subsets

5. The statements are different; a) says that no matter which element a we pick, there will be a set in F that contains it whereas b ) says that there is a set in F that holds every element a.

6. There are 2n+1 boolean functions with n variables. There are 2n possible inputs, and each input has two possible outputs.

7. log2 k bits. No motivation necessary.

8. k2 leaves; each right/left choice takes you one step away from the root and removes half of your remaining choices.

9. I don't completely understand this question; am I just supposed to write any linear inequality for which the boolean function is true? If so, then wouldn't 1*x1 >= 1 suffice? (False if x1 is 0, true if it's 1.) That sounds too easy, so I must have misunderstood the question.

10. I don't understand this either; what exactly is meant by characterize here? If I'm just supposed to explain what quadratic functions fulfill the conditions, then it's those where c = 0 (since q(0) = 0) and a + b = 1.

11. I don't understand this question completely either, but if I'm just supposed to explain my strategy then I would choose my xs such that if pi is the largest of all the ps, then xi = 1, otherwise xi = 0. Since we the sum of my factors can't exceed 1, wasting any part of that 1 on an element that's smaller than the maximum p will result in a value that's less than the maximum p.

You forgot the fourth one (let r be some fixed number...)

Shouldn't the answer to the seventh (according to your count) question be "the ceiling of log_2 k"?

#9: Why restrict yourself to x_1? You need the conjunction of all x_i, in which case I'd say x_1 AND x_2 AND x_3 AND ... AND x_n becomes x_1+x_2+x_3+...+x_n >= n

(and being ultra-pedantic: #6 seems to rely on functional extensionality. QuickSort and Bubble Sort have the same in- and outputs, but are they truly equal functions?)


I agree with all the rest.

2. There are 2n subsets, including the empty set. We can view each subset as a binary string of length n, where the nth binary digit denotes whether the nth element in the set is in the subset or not.

your wording on this one is weird. You use 'n' a lot, but 'n' is already defined as the total number of elements in A. change "nth binary digit" and "nth element" to some other letter for consistency.

Also, there's already equations for a lot of these. Coming up with your own way of visualizing may be good, but the teacher might be expecting you to be using the equations that are already established. Many 'assessments' are often about how you answer as much as getting the right answer.

Thanks for your help!

You forgot the fourth one (let r be some fixed number...)

Oops. The answer, in any case, should be n!/(n-r)! (n*(n-1)*(n-2)...*(n-r).) There are obviously n subsets of length 1, and if we have a subset of length r, then we have already chosen r elements from A so if we want to turn it into a subset of length r+1 we can add one out of the n-r remaining elements.

Shouldn't the answer to the seventh (according to your count) question be "the ceiling of log_2 k"?That's completely true.

#9: Why restrict yourself to x_1? You need the conjunction of all x_i, in which case I'd say x_1 AND x_2 AND x_3 AND ... AND x_n becomes x_1+x_2+x_3+...+x_n >= nYeah, that hit me just this morning; generalizing it from x1 to xn is easy.

(and being ultra-pedantic: #6 seems to rely on functional extensionality. QuickSort and Bubble Sort have the same in- and outputs, but are they truly equal functions?)I'm definitely not sure about this, but shouldn't they be from a purely mathematical view?

'valderman' said:

2. There are 2n subsets, including the empty set. We can view each subset as a binary string of length n, where the nth binary digit denotes whether the nth element in the set is in the subset or not.

your wording on this one is weird. You use 'n' a lot, but 'n' is already defined as the total number of elements in A. change "nth binary digit" and "nth element" to some other letter for consistency.

Oops, accidentally reused n. Of course it should be We can view each subset as a binary string of length n, where the xth binary digit denotes whether the xth element in the set is in the subset or not.

Also, there's already equations for a lot of these. Coming up with your own way of visualizing may be good, but the teacher might be expecting you to be using the equations that are already established. Many 'assessments' are often about how you answer as much as getting the right answer.
Yeah, I should probably go read up on those. I'm better at reasoning things out than remember set formulas for stuff.

(and being ultra-pedantic: #6 seems to rely on functional extensionality. QuickSort and Bubble Sort have the same in- and outputs, but are they truly equal functions?)

I'm definitely not sure about this, but shouldn't they be from a purely mathematical view?

I guess it just depends on how you define it all. But don't worry about it, any sane person would say your answer is correct. As I said, I was being ultra-pedantic, the only reason I brought it up is because of my traumatic experiences with Coq, a theorem prover, which didn't consider two functions to be equal just because they mapped the same inputs to the same outputs. They're only equal if you define them to be equal (i.e. by adding an axiom). I had the sudden urge to share my misery or something like that :-)

6. There are 2n+1 boolean functions with n variables. There are 2n possible inputs, and each input has two possible outputs.

Your justification actually shows that there are 22^n functions on n binary inputs. To make this clearer, think of how you would encode such functions into bit strings. Since there are 2^n possible inputs, you need a bit string of length 2^n to encode a function.

8. k2 leaves; each right/left choice takes you one step away from the root and removes half of your remaining choices.

Correct answer is 2^k. This should be clear when you start to draw complete binary trees.

9. I don't completely understand this question; am I just supposed to write any linear inequality for which the boolean function is true? If so, then wouldn't 1*x1 >= 1 suffice? (False if x1 is 0, true if it's 1.) That sounds too easy, so I must have misunderstood the question.

The general idea is true, but the question is obviously intended more general than that. What they're looking for is x_1 + ... + x_n >= n.

10. I don't understand this either; what exactly is meant by characterize here? If I'm just supposed to explain what quadratic functions fulfill the conditions, then it's those where c = 0 (since q(0) = 0) and a + b = 1.

Yes.

11. I don't understand this question completely either, but if I'm just supposed to explain my strategy then I would choose my xs such that if pi is the largest of all the ps, then xi = 1, otherwise xi = 0. Since we the sum of my factors can't exceed 1, wasting any part of that 1 on an element that's smaller than the maximum p will result in a value that's less than the maximum p.

Yes.

'valderman' said:

6. There are 2n+1 boolean functions with n variables. There are 2n possible inputs, and each input has two possible outputs.

Your justification actually shows that there are 22^n functions on n binary inputs. To make this clearer, think of how you would encode such functions into bit strings. Since there are 2^n possible inputs, you need a bit string of length 2^n to encode a function.

Oh, I see it now. Thanks!

8. k2 leaves; each right/left choice takes you one step away from the root and removes half of your remaining choices.

Correct answer is 2^k. This should be clear when you start to draw complete binary trees.I can't believe I got mixed up 2 and k there; that's just embarrasing. One just has to look at the complexity for just about anything involving binary trees to see that.