LearningTypes of LearningSupervised LearningSlide 4OutlinePredicate-Learning MethodsVersion SpacesVersion Spaces: The ProblemVersion Spaces: The TricksRewarded Card ExampleSimplified RepresentationExtension of a HypothesisMore General/Specific RelationSlide 14Example: Subset of Partial OrderConstruction of Ordering RelationG-Boundary / S-Boundary of VSlide 18Example: G-/S-Boundaries of VSlide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Version Space UpdatePOSITIVE-UPDATE(G,S,x)Slide 33Slide 34Slide 35NEGATIVE-UPDATE(G,S,x)Example-Selection Strategy (aka Active Learning)ExampleExample-Selection StrategyNoiseSlide 41VSL vs DTLStatistical ApproachesNearest Neighbor MethodsIssuesBayesian LearningExample: Candy BagsSlide 48Bayesian Learning cont.Example:Statistical Learning ApproachesNaïve BayesBayesian DiagnosisNaïve Bayes AssumptionNaïve Bayes ExampleLearning the ProbabilitiesMaximum Likelihood Estimate (MLE)Slide 58Laplace Estimate (smoothing)CommentsLearning more complex Bayesian networksNeural NetworksNeural functionBiology of a neuronBrain structureComparison of computing powerNeural networksNeural unitModel NeuronNeural ComputationLearning RulesPerceptron Learning rulePerceptron Learning AlgorithmSlide 74Representation Limitations of a PerceptronPerceptron LearnabilityLayered feed-forward network“Executing” neural networksLearningR&N: ch 19, ch 20Types of LearningTypes of Learning Supervised Learning - classification, predictionUnsupervised Learning – clustering, segmentation, pattern discoveryReinforcement Learning – learning MDPs, online learningSupervised LearningSupervised LearningSomeone gives you a bunch of examples, telling you what each one isEventually, you figure out the mapping from properties (features) of the examples to their type (classification)Supervised LearningSupervised LearningLogic-based approaches:learn a function f(X)  (true,false)Statistical/Probabilistic approachesLearn a probability distribution p(Y|X)OutlineLogic-based Approaches Decision Trees (lecture 24)Version Spaces (today)PAC learning (we won’t cover, )Instance-based approachesStatistical ApproachesPredicate-Learning Predicate-Learning MethodsMethods Version spacePutting Things TogetherPutting Things TogetherObject setGoal predicateObservable predicatesExampleset XTrainingset TestsetBiasHypothesisspace HInducedhypothesis hLearningprocedure LEvaluationyesnoExplicit representationof hypothesis space HNeed to provide H with some “structure”Version SpacesThe “version space” is the set of all hypotheses that are consistent with the training instances processed so far.An algorithm:V := H ;; the version space V is ALL hypotheses HFor each example e:Eliminate any member of V that disagrees with eIf V is empty, FAILReturn V as the set of consistent hypothesesVersion Spaces: The ProblemPROBLEM: V is huge!!Suppose you have N attributes, each with k possible valuesSuppose you allow a hypothesis to be any disjunction of instancesThere are kN possible instances  |H| = 2kNIf N=5 and k=2, |H| = 232!!Version Spaces: The TricksFirst Trick: Don’t allow arbitrary disjunctionsOrganize the feature values into a hierarchy of allowed disjunctions, e.g.any-coloryellowwhitepalebluedarkblackNow there are only 7 “abstract values” instead of 16 disjunctive combinations (e.g., “black or white” isn’t allowed)Second Trick: Define a partial ordering on H (“general to specific”) and only keep track of the upper bound and lower bound of the version spaceRESULT: An incremental, possibly efficient algorithm!Rewarded Card ExampleRewarded Card Example(r=1) v … v (r=10) v (r=J) v (r=Q) v (r=K)  ANY-RANK(r)(r=1) v … v (r=10)  NUM(r) (r=J) v (r=Q) v (r=K)  FACE(r)(s=) v (s=) v (s=) v (s=)  ANY-SUIT(s)(s=) v (s=)  BLACK(s)(s=) v (s=)  RED(s)A hypothesis is any sentence of the form: R(r)  S(s)  IN-CLASS([r,s])where:• R(r) is ANY-RANK(r), NUM(r), FACE(r), or (r=j)• S(s) is ANY-SUIT(s), BLACK(s), RED(s), or (s=k)Simplified RepresentationSimplified RepresentationFor simplicity, we represent a concept by rs, with:• r  {a, n, f, 1, …, 10, j, q, k}• s  {a, b, r, , , , }For example:• n represents: NUM(r)  (s=)  IN-CLASS([r,s])• aa represents: ANY-RANK(r)  ANY-SUIT(s)  IN-CLASS([r,s])Extension of a HypothesisExtension of a HypothesisThe extension of a hypothesis h is the set of objects that satisfies hExamples: • The extension of f is: {j, q, k}• The extension of aa is the set of all cardsMore General/Specific More General/Specific RelationRelation Let h1 and h2 be two hypotheses in H h1 is more general than h2 iff the extension of h1 is a proper superset of the extension of h2Examples: • aa is more general than f • f is more general than q• fr and nr are not comparableMore General/Specific More General/Specific RelationRelation Let h1 and h2 be two hypotheses in H h1 is more general than h2 iff the extension of h1 is a proper superset of the extension of h2 The inverse of the “more general” relation is the “more specific” relation The “more general” relation defines a partial ordering on the hypotheses in HExample: Subset of Partial Example: Subset of Partial OrderOrderaana abnbn44ba4aConstruction of Ordering Construction of Ordering RelationRelation1 10nafj k… …bar G-Boundary / S-Boundary G-Boundary / S-Boundary of Vof V A hypothesis in V is most general iff no hypothesis in V is more general G-boundary G of V: Set of most general hypotheses in VG-Boundary / S-Boundary G-Boundary / S-Boundary of Vof V A hypothesis in V is most general iff no hypothesis in V is more general G-boundary G of V: Set of most general hypotheses in V A hypothesis in V is most specific iff no hypothesis in V is more specific S-boundary S of V: Set of most specific hypotheses in Vaana abnbn44ba4aExample: G-/S-Boundaries of Example: G-/S-Boundaries of VVaa41 k… …Now suppose that 4 is given as a positive exampleSGWe replace every hypothesis in S whose extension does not contain 4 by its generalization setExample: G-/S-Boundaries Example: G-/S-Boundaries of Vof Vaana abnbn44ba4aHere, both G and S have size 1. This is not the case in general!Example: G-/S-Boundaries Example: G-/S-Boundaries of Vof Vaana