What does VC stand for?
Vapnik and Chervonenkis
What is VC dimension?
It's a measure of the complexity of the hypothesis space. The VC dimension of an hypothesis space is a measure of the number of different classifications implementable by functions from the hypothesis space. The VC dimension is used to determine if something is PAC learnable in an infinite hypothesis space.
What are some characteristics that make up a good kernel?
The kernel should be easy to compute, well-defined, an span a sufficiently rich hypothesis space.
What role do kernel functions play in relation to SVM's?
The kernel function allows us to construct an optimal separating hyperplane in the space H without explicitly performing calculations in this space. We use kernel functions when the data is separable in a non linear way.
How do SVM's deal with overfitting?
SVM's use regularisation, which means the data are separated with a large margin.
What is the dividing plane function?
wTx + b = 0
What value do most weights take in support vector regression or linear support vector machines?
zero
What can the kernel function represent in regards to the data?
domain knowledge
What is the goal of PAC learning?
the goal of PAC learning is to determine which classes of target concepts can be learned from a reasonable number of randomly drawn training examples with a reasonable amount of computation.
When is something PAC learnable?
When a learner produces a low error most of the time.
What is a consistent learner?
a learner is consistent if it outputs hypotheses that perfectly fit the training data, whenever possible.
Define the Version Space (VS).
The Version Space is the set of all hypotheses that correctly classify the training examples.
What is the significance of the version space?
The significance of the version space is that every consistent learner outputs a hypothesis belonging to the version space, regardless of the instance space X, hypothesis space H, or training data D. The reason is that by definition the version space contains every consistent hypothesis in H.
What is Haussler's theorem?
to bound the number of examples needed by any consistent learner, we need only bound the number of examples needed to assure that the version space contains no unacceptable hypotheses.In other words: epsilon exhausting the version space.
What is epsilon exhaustion?
the version space is said to epsilon exhausted just in the case that all the hypotheses consistent with the observed training examples (i.e., those with zero training error) happen to have true error less than epsilon.
