# VC-Dimension Questions and Answers – Set 2

This set of Machine Learning Multiple Choice Questions & Answers (MCQs) focuses on “Examples of VC-Dimension”.

1. Instance space: X = set of real numbers, Hypothesis space H: the set of intervals on the real number line. a and b can be any constants used to represent the hypothesis. How is H represented?
a) a – b < a + b
b) a + b < x < 2(a+b)
c) a/b < x < a*b
d) a < x < b

Explanation: H is the set of hypotheses of the form a < x < b, where a and b may be any real constants. It signifies an interval whose lower bound is a and the upper bound is b. X is contained within these bounds.

2. S = {3.1, 5.7}. How many hypotheses are required?
a) 2
b) 3
c) 4
d) 1

Explanation: The four hypotheses (1 < x < 2), (1 < x < 4), (4 < x < 7), and (1 < x < 7) represents each of the four dichotomies over S, covering neither instance, either one of the instances, and both of the instances, respectively.

3. S = {x0, x1, x2}. This set can be shattered by hypotheses of form a < x < b, where a and b are arbitrary constants.
a) True
b) False

Explanation: Without loss of generality, assume x0 < x1 < x2. This set cannot be shattered, because the dichotomy that includes x0 and x2, but not x1, cannot be represented by a single closed interval.

4. S = {x0, x1, x2}. Hypotheses are of the form a < x < b. What is H?
a) infinite
b) 0
c) 2
d) 1

Explanation: No hypotheses of the form a < x < b, where a and b can be any constants, can shatter the three points. Suppose a hypothesis wants to shatter (x0, x2) and x1, but there are no such intervals which contain both x0 and x2 but not x1.

5. S = {x0, x1, x2}. Hypotheses are of the form a < x < b. What is VC(H)?
a) 0
b) 2
c) 1
d) infinite

Explanation: No subset S of size three can be shattered. Maximum two points can be shattered by hypotheses of the form a < x < b, where a and b can be any constants. Thus VC(H) = 2.

6. S = {x0, x1, x2} and H is finite. What is VC(H)?
a) 1
b) 2
c) 3
d) infinite

Explanation: Instead of random intervals, hypotheses are straight lines. They can shatter all three points. For straight lines, VC(H) = n, where n is the number of instances. Thus VC(H) is 3.

7. S = {x0, x1, x2}. Hypotheses are straight lines. What is H?
a) 8
b) 3
c) 4
d) infinite

Explanation: VC(H) = 3. The number of points is 3. Thus, the number of dichotomies is 23 or 8. Each of the 23 dichotomies of these three instances is covered by some hypothesis, a straight line. Thus H contains 8 hypotheses.

8. S = {x0, x1, x2, x3}. Hypotheses are straight lines. What is H?
a) 8
b) 3
c) 4
d) infinite

Explanation: VC dimension of straight line hypotheses is 3. Hence, the maximum number of points that can be shattered is 3. 4 points cannot be shattered. Thus H contains an infinite number of hypotheses.

9. S contains 4 instances. H is the hypothesis space and it can shatter S. What is the correct form of hypotheses?
a) Hypotheses are intervals
b) Hypotheses are straight lines
c) Hypotheses are rectangles
d) No such hypotheses exist

Explanation: A rectangle can distinguish between 4 points easily. So, they can shatter S. Number of instances is 4. The number of hypotheses is 24 or 16.

10. For which combination H is infinite and VC(H) is finite?
a) S contains 2 points and hypotheses are intervals
b) S contains 3 points and hypotheses are intervals
c) S contains 3 points and hypotheses are straight lines
d) S contains 2 points and hypotheses are straight lines

Explanation: Suppose S contains x0, x1, and x2. Let x0 < x1 < x2. There are no intervals such that x0 and x2 are within the interval but x1 is not. Thus S is not shattered by H. So, H is infinite. Since the maximum number of instances that can be shattered is 2, VC(H) is 2.

Sanfoundry Global Education & Learning Series – Machine Learning.

To practice all areas of Machine Learning, here is complete set of 1000+ Multiple Choice Questions and Answers.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]