CS 534 Spring 2019

Computer Science Department

CS534 Artificial Intelligence
Homework 5 - Spring 2019

PROF. CAROLINA RUIZ

Due Date: Wednesday, April 3rd, 2019 by 10:59 am

Homework Instructions:

Read Chapters/Sections 14.1,14.2,14.4.1; 18.1-18.4, 18.7; and 18.9 of the textbook.
This is a group homework. Students must form groups of 2 students. Students are free to select their HW5 teammate (it doesn't need to be the same teams as in previous homework).
Do *not* split the problems between you and your teammate. Instead, solve each and every required HW problem by yourself and then meet with your teammate to compare your solutions and work on a joint solution together. This will prepare you both for the exam.
Turn in your group's written solutions (hardcopy) ONLY TO THE PROBLEMS MARKED AS REQUIRED BELOW by 10:59 am right before the beginning of class when the homework is due. No late homework will be accepted, no exceptions.
All required problems in this assignment will be graded.
See multiple examples of Decision Trees, Naive Bayes, and Bayesian Net problems in the solutions to homework and exam problems on the webpages of my offerings of CS4341 (ugrad AI) and CS4445 Data Mining.

Homework Problems:

Chapter 14: (pp. 558-565)

Required for the HW:
- Problem 1: Bayesian Reasoning. (10 points)
  Using the information provided in the Bayesian Reasoning Handout distributed in class, calculate the following probability. Show and justify each step of your solution.
  - P(A | E).
Not required for the HW but useful to study for the exam:
- 14.14.

Chapter 18:

Required for the HW:

Problem 2: Decision Trees. (30 points)
[Hint: For this problem, use the Decision Trees handout used in class as an illustration of how to construct a decision tree classifier.]

Consider the following very small subset of the Car Evaluation Dataset. The full dataset is available at the Univ. of California Irvine (UCI) Machine Learning Repository. See the datase webpage for a description of the different fields of this dataset.

ATTRIBUTES:	POSSIBLE VALUES:
buying          {high,low,med}
maint           {high,low,med}
persons         {four,more}
safety          {high,med}
class           {acc,good,vgood} <- classification target

buying	maint	persons	safety	class
high	high	four	high	acc
high	low	more	high	acc
high	low	four	high	acc
low	high	more	high	acc
med	high	four	high	acc
med	high	more	high	acc
high	high	four	med	acc
high	low	four	med	acc
low	med	four	med	acc
low	high	four	med	acc
low	high	more	med	acc
low	low	four	med	acc
low	high	more	med	acc
low	high	four	med	acc
med	high	four	med	acc
med	low	four	high	good
low	low	more	med	good
low	med	more	med	good
med	low	four	med	good
low	med	more	high	vgood
low	high	four	high	vgood
med	med	four	high	vgood

(25 points) Construct the full decision tree for the above dataset where class is the (classification) target attribute. Show all the steps of the calculations and of the construction of your decision tree. For your convenience, the logarithm in base 2 of selected values are provided.

x	1/2	1/3	1/4	3/4	1/5	2/5	3/5	1/6	5/6	1/7	2/7	3/7	4/7	1
log2(x)	-1	-1.5	-2	-0.4	-2.3	-1.3	-0.7	-2.5	-0.2	-2.8	-1.8	-1.2	-0.8	0

(5 points) Use the decision tree you constructed to predict the classification value of the following test instances. Show your work.

buying	maint	persons	safety	class
med,    low,    more,   med     your decision tree predicts: ______ 
low,    low,    four,   high    your decision tree predicts: ______ 
low,    med,    four,   high    your decision tree predicts: ______ 
med,    med,    more,   high    your decision tree predicts: ______

Problem 3: Naive Bayes Models. (30 points)
[Hint: For this problem, use the Naive Bayes handout used in class as an illustration of how to construct and reason with a Naive Bayes classifier.]
Consider the Car Evaluation dataset given above.
- Construct the Naive Bayes classifier over this dataset of 22 data instances.
  1. (3 points) Construct the graph of the Naive Bayes net.
  2. (17 points) For each node in the graph, construct either its prior probability table or its conditional probability table, as appropriate, based on the dataset provided. Remember to add 1 to each of the counts to avoid having probabilities that are equal to 0. Explain your work.
- (10 points) Use the Naive Bayes model you constructed to predict the classification value of the following test instance. Show your work.
```
buying	maint	persons	safety	class
low,    med,    four,   high    your Naive Bayes model predicts: ______ 
```
Problem 4: Bayesian Network Models. (30 points)
[Hint: For this problem, use the Bayesian Networks handout used in class as an illustration of how to construct and reason with a Bayesian network classifier.]
Consider the Car Evaluation Dataset above (22 instances).
- (20 points) Construct all of the conditional probability tables and prior probability tables needed for the Bayesian net below based on the 22 data instances:
- (10 points) Use the Bayesian model you constructed to predict the classification value of the following test instance. Show your work.
```
buying	maint	class
low,    med     your Bayes Network model predicts: ______ 
```

CS534 Artificial Intelligence Homework 5 - Spring 2019

PROF. CAROLINA RUIZ

Homework Instructions:

Homework Problems:

CS534 Artificial Intelligence
Homework 5 - Spring 2019