PS#1
pdf
keyboard_arrow_up
School
California Lutheran University *
*We aren’t endorsed by this school
Course
IDS575
Subject
Mathematics
Date
Apr 3, 2024
Type
Pages
11
Uploaded by SuperHumanCrabPerson1153
Q1 Instance-based Learning
30 Points
Juno just started her master program at UIC this semester. As Juno is new in Chicago, she has tried several restaurants based on Opentable reviews, but none of them is truly satisfactory. She concludes that the review system does not match well with her taste because the star-
ratings are too detailed. Opentable reviews consist of four different attributes: food, ambiance, service, and noise level. Now she wants to simplify evaluation criteria of those attributes as follows:
ood: Only three categories: poor, average, or good food.
mbiance: Only three categories such as inferior, normal, or superior ambiance. ervice: Only two categories: bad or fair service.
oise-level: Ignore as this is too subjective and sensitive to visiting hours.
Based on this simplification, Juno tries to predict whether or not
she would ike a certain restaurant. The next table shows her initial research for five different restaurants in West Loop. Her goal is to learn a function: using the table of the five examples as a training data .
Q1.1
5 Points
Define each attribute ood, mbiance, ervice, and the output space ike, respectively as a set of possible values described above. (Free Response)
F
A
S
N
L
F
×
A
×
S
→
L
D
F
A
S
L
Food = {'good', 'average', 'poor'} Ambiance = {'normal', 'superior', 'inferior'} Service = {'fair', 'bad'} Like = {'yes', 'no'}
Q1.2
5 Points
What is the size of the instance space ?
18 (= 3 * 3 * 2)
Q1.3
5 Points
Hypothesis space is defined as a set of all possible function . What is the size of the hypothesis space ?
262144 (=2^18)
Q1.4
5 Points
Initially Juno thought that she will like any restaurant that serves food. Is this hypothesis consistent with the training set ?
Q1.5
5 Points
∣
X
∣
X
H
h
:
F
×
A
×
S
→
L
∣
H
∣
H
good
h
D
Yes
No
Unclear
Count the number of hypotheses in the hypothesis space (defined in Q1.2) that are consistent to her training data .
8192 (= 2^13)
Q1.6
5 Points
Juno has realized that the hypothesis space from Q1.2 would be too large to model her taste. She instead tries to evaluate each criterion by assigning numeric scores such as Food: Ambiance: Service: Her goal is to restrict hypotheses to certain functions that only use the sum of any two attribute values for predicting her potential preference. In particular, if if . Under this restriction, for instance, Juno now likes the Restaurant 4 in because it achieves 2 points from its food and service despite its ambiance.
Let H′ be the restricted hypothesis space that satisfies the above numeric prediction rule. Measure the size , a new restricted hypothesis space of . (Hint: Consider each of the three cases where only , , or matters and the other one attribute doesn’t care. Make sure that must
be a subset of )
3
Q2 Mathematical Function
10 Points
These questions will be auto-graded.
H
D
H
poor
= −1,
average
= 0,
good
= 1
inferior
= −1,
normal
= 0,
superior
= 1
bad
= −1,
fair
= 1
Like
=
yes
sum
> 0
Like
=
no
sum
≤ 0
D
good
fair
inferior
(
H
′ ⊆
H
)
∣
H
∣
′
H
{
F
,
A
} {
F
,
S
}
{
A
,
S
}
H
′
H
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
- Access to all documents
- Unlimited textbook solutions
- 24/7 expert homework help
Q2.1
5 Points
Let and be the sets with 10 and 3 elements, respecitvely. Count the number of functions that maps each element in to an element in . (Auto. Hint: Solve this problem earlier than Q1 could be helpful)
Q2.2
5 Points
Now your function must correspond the first element of into the first element of . Count again the number of functions that follows this condition.
19683 (= 3^9)
Q3 k-Nearest Neighborhood Basic
24 Points
The following subquestions will be all auto-graded. Choose either True or False.
Q3.1 Basic
5 Points
-NN can be only applicable to datasets with categorical labels.
X
Y
f
X
Y
10 + 3
10 × 3
10
3
3
10
10 −
3
1
f
X
Y
f
k
True
False
Q3.2
5 Points
-NN classifers with higher does not always perform better than the classifiers with lower . If the provided dataset consists of non-
negligible outliers, we should decrase .
Q3.3
5 Points
Generally the best is the number that shows highest training accuracy. That is the highest performance when testing on training data.
Q3.4
5 Points
Assume your 3-NN to the query point includes three data points:
90 at distance 2
80 at distance 2
50 at distance 1
Then your 3-NN prediction will be .
Q3.5
k
k
k
k
True
False
k
True
False
2+2+1
2×90+2×80+2×50
True
False
4 Points
-NN performs efficiently when there are only a few prediction queries.
Q4 k-Nearest Neighborhood
36 Points
Consider a binary classification problem with two real valued features and . Figures 1 and 2 illustrate two different training sets and . White circles indicate the positively-labeled examples, whereas black squares indicate the negatively-labeled examples. To classify a new instance point, we will use (unweighted) -Nearest Neighbors with Euclidean distance and different values. Thus the label for a new point will be predicted by the majority class (i.e., positive or negative) among the k closest examples around the query point.
Q4.1
8 Points
Draw the decision boundaries of and when .
Q4.1.pdf
Download
k
True
False
x
1
x
2
S
1
S
2
k
k
S
1
S
2
k
= 1
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
- Access to all documents
- Unlimited textbook solutions
- 24/7 expert homework help
1
of 1
Q4.2
5 Points
Which label would you predict for the query points (3, 2) and (4, 2) given the decision boundary of in Q4.1? Ties must be broken toward predicting the positive class. (Auto: Your answer must be look like "negative, negative")
negative, positive
S
1
Q4.3
5 Points
Which label would you predict for the query points (4.5, 4) and (4, 2) given the decision boundary of in Q4.1? Ties must be broken toward predicting the positive class. (Auto: Your answer must be look like "negative, negative")
positive, positive
Q4.4
10 Points
When , a partition of spaces like the above is called the -th order Voronoi Diagram or Voronoi Tesselation. Try to draw the decision boundaries of when . (Hint: Try to draw every bisector between all pairs of positive and negative examples)
Q4.4.pdf
Download
S
2
k
> 1
k
S
1
k
= 3
1
of 1
Q4.5
8 Points
If the -coordinate of four example points in are multiplied by 5, what would happen to its decision boundary when ? Could this effect cause problems when working with real data? Describe your idea: how to alleviate it. (Free Response)
Multiplying only x2 coordinates with any scalar value (>1), significance of x2 coordinates will have larger impact as compare x
2
S
1
k
= 1
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
- Access to all documents
- Unlimited textbook solutions
- 24/7 expert homework help
to x1 coordinates. And so distribution of nearest point will change accordingly which will result in change in decision boundary. To eliminate it, we can standardize or bring all attributes on same scale which makes more sense in terms of end result on real data.
GRADED
Problem Set (PS) #01
STUDENT
Urvashiben Patel
TOTAL POINTS
93 / 100 pts
QUESTION 1
Instance-based Learning
30
/ 30 pts
1.1
(no title)
5
/ 5 pts
1.2
(no title)
5
/ 5 pts
1.3
(no title)
5
/ 5 pts
1.4
(no title)
5
/ 5 pts
1.5
(no title)
5
/ 5 pts
1.6
(no title)
5
/ 5 pts
QUESTION 2
Mathematical Function
10
/ 10 pts
2.1
(no title)
5
/ 5 pts
2.2
(no title)
5
/ 5 pts
QUESTION 3
k-Nearest Neighborhood Basic
24
/ 24 pts
3.1
Basic
5
/ 5 pts
3.2
(no title)
5
/ 5 pts
3.3
(no title)
5
/ 5 pts
3.4
(no title)
5
/ 5 pts
3.5
(no title)
4
/ 4 pts
QUESTION 4
k-Nearest Neighborhood
29
/ 36 pts
4.1
(no title)
6
/ 8 pts
4.2
(no title)
R
0
/ 5 pts
4.3
(no title)
5
/ 5 pts
4.4
(no title)
10
/ 10 pts
4.5
(no title)
8
/ 8 pts