Statistical learning methods

Definition:

The problem is to learn a function mapping examples into two classes: positive and

negative. We are given a database of examples already classified as positive or negative.

Concept learning: the process of inducing a function mapping input examples into a

Boolean output.

Examples:

  Classifying objects in astronomical images as stars or galaxies

  Classifying animals as vertebrates or invertebrates

Class of Tasks: Predicting poisonous mushrooms

Performance: Accuracy of classification

Experience: Database describing mushrooms with their class

Knowledge to learn: Function mapping mushrooms to {0,1} where 0:not-poisonous and

1:poisonous

Representation of target knowledge: conjunction of attribute values.

Learning mechanism: candidate-elimination

Representation of instances:

Features:

• color {red, brown, gray}

• size {small, large}

• shape {round,elongated}

• land {humid,dry}

• air humidity {low,high}

• texture {smooth, rough}

Input and Output Spaces:

X : The space of all possible examples (input space).

Y: The space of classes (output space).

An example in X is a feature vector X.

For instance: X = (red,small,elongated,humid,low,rough)

X is the cross product of all feature values.

Only a small subset of instances is available in the database of examples.

Learning with complete data and hidden variables

we must state some formal definitions:

Definition 1: Let X be some set of objects, with elements noted as x. Thus,X = {x}.

Definition 2: A fuzzy set A in X is characterized by a membership function mA(x) which maps each point in X onto the real interval [0.0, 1.0]. As mA(x) approaches 1.0, the "grade of membership" of x in A increases.

Definition 3: A is EMPTY iff for all x, mA(x) = 0.0.

Definition 4: A = B iff for all x: mA(x) = mB(x) [or, mA = mB].

Definition 5: mA' = 1 - mA.

Definition 6: A is CONTAINED in B iff mA <= mB.

Definition 7: C = A UNION B, where: mC(x) = MAX(mA(x), mB(x)).

Definition 8: C = A INTERSECTION B where: mC(x) = MIN(mA(x),mB(x)).