Given a set ((x,y)) need to estimate (f(x)=y) .

Terms:

  • Feature (x_i) - property of object to be classified
  • Instance (x=\begin{pmatrix}x_1&x_2&x_3&\ldots\end{pmatrix}) - features of an object
  • Instance Space (\cal I) - space of all possible instances
  • Class (\cal Y) - categorical feature of an object
  • Example ((x,y)) - instance with membership
  • Training Set (X = {}_{i=1}^N{x_i,y_i})
  • Target Concept (\cal C) - correct expression of class.
  • Concept Class - Space of all possible concepts
  • Hypothesis (h :x\mapsto{0,1}) - Approximation to target concept
  • Hypothesis class (\cal H) - Space of all possible hypothesis
  • Learning Goal - Find (h\in\cal H) that closely approximates (\cal C) (possible (\cal C\not\in H))

Errors:

  • Empirical: (E(h|X) = \frac 1N\sum_{t=1}^N 1(h(x_t)\ne y_t))
  • Generalization: instances not in (X)
  • True: instances in (\cal I)
  • Most specific and general hypothesis (\cal S) and (\cal G) covering fewest and most instances.
  • Version space - between (\cal S) and (\cal G)