Concept Learning Flashcards
What is a concept? English Definition.
A description of attributes/characteristics that can identify a particular set of object/events over a larger set of varying objects/events
What is a concept? Math Definition.
Boolean values function that returns true if an instance matches a description of attributes/characteristics…
What are instances?
Set of items over-which a concept is defined
What is a hypothesis?
Set of constraints on instance attributes.
What is a conjunctive concept?
Conjunctive concepts mandate such properties like mother mandate that both features (i) female, and (ii) parent, be present with omission of either being impossible for mother to remain true
What is a disjunctive concept?
A disjunctive concept such as a car that has many attributes but can still be a car without one of the attributes
What is the maximally general hypothesis?
Accepts all instances of X.
What is the maximally specific hypothesis?
Accepts no instances of X.
What is the target concept?
The concept we are trying to learn.
What is the goal of concept learning?
To find all hypothesis s.t h(x) = c(x) for all x
On what proof is concept learning based on?
Induction
What is the inductive learning hypothesis
Any hypothesis that can approximate the target function over sufficient training examples will do the same for test examples
What is the Find S algorithm
Finds the maximally specific hypothesis of a training set.
Basically one half of candidate elimination: only generalise the maximally specific hypothesis
What are some of the advantages of find S?
Speed
Simple
Scalable
Always guarantees one viable hypothesis
What are some of the disadvantages of find S?
Won’t always converge
Guarantees only one viable hypothesis
Sensitive to noise
What is a version space?
Set of all hypotheses consistent with training data
What is the List then Eliminate Algorithm?
Brute force
Generate every feasible hypothesis then eliminate ones where h(x) /= c(x)
Advantages of LTE
Exhaustive
Returns list of consistent hypotheses
Disadvantages of LTE
Exhaustive
Scales bad
Pretty much doo doo unusable dog water algorithm
What is the candidate elimination algorithm?
On positive examples, we generalise the maximally specific hypothesis and on negative examples, we constrain the maximally general hypothesis.
(You have to watch a youtube video)
Does C.E. converge
Yes if no noise and a valid hypothesis exists
What type of examples should learners request? (yes they can request examples)
Aim to remove as many competing hypotheses from the version space as possible.
How can we use partially learned concepts?
Have each hypothesis in the version space vote on whether an instance should be accepted or not.
An instance will be positive if it is accepted by every member of S.
An instance will be negative if it is rejected by every member of G
What is an unbiased learner?
define an unbiased hypothesis space by allowing arbitrary conjunctions, disjunctions, and negations.
Basically overfitting.
