Suppose you want to learn the concept of a favorite book model. The features you
ID: 3765652 • Letter: S
Question
Suppose you want to learn the concept of a favorite book model. The features you are looking at are: author’s gender (values: male and female), author’s country of living (US, UK, and Canada), genre of the book (comedy, drama, mystery, and romance), author’s age (senior, mid-aged, and junior), is NYT bestseller (yes and no). You gathered some data which are summarized in the table below.
Use the notation [?, ?, ?, ?, ?] for the most general model, where the “?” indicates any attribute value in the corresponding position is allowed.
What is the hypothesis that fits this data using the Version Space method? Do not simply give the answer; show the trace of all the steps that lead you to the result. Add any commentary to clarify the steps.
Explanation / Answer
Solution:
1. Positive Example: (male, US, comedy, mid, yes)
Explanation:
Initialize G to a singleton set that includes everything. i.e G = {(?,?,?,?,?)}
Initialize S to a singleton set that includes the first positive example. i.e S = {(male, US, comedy, mid, yes)}
Positive is = S = {(male, US, comedy, mid, yes)}
Negative is = G = {(?,?,?,?,?)}
These models represent the most general and the most specific heuristics one might learn.
The actual heuristic to be learned, "US male Best Comedy Seller", probably lies between them somewhere within the version space.
O -> (?,?,?,?,?) (Negative)
O -> (male, US, comedy, mid, yes) (Positive)
2. Negative Example: (male, UK, drama, senior, no)
Explanation: Specialize G to exclude the negative example.
G = { (?, US, ?, ?, ?),
(?, ?, comedy, ?, ?),
(?, ?, ?, mid, ?),
(?, ?, ?, ?, yes) }
S = (male, US, comedy, mid, yes)
Refinement occurs by generalizing S or specializing G, until the heuristic hopefully converges to one that works well.
(?,?,?,?,?)
/ /
/ /
(?, US, ?, ?, ?) / (?, ?, ?, ?, yes)
(?, ?, comedy, ?, ?) (?, ?, ?, mid, ?)
3. Positive Example: (male, UK, comedy, junior, yes)
Explanation:
Prune G to exclude descriptions inconsistent with the positive example.
prune Generalize S to include the positive example.
G = { (?, ?, comedy, ?, ?),
(?, ?, ?, ?, yes) }
S = { (male, ?, comedy, ?, yes) }
(?,?,?,?,?)
/ /
/ /
(?, US, ?, ?, ?) / (?, ?, ?, ?, yes)
(?, ?, comedy, ?, ?) (?, ?, ?, mid, ?)
(male, ?, comedy, ?, yes)
|
|
(male, US, comedy, mid, yes)
4. Negative Example: (female, Canada, mystery, mid, yes)
Explanation:
Specialize G to exclude the negative example (but stay consistent with S)
G = { (?, ?, comedy, ?, ?),
(male, ?, ?, ?, yes) }
S = { (male, ?, comedy, ?, yes) }
(male, ?, comedy, ?, yes)
|
|
(male, US, comedy, mid, yes)
5. Positive Example: (male, US, romance, mid, yes)
Explanation:
Prune G to exclude descriptions inconsistent with positive example.
Generalize S to include positive example.
G = { (male, ?, ?, ?, yes) }
S = { (male, ?, ?, ?, yes) }
(male, ?, ?, ?, yes)
|
|
(male, ?, comedy, ?, yes)
|
|
(male, US, comedy, mid, yes)
G and S are singleton sets and S = G.
Converged.
(?, ?, ?, ?, ?)
|
|
(?, ?, ?, ?, yes)
|
|
(male, ?, ?, ?, yes) (Negative)
|
|
(male, ?, ?, ?, yes) (Positive)
|
|
(male, ?, comedy , ?, yes)
|
|
(male, US, comedy, mid, yes)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.