Computer Science notes ⇒ COM6170: Machine Learning Foundations

Much machine learning is set in the context of learning input-output functions. This includes applications such as character and speech recognition, where a graphical representation of a character sequence or a waveform is taken and a character of word sequence is returned, face recognition, load forecasting for the National Grid, credit assessment or games.

We can consider learning a function as curve fitting - finding a function which closely approximates the data we have. If we are trying to learn a function f (or the target function) which takes a vector-valued input (typically an n-tuple) and f itself may be vector valued, yielding a k-tuple as output. Often f produces a single output value.

The job of the learner is to output a hypothesis h which is a guess or approximation of the target function f. We assume that h is drawn a priori from a class of function H. f is not always known, and is not necessarily in the class H.

The learner selects h based on a set of training examples. Each training example consists of an n-tuple x drawn from the set of input vectors over which f is defined.

If for each training example x the value of f (i.e., f x) is also supplied, then the learning setting is called a supervised learning setting (most of the methods covered here will be supervised). If the training examples do not have associated output values, then the learning setting is called unsupervised learning.

Unsupervised learning is just used to explore the data, and is useful for partitioning datasets. Supervised learning is more useful - you give it inputs and the expected ouputs to find the best f.

Input vectors go by a variety of names in the literature: input vector, pattern vector, feature vector, sample, example, instance, etc, and the components x_i are variously called features, attributes, input variables or components. The values of components are generally of two major sorts: numeric (or ordinal - themselves in two divisions: real-valued and discrete-valued numbers) and nominal (or categorical, enumerated, or confusingly discrete).

If a learner produces a hypothesis h that outputs a real number, it is called a function estimator and its output is called an output value or estimate.

If a learner produces a hypothesis h that outputs a categorical value, it is called a classifier, or a recogniser categoriser, and its output is called a label, class, category or decision.

Outputs could also be vector-valued with the components being numeric and nominal (or both).

When it comes to the training regimes, considerable variation is possible in how training examples are presented or used. In the batch method, all training examlpes are available and used all at once to compute h (in a variant of this, all training examples are used iteratively to refine a current hypothesis until some stopping condition). In the incremental method, one member of the training set is selected at a time and used to modify the current hypothesis. Members of training set can be selected at random, or cycled through iteratively. If training instances become available at a particular time and are used as soon as they become available, this is called an on-line method.

Training can be direct, where each training instance has an associated target value, or indirect where only sequences of training instances have an associated outcome (e.g., chess). It may not be possible to know if an individual move is correct, only whether a sequence of moves leads to win or loss. The learner must decide which moves in the sequence were good or bad (this is the credit assignment problem).

A final consideration is to know how well our learner is doing (i.e., how good the hypothesis it produces is). A standard approach is to test the hypothesis on a set of inputs and function values not used in training - this is called the test set. Common evaluation measures used are the mean-squared error and accuracy tests (e.g., the proportion of instances misclassified).

Concept learning may be viewed as search over the space of hypotheses, as defined by the hypothesis representation, we can compute the number of distinct value combinations, and remember the combinations can include ? and ∅ to compute the number of syntactically distinct hypotheses.

However, since every hypotheses containing one or more ∅'s is equivalent (this classifies all instances as negative), we can reduce the number of syntactically distinct hypotheses to find the number of semantically distinct hypotheses.

We now have a problem of how to search this space to find the target concept.

One solution is to start with the most specific hypotheses (a vector of ∅) and, considering each training example in turn, generalise towards the most general hypothesis (a vector of ?), stopping at the first hypothesis that covers the training examples. This is called Find-S.

Intuitively we know that a hypothesis h_i is more general than h_j if every instance that h_j classifies as positive, h_i also classifies as positive, and h_i classifies instances as positive that h_j does not.

More formally, we say that instance x satisfies hypothesis h iff h(x) = 1. We define a partial ordering relation more-general-than-or-equa-to holding between two hypotheses h_i and h_j in terms of the sets of instances that satisfy them: h_i is more-general-than-or-equal-to h_j iff every instance that satisfies h_j also satisfies h_i.

Or, let h_i and h_j be boolean-valued functions defined over X. h_i is more-general-than-or-equal-to h_j (h_i ≥_g h_j) iff (∀x ∈ X)[(h_j(x) = 1) → (h_i(x) = 1)].

≥_g provides a strucutre over the hypothesis space H for any concept learning problem. Learning algorithms can take advantage of this.

Find-S is used to find a maximally specific hypothesis, and the algorithm is defined as:

1. Initialise h to the most specific hypothesis in H
2. For each positive training instance x:
    For each attribute constraint a_i in h:
        If the constraint a_i in h is satisfied by x,
        then do nothing
        else replace a_i in h by the next more general constraint satisfied by x
3. Output hypothesis h

Note that Find-S completely ignores negative training instances.

For hypothesis spaces described by conjunctions of attribute constraints, Find-S is guaranteed to output the most specific hypothesis in H consistent with the positive training examples. Find-S is also guaranteed to output a hypothesis consistent with the negative examples provided that the correct target concept is in H, and the training examples are correct.

However, Find-S has multiple problems. There may be multiple hypotheses consistent with the training data, but Find-S will only find one and give no indication of whether there may be others.

Find-S also always propose the maximally specific hypothesis, but why is this preferred to, for example, the maximally general? Find-S also has seriour problems when training examples are inconsistent - which frequently happens with noisy "real" data.

One way to represent the version space is by listing all of its members, which leads to the list-then-eliminate concept learning algorithm:

1. VersionSpace ← a list containing every hypothesis in H
2. For each training example ⟨x, c(x)⟩ remove from VersionSpace any hypothesis h for which h(x) ≠ c(x)
3. Output the list of hypotheses in VersionSpace

List-then-eliminate works in principle, so long as the version space is finite, however, since it requires an exhaustive enumeration of all hypotheses, in practice it is not feasible. From this, we can consider a more compact way to represent version spaces.

The candidate-elimination algorithm is similar to the list-then-eliminate algorithm, but uses a more compact representation of version space - representing it by its most general and most specific members. Other intermediate members in a general-to-specific ordering can be generated as needed.

The general boundary, G, of the version space VS_H,D is the set of its maximally general members. The specific boundary, S, of version space VS_H,D is the set of its maximally specific members.

Mitchell p.32 has a proof

The version space representation theorem states that every member of the version space lies between these boundaries: VS_H,D = {h ∈ H | (∃s ∈ S)(∃g ∈ G)(g ≥_g h ≥_g s)}

Intuitively, the candidate-elimination algorithm proceeds by initialising G and S to the maximally general and maximally specific hypotheses in H, and then considering each training example in turn: use positive examples to drive the maximally specific boundary up, and use negative examples to drive the maximally general boundary down.

More formally we can specify this as:

G ← maximally general hypotheses in H
S ← maximally specific hypotheses in H
For each training example d:
    if d is a positive example:
        Remove from G any hypotheses inconsistent with d
        For each hypotheses s in S that is not consistent with d:
            Remove s from S
            Add to S all minimal generalisations h of s such that h is consistent with d and some member of G is more general than h
            Remove from S any hypothesis that is more general than another hypothesis in S
    if d is a negative example:
        Remove from S any hypotheses inconsistent with d
        For each hypotheses g in G that is not consistent with d:
            Remove g from G
            Add to G all minimal generalisations h of g such that h is consistent with d and some member of S is more specific than h
            Remove from G any hypothesis that is less general than another hypothesis in S

The version space learned by the candidate-elimination algorithm will converge towards a central hypothesis provided there are no errors in the training examples, and there is a hypothesis in H that describes the target concept. In such cases, the algorithm will converge to an empty space.

If the algorithm can request the next training example (e.g., from a teacher), the speed of convergence can be increased by requesting examples that split the version space. an optimal query strategy is to request examples that exactly split the version space - this would converge in ⌈log₂ |VS|⌉ steps, however this is not always possible.

When using a classifier that has not completely converged, new examples may be classed as positive by all h ∈ VS, classes as negative by all h ∈ VS, or classed as positive by some, and negative by others.

The first two cases here are unproblematic, but in case 3, we may want to consider the proportion of positive vs. negative classifications (but then a priori probabilities of hypotheses are relevant).

As noted, the version space learned by the candidate-elimination algorithm will converge towards the correct hypothesis provided that there are no errors in the training examples, and there is a hypothesis in H that describes the target concept - however, what if no concept in H describes the target concept?

A more expressive hypothesis representation language is needed, specifically to allow disjunctive or negative attribute values.

An unbiased learned would ensure that every concept can be represented in H. Since concepts are subsets of an instance space X, we want H to be able to represent any set in the power set of X.

We can do this by allowing hypotheses that are arbitrary conjunctions, disjunctions and negations of our earlier hypotheses, but we have a new problem: the concept learning algorithm can not generalise beyond the observed examples - the S boundary is a disjunction of positive examples (covering exactly the observed positive examples) and the G boundary is a negative of a disjunction of negative examples (exactly ruling out the observed negative examples).

The capacity of candidate-elimination to generalise lies in its implicit assumption of bias - that the target concept can be represented as a conjunction of attribute values.

This forms a fundamental property of inductive inference: A learner that makes no a priori assumptions regarding the identity of the target concept has no rational basis for classifying any unseen instances (i.e., bias-free learning is futile).

More formally, since all inductive learning involves bias, it is useful to characterise learning approaches by the type of bias they employ.

If we consider a concept learning algorithm L, some instances X and a target concept c and the training examples D_c = {⟨x, c(x)⟩}, then let L(x_i, D_c) denote the classification, positive or negative, assigned to the instance x_i by L after training data on D_c. The inductive bias of L is any minimal set of assertions B such that for any target concept c and corresponding training examples D_c:

(∀x_i ∈ X)[(B ∧ D_c ∧ x_i) |- L(x_i, D_c)].

The ID3 algorithm (originally called binary classification) is the basic decision tree learning algorithm:

ID3(Examples, Target_Attribute, Attributes):
    Create a root node for the tree
    If all examples positive, return 1-node tree Root with label +
    Else if all examples negative, return 1-node tree Root with label -
    Else if Attributes = [] return 1-node tree Root with the label of the most common value of Target_Attribute in Examples
    Else
        A ← the attribute in Attribues that best classifies Examples
        The decision attribute for Root ← A
        Let Examples_vi = subset of Examples with value v_i for A
        If Examples_vi = []
        Then below this new branch add leaf node with label = the most common value of Target_Attribute in Examples
        Else below this new branch add the subtree ID3(Examples_vi, Target_Attribute, Attributes - {A})
    Return Root

Information Gain

ID3 searches a space of hypotheses (a set of possible decision trees) for one fitting the training data. The search is a simple-to-complex hill-climbing search guided by the information gain evaluation function.

The hypothesis space of ID3 is a complete space of finite, discrete-valued functions with regard to available attributes (as opposed to an incomplete hypothesis space, such as the conjunctive hypothesis space).

ID3 maintains only one hypothesis at any time, instead of (e.g.) all hypotheses consistent with the training examples seen so far. This means it can't ask questions to resolve competing alternatives, or determine how many alternative decision trees are consistent with the data.

ID3 performs no backtracking - once an attribute is selected for testing at a given node, this choice is never reconsidered, so it is susceptible to converging to local optima, rather than globally optimum solutions. It also uses all training examples at each step to make statistically-based decisions about how to refine the current hypothesis (as opposed to Candidate-elimination or Find-S, which makes decisions incrementally based on single training examples). Using statisically based properties of all the examples means this technique is robust in the face of errors in individual examples.

Inductive Bias

If we got a new example whose target classification is wrong, then the result will be a tree that performs well on errorful training examples, but less well on new unseen instances. Adapting to this noisy training data is one type of overfitting.

Overfitting can also occur when the number of training examples is too small to be representative of the true target function, and coincidental regularities can be picked up during training.

More precisely, we say that given a hypothesis space H, a hypothesis h ∈ H overfits the training data if there is another hypothesis h′ ∈ H such that h has a smaller error than h′ over the training data, but h′ has a smaller error over the entire distribution of instances.

Overfitting is a real problem for decision tree learning, with one empirical study showing a 10-25% decrease in accuracy over a range of tasks. Other machine learning tasks also suffer from the problem of overfitting.

There are two approaches to avoiding overfitting: stopping growing trees before it perfectly fits the training data (e.g., when the data split is not statistically significant), or to grow the full tree and then prune it afterwards. In practice, the second approach is more successful.

For either approach, we have to find the optimal final tree size. Ways to do this include using a set of examples distinct from the training examples to evaluate the quality of the tree, using all the data for training but then applying a statistical test to decide whether expanding or pruning a given node is likely to improve performance over the whole instance distribution, or measuring the complexity of encoding the exceptional training examples and the decision tree, and to stop growing the tree when this size is minimised (the minimum description length principle).

The first approach is the most common and is called the training and validation set approach. Available instances are divided into a training set (approximately 2/3rds of the data) and a validation set (commonly around 1/3rd of the data) with the hope that random errors and coincidental regularities learned from the training set will not be present in the validation set.

With this approach, assuming the data is split into the training and validation sets, we train the decision tree on the training set, and then until further pruning is harmful, for each decision node we evaluate the impact on the validation set of removing that node and those below it, and then remove the node that most improves the accuracy on the validation set.

The impact of removing a node is evaluated by removing a decision node, and the subtree rooted at it is replaced with a leaf node whose classification is the most common classification of the examples beneath the decision node, and this new tree can be evaluated.

To assess the value of reduced error pruning, we can split the data into 3 distinct sets: the training examples for the original tree, the validation examples for guiding the tree pruning, and further test examples to provide an estimate over future unseen examples. However, holding data back for a validation set reduces the data available for training.

Rule post-pruning is perhaps the most frequently used method (e.g., in C4.5).

This proceeds by converting the tree to an equivalent set of rules (by making the conjunction of decision nodes along each branch the antecedent of a rule, and each leaf the consequent), pruning each rule independently of the others, and then sorting the final rules into a desired sequence for use.

To prune rules, any precondition (the conjunct in an antecedent) of a rule is removed, if it does not worsen rule accuracy. This can be estimated by using a separate validation set, or by using the training data but assuming a statistically-based pessimistic estimate of rule accuracy (C4.5 does the latter).

By converting trees to rules before pruning, this allows us to distinguish different contexts in which rules are used, and to therefore treat each path through the tree differently (in contract to removing a decision node, which removes all the paths below it). Also, this removes the distinction between testing nodes near the root, and those near the leaves, avoiding the need to rearrange the tree should higher nodes be removed. Rules are often easier for people to understand too.

The initial definition of ID3 was restricted to discrete-valued target attributes and decision node attributes.

We can overcome this second limitation by dynamically defining new discrete-valued attributes that partition a continuous attribute value into a set of discrete intervals, i.e., for a continuous value A, we dynamically create a new boolean attribute A_c that is true if A > c and false otherwise. c is chosen such that it maximises information gain. This can be extended to split continuous attributes into more than 2 intervals.

The confidence intervals discussed so far only offer two-sided bounds - above and below, but we may only be interested in a one-sided bound (e.g., the upper bound on an error), and not mind if the error is lower than our estimate.

Since the normal distribution is symmetrical, we can convert any two-sided confidence interval into a one-sided interval with twice the confidence, e.g., we turn an 80% confidence interval into a 90% one-sided confidence interval by simply removing the lower bound (where an additional 10% lay).

In some cases, it may be useful to assume that every hypothesis is equally probably a priori, i.e., P(h_i) = P(h_j) for all h_i, h_j ∈ H.

In such cases, we need only consider P(D|h), the likelihood of data D given h, to find the most probably hypothesis. Any hypothesis that maximises P(D|h) is called a maximum likelihood (ML) hypothesis: h_ML = argmax_{h ∈ H}P(D|h).

A brute force MAP hypothesis learner could be implemented like so: for each hypothesis h in H, calculate the posterior probability P(h|D) = P(D|h)P(h)/P(D), and then output the hypothesis h_MAP with the highest posterior probability.

However, this brute-force MAP learning algorithm may be computationally infeasible, as it requires applying the Bayes theorem to all h ∈ H. However, this is still useful as a standard against which other concept learning approaches may be judged.

Therefore, to apply the brute-force MAP to concept learning, we assume that the training data is noise free, and that the target concept c is in hypothesis space H, and there is no a priori reason to believe any one hypothesis is more probable than any other. Therefore, we should choose P(h) = 1/|H| for all h ∈ H, therefore P(D|h), the probability of observing the target values D = ⟨d₁, ..., d_m⟩ for fixed instances ⟨x₁, ..., x_m⟩ if h is true is 1 if d_i = h(x_i) for all d_i ∈ D, and 0 otherwise.

Therefore, the brute force algorithm can now proceed in two ways. If h is inconsistent with D, then P(D|h) = 0, therefore P(h|D) = 0, or h is consistent with the training data D and P(D|h) = 1, and P(h|D) = 1/|VS_H,D|.

Therefore, if we assume a uniform prior probability distribution over H (i.e., P(h_i) = P(h_j, 1 ≤ i, j ≤ |H|) and deterministic, noise-free data (i.e., P(D|h) = 1 if D and h are consistent; 0 otherwise), then Bayes theorem tells us P(h|D) = 1/|VS_H,D| if h is consistent with D, and 0 otherwise.

Thus, every consistent hypothesis has posterior probability 1/|VS_H,D| and is a MAP hypothesis. One way of thinking of this is the posterior probability evolving as the training examples are presented from an initial even distribution over all the hypotheses to a concentrated distribution over those hypotheses consistent with the examples.

A consistent learner is any learner that outputs a hypothesis that commits 0 errors over the training examples. Each such learner, under the two assumptions of a uniform prior probability distribution over H and deterministic noise-free data, outputs a MAP hypothesis.

If we consider Find-S, as it outputs a consistent hypothesis (i.e., is a consistent learner), then under the assumptions about P(h) and P(D|h), Find-S outputs a MAP hypothesis. Find-S itself does not explicitly manipulate probabilities, but using a Bayesian framework, we can analyse it to show that its outputs are MAP hypotheses by identifying the underlying probability distributions P(h) and P(D|h) (analogous to characterising ML algorithms by their inductive bias).

We can use Bayesian analysis to show, under certain assumptions, that any learning algorithm that minimises the squared error between hypothesis and training data in learning a real-valued function will output a maximum likelihood hypothesis.

If we consider any real-valued target function f and training examples ⟩x_i, d_i⟨, where d_i is a noisy training value d_i = f(x_i) + e_i, where e_i is a random variable (noise) drawn independently for each e_i according to some normal distribution with mean = 0.

This is justified on slide 16.

The maximum likelihoold hypothesis is therefore the one that minimises the sum of the squared errors: h_ML = argmin_h∈HΣ^m_i=1(d_i - h(x_i))².

The Minimum Description Length (MDL) principle is the principle that shorter encodings (e.g., of hypotheses) are to be preferred. It too can be given an interpretation in the Bayesian framework.

MDL says (in a machine learning setting) h_MDL = argmin_h∈HL_C1(h) + L_C2(D|h), where L_C(x) is the description length of x under encoding C (i.e., prefer the hypothesis that minimises the length of encoding the hypothesis, plus the data encoded using the hypothesis).

L_C1(h) is the number of bits to describe a tree h, and L_C2(D|h) is the number of bits to describe D given h (and is equal to 0 is the examples are perfectly classified by h, so is only used to describe the exceptions), hence h_MDL trades off tree size for training errors.

So far we have sought the most probable hypothesis given the data D (i.e., h_MAP), but given a new instance x, h_MAP(x) is not the most probable classification.

In general, the most probable classification of a new instance is obtained by combining the predictions of all hypotheses, weighted by their posterior probability.

If we suppose that classifications can be any value v_j from a set of values V, then the probability that P(v_j|D) is the correct classification is Σ_hi∈HP(v_j|h_i)P(h_i|D).

So, the optimal classification for a new instance is the value v_j which maximises P(v_j|D). This is the Bayes optimal classification: argmax_vj∈VΣ_hi∈HP(v_j|h_i)P(h_i|D).

A surprising consequence of this is that Bayesian optimal classifiers may make predictions corresponding to hypotheses not in H (i.e., the classifications over all x in X produced by a Bayesian classifier may not be those which any single hypothesis in H would produce). Hence, we can think of the Bayesian optimal classifier operating over a hypothesis space H′, which includes the hypotheses that perform linear combinations of multiple hypotheses in H, and is different to the H over which Bayes theorem is applied.

The Bayes optimal classifier provides the best classification result achievable, however it can be computationally intensive, as it computes the posterior probability for every hypothesis h ∈ H, the prediction of each hypothesis for each new instance, and the combination of these 2 to classify each new instance.

Gibbs chooses one hypothesis at random according to P(h|D), and uses this to classify a new instance.

If we assume the target concepts are drawn at random from H according the the priors on H, then the error of Gibbs is less than twice the error of optimal Bayes.

Gibbs is seldom used, however.

The assumption which underlies the naive Bayes classifier, that attribute values are conditionally independent given some target value, this works fine in some settings, but in others it is too restrictive.

However, Bayesian classification is intractable without some assumption. Bayesian belief networks are some sort of intermediate approach. Rather than obliging us to determine dependencies between all the combinations of attributes/attribute values they describe the conditional independence among subsets of attributes.

More precisely, if we think of the attributes as discrete-valued random variables Y₁, ..., Y_n, each of which takes on a value from a set of values V_i, then the joint space of the variables is V₁ × ... × V_n and the joint probability distribution is the probability distribution over this space.

Bayesian belief networks describe a joint probability distribution for a set of variables, typically a subset of available instance attributes, and allow us to combine prior knowledge about dependencies and independencies among attributes with the observed training data.

Bayesian belief networks are represented as a directed acyclic graph, where each node represents a variable, and the directed arcs represent the assertion that the variable is conditionally independent of its non-descendants, given its immediate predecessors. Associated with each variable is a conditional probability table describing the probability distribution for that variable, given the values of its immediate predecessors.

The network completely describes the joint probability distribution of the variables represented by its nodes, according to the formula P(y₁, ..., y_n) = &product;ⁿ_i=1 P(y_i | Parents(Y_i)), where Parents(Y_i) denotes the immediate predecessors of Y_i in the graph.

CPTs work well for networks where all of the variables are discrete, but if the network contains continuous variables, it is impossible to specify conditional probabilities explicitly for each value - there are infinitely many values. One approach to avoid continuous variables is using discretisation - dividing up the data into a fixed set of intervals. This sometimes works, but can result in a loss of accuracy and very large CPTs.

Another approach is to use standard families of probability density functions that are specified by a finite number of parameters (e.g., normal or gaussian).

Bayesian networks where conditional distribution for a continuous variable given a discrete or continuous parents, and conditional distribution for a discrete variable given continuous parents need to be addressed.

To infer the probabilities of the values of one or more network variables given the observed values of the others can be done using Bayesian networks.

If only one variable (the query variable) is unknown, and all other variables have observed values, then it is easy to infer, but in the general case, there may be unobserved, or hidden, variables in addition to the observed or evidence variables. What is then sought, for each query variable X and observed event e (where e instantiates a set of evidence variables), is the posterior probability distribution P(X|e). This problem is NP-hard.

This can succeed in many cases, however. Exact inference methods work well for some network structures, and for large, multiply connected networks, approximate inference can be carried out using randomised sampling, or Monte Carlo, algorithms, which provide approximate answers whose accuracy depends on the number of samples generated.

Learning Bayesian Networks

k-nearest neighbour, or k-NN is the grandad of instance-based methods. It generally assumed that instances are represented as n-tuples of real values, i.e., as points in n-dimensional space Rⁿ.

The distance between any two instances is defined in terms of Euclidean distance, so given an instance x described by ⟨a₁(x), ... a_n(x)⟩, where a_r(x) is the value of the rth attribute of x, then the distance between the two instances x_i and x_j is defined as d(x_i, x_j) = √Σⁿ_r=1(a_r(x_i) - a_r(x_j))².

Given a new instance x_q to classify, k-NN finds the nearest k instances closest to x_q according to the distance measure d and picks their most common value for discrete-valued target functions, and picks their mean value for real-valued target functions. It can be thought of as nearest neighbours voting for the classification of the query instance.

Some variants interpret k as the k nearest distances instead of the k nearest instances to account for multiple equidistant neighbours.

For discrete-valued target functions f : X → V, the algorithm is:

If training, for each training example ⟨x, f(x)⟩, add the example to the list training_examples

If classifying, given a query instance x_q to be classified:
    Let x₁,x₂, ..., x_k denote the k nearest instances in training_examples to x_q
    return f^(x_q) ← argmax_{v ∈ V}∑^k_i=1 δ(v, f(x_i)), where δ(a, b) = 1, if a = b and δ(a, b) = 0 otherwise.

For continous-valued target functions f : X → R:

If training, for each training example ⟨x, f(x)⟩, add the example to the list training_examples

If classifying, given a query instance x_q to be classified:
    Let x₁,x₂, ..., x_k denote the k nearest instances in training_examples to x_q
    Return f^(x_q) ← (∑^k_i=1f(x_i))/k

Distance weighted k-nearest neighbour

Alternate distance metrics

Feature Weighting

OneR is a very simple rule learner that classified examples on the basis of a single attribute - similar to a one-level decision tree.

OneR(Target_Attribute, Attributes, Examples)
For each attribute A ∈ Attributes:
    For each value of A:
        Select the optimal value c of Target_Attribute for training examples with A = v (i.e., the most common class of training examples with A = v)
        Add the rule "if A = v then Target_Attribute = c" to the rule set for A
Return the rule set for the attribute whose rules have the highest accuracy (minimal errors) over the training examples.

The idea underlying this algorithm is that given a set of positive and negative examples, then one rule that covers many examples and incorrectly covers as few as possible is learnt, and these correctly covered examples are then removed from the set, and the process is repeated to learn more rules.

This is a greedy algorithm - it always learns the next best rule (according to some definition of best) without backtracking. The result may not be the smallest or best rule set that covers the training examples.

We must find a way of learning a rule that need not cover all the positive examples, but covers as few negative ones as possible.

Like in ID3, we start with an empty attribute test (i.e., assume all the examples are positive) and then add the attribute test that most improves rule performance over the test set, and then repeat. Hence, this search is a general-to-specific search through the space of possible rule antecedents.

Unlike in ID3, rather than exploring (via a subtree) each possible value the chosen attribute may take, we just follow the attribute-value pair that yields the best performance.

This type of search is a beam search - a greedy, depth-first search with no backtracking.

Beam searches can be of width k, where the k best hypotheses at each depth are pursued, rather than just the best. This reduces the risk, as present in a greedy search, of finding local optima, not the global optimum.

Again, like in ID3, there are many possible ways of choosing the next best extension to the hypothesis, and entropy is one of these ways.

Slide 12, lecture 12 has
full pseudocode.

This algorithm is closely related to the CN2 program introduced by P. Clark and R. Niblett in 1989. The rule output by the algorithm is the one whose performance is the greatest (not necessarily the last one generated), and the postcondition is only chosen as the last step, after the best precondition has been identified (the postcondition is chosen to relfect the most common value of the target attribute amongst the examples matched by the precondition).

A variant on rule learning programs is the default negative classification. It may be useful to learn only rules that cover positive examples, and assign a default negative classification to every example not covered by a rule. When the fraction of training examples that are positive is small, a rule set is more compact and intelligible to humans if rules identify only positive examples, all other examples are classified as negative.

Learn-one-rule can be modified to do this by adding an input argument to specify which target attribute value is to be learnt (generalisation to multi-valued target attributes) and modifying the evaluation function such that it measures a fraction of positive examples covered, instead of negative entropy.

Sequential covering algorithms (e.g., CN2) repeatedly learn one rule at a time, removing the covered examples, but simultaneous covering algorithms (e.g., ID3) learns a whole set of disjunctive rules simultaneously. Algorithms such as ID3 choose amongst attributes (to decide which should be the next decision node) based on the partitions of data alternative attributes define, whereas CN2 choosed amongst attribute-value pairs based on the subsets of data they cover.

To learn n rules with k attribute-value tests in their preconditions, sequential covering algorithms evaluate n × k possible rule preconditions, with an independent choice about each precondition in each rule. Simultaneuous covering algorithms make fewer independent choices - adding a decision node which is an attribute with m values corresponds to choosing preconditions for the multiple rules associated with that node.

Sequential covering algorithms may be more appropriate when there is more training data.

Another consideration is whether general-to-specific, or specific-to-general, is preferred. Algorithms such as learn-one-rule search from general-to-specific, whereas Find-S is specific-to-general. Which is preferable? Searching from general-to-specific gives a unique starting point, whereas searching from specific-to-general means each instance is a potential starting point - this can be addressed by randomly selecting some instances with which to initialise and then directing the search.

Generate-then-test and example-driven are also two variants of rule learning programs. Learn-one-rule is a generate-then-test algorithm - it repeatedly generates a syntatically legal rule precondition and then tests the precondition's performance. The alternative example-driven strategy, as used in Find-S and Candidate-Elimination, are guided by the individual training examples in the generation of hypotheses.

In example-driven algorithms, a single example is analysed to derive an improved hypothesis, but in a generate-then-test algorithm, hypotheses are generated without reference to the training data, only be exploring the space of syntactically legal hypotheses, and then testing against the data.

Generate-then-test algorithms have the advantages that performance is assessed over many examples, rather than just one, minimising the impact of noisy training data, whereas example-driven algorithms can be misled by a single noisy training example.

As with decision trees, the rules learned by sequential covering and learn-one-rule can become over-specialised so as to fit the trining data, but performing less well in the real world. As with decision trees, post-pruning of rules can be used to deal with this. Removing pre-conditions from a rule if that leads to increased performance over a set of held-out pruning examples, distinct from the training examples, is one way to tackle this.

Rule Performance Functions

Recall LPA.

Propositional logic allows the expression of individual propositions and their truth-functional combinations (using connectives such as ∧, &or, etc), and inference rules can be defined over propositional forms, but propositional logic does not break down inside the proposition for individual parts to be considered. e.g., "Tom is a man" is an atom, and "Tom" is not its own entity.

e.g., if P is "Tom is a man" and Q is "All men are mortal", then the inference that Tom is mortal does not follow in propositional logic. First order predicate calculus would allow us to express this.

First order rule learners can generalise over relational concepts (which propositional learners can not), and they can also learn recursive rules.

Since the rules (Horn clauses) that are learnt by rule learners are the same form as rules in logic programming languages, such rule programming is called inductive logic programming.

FOIL (Qunlan, 1990) is the natural extension of Sequential-Covering and Learn-One-Rule to first order rule learning. FOIL learns first order rules which are similar to Horn clauses with two exceptions: literals may not contain function symbols (reducing the complexity of the hypothesis space), and literals in the body of the clause may be negated (hence making them more expressive than Horn clauses).

Like Sequential-Covering, FOIL learns one rule at a time and then removes positive examples covered by the learned rule before attempting to learn a further rule, but unlike Sequential-Covering, FOIL only tries to learn rules that predict when the target literal is true (the propositional version sought rules that predicted both true and false values of the target attribute), and performs a simple hill-climbing search (a beam search of width 1).

FOIL searches its hypotheses space via two nested loops.

The full pseudocode and algorithm
is on slide 10, lecture 13.

The outer loop at each iteration adds a new rule to an overall disjunctive hypothesis. This may be viewed as a specific-to-general search starting with the empty disjunctive hypothesis covering no positive instances and stopping when the hypothesis is general enough to cover all the positive examples.

The inner loop works out the detail of each specific rule, adding conjunctive constraints to the rule preconditions on each iteration. This loop may be viewed as a general-to-specific search, starting with the most general precondition (empty) and stopping when the hypothesis is specific enough to exclude all the negative examples.

The principle differences between this and Sequential-Covering is that in the inner loop, FOIL needs to cope with variables in the rule preconditions. The performance measure used in FOIL is not the entropy measure used before since the performances of distinct bindings of rule variables need to be distinguished, and FOIL only tries to discover rules that cover positive examples.

If we are learning a rule of the form P(x₁, x₂, ..., x_k) ← L₁...L_n, then candidate specialisations add a new literal of the form: Q(v₁, ..., v_r) where Q is any predicate in the rule or training data, and at least one of the v_i in the created literal must already exist as a variable in the rule; or, Equal(x_j, x_k) where x_j and x_k are variables already present in the rule; or, the negation of either of the above forms of literals.

To choose the best literal to add when specialising, FOIL considers each possible binding of variables in the candidate rule specialisation to constants in the training examples, making the closed world assumption that any predicates or constants not in the training data are false given an initial rule.

At each stage of rule specialisation, candidate specialisations are preferred according to whether they possess more positive and fewer negative bindings. The precise evaluation measure used by FOIL is:

Foil_Gain(L, R) = t(log₂((p₁)/(p₁ + n₁)) - log₂((p₀)/(p₀ + n₀))), where L is the candidate literal to add to the rule R, p₀ is the number of positive bindings of R, p₁ is the number of positive bindings of R + L, n₀ is the number of negative bindings of R, n₁ is the number of negative bindings of R + L and t is the number of positive bindings of R also covered by R + L.

In information theoretic terms, -log₂((p₀)/(p₀ + n₀)) is the minimum number of bits to encode the classification of a positive binding covered by R and -log₂((p₁)/(p₁ + n₁)) is the minimum number of bits to encode the classification of a positive binding covered by R + L and t is the number of positive bindings covered by R that remain covered by R + L.

So, Foil_Gain(R, L) is the reduction due to L in the total number of bits required to encode the classification of all the positive bindings of R.

FOIL can only add literals until no negative examples are covered only in the case of noise-free data - otherwise some other strategy must be adopted. Quinlan proposed the use of a minimum description length measure to stop rule extension when the description length of rules exceeds that of the training data they explain.

A second appraoch to inductive logic programming is based on the observation that induction is the inverse of deduction.

More formally, induction is finding a hypothesis h such that (∀⟨x_i, f(x_i)⟩ ∈ D) B ∧ h ∧ x_i entails f(f(x_i)), where D is the training data, x_i is the ith training instance and f(x_i) is the target function value for x_i and B is other background knowledge.

This says, for each training data instance, the instance's target classification is logically entailed by the background knowledge, together with the hypothesis and the instance itself. The task is, typically given the target classification, the training data instance and some background knowledge, which hypothesis h satisfies the the above.

This approach subsumes the earlier idea of finding a h that fits the training data, and the domain theory B helps define the meaning on fitting the data. The formula suggests algorithms that search H, guided by B.

However, this does not naturally allow for noisy data - noise can result in inconsistent constraints in h and most logical frameworks break down when given an inconsistent set of assertions. Additionally, first order logic gives a huge hypothesis space H, which can result in overfitting, as well as the issue of intractibility in calculating all acceptable h's. Whilst the background knowledge B should help constrain hypothesis search, many ILP systems increase the hypothesis search space as B is increased.

Propositional Resolution

First Order Resolution

The inverse resolution operation is non-deterministic. In general, for a given target predicate C, there are many ways to pick C₁ and L₁ and the unifying substitutions Θ₁ and Θ₂.

Rule learning algorithms based on inverse resolution have been developed, e.g., CIGOL which uses sequential covering to iteratively learn a set of Horn clauses that cover the positive examples: on each iteration, a training example not yet covered is selected, and inverse resolution is used to general a candidate hypothesis h that satisfies B ∧ h ∧ x_i entails f(x_i), where B is the background knowledge, and clauses learned already. This is an example-driven search, though if multiple hypotheses cover the example, then the one with the highest accuracy over further examples can be preferred - this contracts with FOIL's generate-then-test approach.

Progol

Initially, we consider only the case of learning boolean-valued functions from noise-free data. The general learning setting consists of: X, the set of all possible instances over which target functions are to be defined; C, the set of target concepts the learner may be asked to learn (∀ c ∈ C, c ⊆ X); the examples are drawn at random from X according to a probability distribution D; a learner L that considers a set of hypothesis H, and, after observing some sequence of training examples, outputs a hypothesis h ∈ H which is its estimate of c. L is then evaluated by testing the performance of h over some new instances drawn randomly from X according to D.

Given this setting, computational learning theory attempts to characterise the various learners L using various hypothesis spaces H, with learning target concepts drawn according to various instance distributions D from various classes C.

We would like to determine how many training examples we need to learn a hypothesis h with error_D(h) = 0. However, this is pointless, since for any set of training examples T ⊂ X, there may be multiple hypotheses consistent with T and the learner can not be guaranteed to choose one corresponding to the target concept, unless it is training on every instance in X (which is unrealistic). Additionally, since training examples are drawn at random, there must be a non-zero probability that they will be misleading.

To compensate for this, we weaken the demands on the learner, no longer requiring it to output a zero error hypothesis, only that the error be bounded by some constant ε that can be arbitrarily small, and we don't require that the learner succeeds for every randomly drawn sequence of training examples - only that its probability of failure by bounded by some constant δ that can be made arbitrarily small.

That is - we only assume the learner will probably learn a hypothesis that is approximately correct - hence probably approximately correct (PAC) learning.

If we consider a class C of possible target concepts defined over a set of instances X of length n, and a learner L using hypothesis space H, then C is PAC-learnable by L using H if ∀ c ∈ C, distributions D over X, ε such that 0 < ε < 0.5, and δ such that 0 < δ < 0.5, learner L will, with probability at least (1 - δ) output a hypothesis h ∈ H such that error_D(h) ≤ ε in time that is polynomial in 1/ε, 1/δ, n and size(c).

Here, n measures the length of individual instances (e.g., if instances are conjunctions of k boolean features n = k) and size(c) is a length encoding of c, so if concepts in C are conjunctions of 1 to k boolean features, then size(c) is the number of boolean features use to describe c.

The definition of PAC-learnability requires that L must output with arbitrarily high probability (1 - δ) a hypothesis with arbitrarily low error ε and the L must output a hypothesis efficiently - in a time that grows at most polynomially is 1/&epsilon and 1/δ (the demands on the hypothesis), n (a demand on the complexity of the instance space X) and size(c) (a demand on the complexity of a concept class C).

This definition does not explicitly mention the number of training examples required, only the computational resources (time) required. However, the overall time and the number of examples are closely linked. If L requires a minimum time per training example, then for C to be PAC-learnable by L, L must learn from a number of examples which is polynomial in 1/ε, 1/δ, n and size(c). A typical approach to proving some class C is PAC-learnable is to show that each concept in C can be learned from a polynomial number of training examples, and the processing time per training example is polynomially bounded.

It is difficult to know if H contains a hypothesis with arbitrarily small error for each concept in C if C is not known in advance. We could could know this if H is unbiased, but this is an unrealisatic setting for ML. Still, PAC learning provides valuable insights into complexity of learning problems, and the relationship between generalisation accuracy and the number of training examples. Also, the framework can be modified to remove the assumed that H contains a hypothesis with arbitrarily small error for each concept in C.

The growth in the number of required training examples with problem size is called the sample complexity.

We are interested in the bound on sample complexity for consistent leaners (those that output hypotheses that perfectly fit the training data, if it exists) independent of any specific algorithm.

If we recall that version space contains every consistent hypothesis, then every consistent learner must output a hypothesis somewhere in the version space. So, to bound the number of examples needed by a consistent learner, we need only bound the number of examples needed to ensure the version space contains no unacceptable hypotheses.

More precisely, we say that the version space VS_H,D is said to be ε-exhausted with respect to the target concept c and instance distribution D if every hypothesis h in VS_H,D has error less than ε with respect to c and D: (∀h ∈ VS_H,D) error_D(h) < ε.

VS_H,D is the subset of h ∈ H such that h has no training error (r = 0). It is important to remember that error_D(h) may be non-zero, even when h makes no errors on the training data.

The version space is then ε-exhausted when all hypotheses remaining in VS_H,D have error_D(h) < &epsilon.

We can demonstrate a bound on the probability that a version space will be exhausted after a given number of training examples, even without knowing the identity of the target concept, or the distribution from which the training examples are drawn:

If the hypothesis space H is finite, and D is a sequence of m >e; 1 independently random examples of some target concept c, then for any 0 <e; ε <e; 1, the probability that the version space with respect to H and D is not ε-exhausted (with respect to c) is less than |H|e^-εm.

This bounds the probability that any consistent learner will output a hypothesis h with error_D(h) >e; ε. If we want this probability to be below &delta (i.e., |H|e^-εm <e; δ), then m >e; 1/ε(ln|H| + ln(1/δ)). This gives a general bound on the number (m) of training examples needed to learn any target concept in H for any δ,&epsilon.

Given this theorem, we can use it to determine sample complexity and PAC-learnability of specific concept classes. If we consider a concept class C consisting of concepts describable by conjunctions of boolean literals (boolean variables and negations of these) and suppose H contains conjunctions of constraints on up to n boolean attributes (i.e., n boolean literals), then |H| = 3ⁿ (for each literal, a hypothesis may either include it, include its negation, or not include it).

We can now consider how many examples are sufficient to assure with probability at least (1 - δ) every h in VS_H,D satisfies error_D(h) <e; ε. Using the theorem, m ≥ 1/ε(n ln 3 + ln(1/δ)).

So far, we have assumed c ∈ H (i.e., there is at least one h with zero error), however if this is not the case, we typically want the hypothesis h that makes the fewest errors on training data. A learner that does not assume c ∈ H is called an agnostic learner.

If we let error_D(h) (which may differ from the true error) be the training error of h over training examples D, we want to determine how many training examples are necessary to ensure, with high probability, that the true error of the best hypothesis error_D(h_best) will be no more than ε + error_D(h_best).

Hoeffding bounds can be used which assert that for the training data containing m randomly drawn examples: Pr[error_D(h) > error_D(h) + ε] ≤ e^-2mε2.

This bounds probability that an arbitrarily chosen single hypothesis has a very misleading training error. To ensure the best hypothesis has an error bounded this way, we must consider the probability that any of the |H| hypotheses could have a large error: Pr[(&exists;h ∈ H) error_D(h) > error_D(h) + ε] ≤ |H|e^-2mε2.

We call this probability δ and determine how many training examples are necessary to hold δ to a desired value (i.e., to keep δ ≤ |H|e^-2mε2): m ≥ 1/2ε² (ln |H| + ln (1/δ)).

This is an analgoue of the previous equation where the learner was assumed to pick a hypothesis with zero training errors, now we assume the learner picks the best hypotheses, but may still contain training errors.

We now note that m grows as a square of 1/ε, rather than linearly.

Vapnik-Chervonenkis (VC) dimension

Above we have considered the number of examples that are needed to learn a target concept, but an alternative question that may be asked is "how many mistakes does the learner make before converging to a correct hypothesis?". This leads to a different framework for characterising learning algorithms.

If we consider a setting similar to PAC learning (that is, instances drawn at random from X according to some distribution D, and the learner must classify each instance before receiving the correct classification from the teacher), we can ask whether we can bound the number of mistakes the learner makes before converging.

The mistake bound model can be of practical interest in settings where learning must take place during the use of the system, rather than in the off-line training state, so errors during this process want to be minimised.

We let M_A(C) be the maximum number of mistakes made by the algorithm A to the learn the concepts in C (the maximum over all possible c ∈ C, and all possible training sequences): M_A(C) ≡ max_c∈CM_A(c).

If C is an arbitrary non-empty concept class, then the optimal mistake bound for C (denoted Opt(C)) is the minimum over all possibly learning algorithms A of M_A(C): Opt(C) ≡ min_{A∈learning algorithms}M_A(C), i.e., Opt(C) is the number of mistakes made for the hardest concept in C, using the hardest training sequence by the best algorithm.

VC(C) ≤ Opt(C) ≤ M_Halving(C) ≤ log₂(|C|) has been proved to hold.

Weighted-Majority Algorithm

Numeric regression can be used as a classic technique if the target and non-target attributes are numeric.

The output class/target attribute x is expressed as a linear combination of the other attributes a₁, ..., a_n with predetermined weights w₁, ..., w_n such that x = w₀ + w₁a₁ + w₂a₂ + ... + w_na_n.

The machine learning challenge is to compute the weights from the training data (i.e., view an assignment to weights w_i as an hypothesis and pick the hypothesis that best fits the training data).

In linear regression, the technique used to do thise choses the w_i so as to minimise the sum of the squares of the differences between the actual and predicted values for the target attribute over the training data - this is called least squares approximation. If the difference between actual and predicted target values is viewed as an error, then the least squares approximation minimises the sum of the errors squared, and hence sum of the errors across the training data.

Linear regression is frequently thought of as fitting a line/plane to a set of data points, but it can be used to fit the data with any function of the form (x; β) = β₀ + β₁x₁ + ..., where x and β are vectors. That is, each explanatory variable (x_i) in the function is multiplied by an unknown parameter (β_i), there is at most one unknown parameter with no corresponding explanatory variable (β₀) and all of the individual terms are summed to produce the final function value. Hence, quadratic curves, straight-line models in log(x), polynomials in sin(x) are linear in the statistical sense so long as they are linear in the parameters β_i, even though they are not linear in respect of the explanatory variables.

Least Squares Approximation

Linear regression (or any regression technique) can be used for classification in domains with numeric attributes.

Regression is performed for each class, setting the output to 1 for each training instance in the class, and 0 to the others, resulting in a linear expression for each class. For test instances, the value of each linear expression is calculated, and the class which has the largest linear expression is the one assigned. This is called multiresponse linear regression.

Another technique for multiclass (i.e., more than 2 classes) classification is pairwise classification. Here, you build a classifier for every pair of classes using only the training instances from those classes. The output for a test instance is the class which receives the most votes (across all the classifiers).

If there are k classes, this method results in k(k - 1)/2 classifiers, but this is not overly computationally expensive, since for each classifier, training takes place on just the subset of instances in the two classes.

This technique can be used with any classification algorithm.

The Perceptron

The main limitation of simple linear classifers is that they can only represent linear class boundaries, making them too simple for many applications. Support vector machines (SVMs) use linear models to implement non-linear class boundaries by transforming input using a non-linear mapping. The instance space is mapped into a new space, and a non-linear class boundary in the original space maps onto a linear boundary in the new space.

Suppose that we replace the original set of n attributes by a set including all products of k factors that can be constructed from these attributes (i.e., we move from a linear expression in n variables to a multivariate polynomial of degree k). So, if we started with a linear model with two attributes and two weights (x = w₁a₁ + w₂a₂), we would move to one with four synthetic attributes and four weights (x = w₁a₁³ + w₂a₁²a₂ + w₃a₁²a₂² + w₄a₂³).

To generate a linear model in the space spanned by these products of factors, each training instance is mapped into a new space by computing all possible 3 factor products of its two attribute values and the learning algorithm applied to these transformed instances. To classify a test instance, it is transformed prior to classification.

However, there are issues of computational complexity: 5 factors of 10 attributes lead to other 2000 coefficients, and additionally overfitting can occur if the number of coefficents is large relative to the number of training instances (the model is "too nonlinear"). SVMs solve both problems using a linear model called the maximum margin hyperplane.

The maximum margin hyperplane gives the greatest separation between the classes. The perpendicular bisector of the shortest line connecting the convex hulls (tightest enclosing convex polygon) of the sets of points in each class is constructed, and the instances closest to the maximum margin hyperplane are called support vectors, and there is at least one per class. These support vectors uniquely define the maximum margin hyperplane. Given them, we can construct the maximum margin hyperplane and all other instances can be discarded.

SVMs are unlikely to overfit as overfitting is caused by too much flexibility in the decision boundary. The maximum margin hyperplane is relatively stable and only changes if the training instances that are the support vectors are added or removed. Usually, there are few support vectors (which can be thought of as global representatives of the training set) which give little flexibility.

SVMs are not computational infeasible as to classify a test instance, the vector dot product of the test instance with all support vectors must be calculated. The dot product invloves one multiplication and one addition per attribute (expensive in the new high-dimensional space resulting from the non-linear mapping), however we can compute the dot product on the original attribute set before mapping (e.g., if using a high dimensional feature space based on the products of k factors, take the dot product of vectors in low dimensional space and raise the the power k - a function called a polynomial kernel - k usually starts at 1, a linear model, and increased until no reduction in the estimated error).

Other kernel functions can be used to implement different non-linear mappings: radial basis function (RBF) kernel, equivalent to an RBF neural network, or sigmoid kernels, equivalent to a multilayer perceptron with one hidden layer).

The choice of kernel depends on the application and may not be much different in practice. SVMs can be generalised to cases where the training data is not linearly separable, but as slow in training compared to other algorithms, such as decisino trees. However, SVMs can produce very accurate classifiers, and on text classification, the best results are now typically obtained using SVMs.

As the perception training rule is only guaranteed to converge if the training examples are linearly separable. The delta rule is designed to address this difficulty, it converges to a best-fit approximation to a target function if the training examples are not linearly separable.

The key idea behind the delta rule is to use gradient descent to search the hypothesis space of possible weight vectors to find the best fit to the training data. Gradient descent is important because it is the basis of the Backpropagation algorithm (the most popular algorithm for training multilayer ANNs) and can be used as the basis for any learning algorithm that must search a hypothesis space containing hypotheses with continuous parameters.

If we consider the task of training an unthresholded perceptron (i.e., a linear unit) whose output o is given by o(x) = w·x, then we can specify a measure of training error of a hypothesis (weight vector) w.r.t. the training examples: E(w) ≡ 1/2 ∑_d∈D(t_d - o_d)², where D is the set of training examples, t_d is the target output for a training example d and o_d the output of the linear unit for the training example d.

If we consider a linear unit with just two weights (w₀ and w₁), then the plane w₀,w₁ represents the entire hypothesis space. A third dimension exists for the error E for a fixed set of training examples. Given the definition of E, the error surface must always be parabolic with a single global minimum.

Gradient descent search determines a weight vector that minimises E by starting with an arbitrary weight vector, and modifies the vector in small steps by altering it in the direction that produces the steepest descent along the error surface, stopping when the global minimum error is reached.

The derivation of the steepest descent along the error surface is determined by computing the derivative of E w.r.t. each component of the vector w - this is called the gradient of E w.r.t. w. When interpreted as a vector in weight space, the gradient specifies the direction of the steepest increase in E, so the negative of this is the direction of the steepest decrease.

Gradient_Descent(training_examples, η)
Initialise each w_i to some small random value
Until the termination condition is met:
    initialise each Δw_i to 0
    for each ⟨x, t⟩ in training_examples:
        input the instance x to the unit and compute the output o
        for each linear weight w_i:
            Δw_i ← Δw_i + η(t - o)x_i
    for each linear weight w_i:
        w_i ← w_i + Δw_i

Since the error surface has a single global minimum, this algorithm converges to a weight vector with minimum error regardless of whether the training examples are linearly separable, given a sufficiently small η.

Stochastic Approximation to Gradient Descent

The delta rule converges asymptopically toward the minimum error hypothesis, possibly requiring unbounded time, regardless of whether the training examples are linearly separable.

Single perceptrons can only express linear decision surfaces. Interesting real world problems often involve learning decision boundaries. Multiple layers of cascaded linear units still only produce linear functions, so they are not appropriate if we want to learn non-linear functions. Perceptrons are another possiblity, but discontinuous thresholds means it is undifferentiatable and hence not suitable for gradient descent.

One solution is the sigmoid unit - like a perceptron, but based on a smoothed, differentiable threshold function. The sigmoid's output o is given by o = σ(w·x) where σ(y) = 1/(1 + e^-y).

The Backpropagation algorithm learns the weights for a multilayer network governing a network with a fixed set of units and connections. It uses gradient descent to try and minimise the squared error between the network outputs and the target values for the same inputs that produced these outputs.

Since we are dealing with a network with multiple output units, rather than one as before, E must be redefined to sum the error over all the output units: E(w) ≡ 1/2 ∑_{d ∈ D}∑_k∈outputs(t_kd - o_kd)², where outputs is the set of output units, t_kd and o_kd are the target and output valyes of the kth output unit for the training example d.

The learning problem is to search a hypothesis space defined by all possible weight values for all units in the network. This can be visualised in terms of an error surface as before, except now the error is defined as above and one dimensional in the space needed for each of the weights associated with the units in the network. As before, we can now use gradient descent to search for a hypothesis to minimise E.

The algorithm is outlined on
slide 24 of lecture 18.

In multilayer networks, the error surface may have multiple local minima, and backpropagation is only guaranteed to converge toward some local minimum, not the global minimum error. Despite this, it has been remarkably successful in practice.

The algorithm as stated only applied to two level feedforward networks, but can be straightforwardly extended to feedforward networks of any depth.

The gradient descent weight update rule is similar to the delta rule. Like the delta rule, each weight is updated in proportion to the learning rate η, the input value x_ji to which the weight is applied and the error in the output of the uni, but the error (t - o) in the delta rule is replaced by the more complex error term δ_j. The exact form of δ_j follows from the mathematical derivation of the backpropagation weight tuning rule.

The backpropagation algorithm presented corresponds to stochastic gradient descent.

We could use the rule learning methods studied earlier, considering each possible combination of attributes as a possible consequent of the if-then rule and then prune the resulting association rules by coverage (or support - the number of instances the rules correctly predict) and accuracy (or confidence - the proportion of instances to which the rule applies which it correctly predicts). However, given the combinatorics, such an approach is computationally infeasible. Instead, we base the approach on the assumption that we are only interested in rules with some minimum coverage. We look for combinations of attribute-value pairs with pre-specificed minimum coverage, called item sets - where an item is an attribute-value pair.

We start by sequentially generating all 1-item, 2-item, ..., n-item sets that have minimum coverage. This can be done efficiently by observing that an n-item set can achieve minimum coverage only if all of them n - 1-item sets which are subsets of the n-item set have minimum coverage.

Next, we form rules by considering for each minimum coverage item set all possible rules containing 0 or more attribute-value pairs from the item set in the antecedent and one or more attribute-value pairs from the item set in the consequent. The coverage for each rule is then computed: number for which the consequent is correct / number for which the antecedent matches.

Approaches to clustering can be characterised in various ways. One such characterisation is by the type of clusters produced.

Clusters may be partitions of the instance space (each instance is assigned to exactly one cluster), overlapping subsets of the instance space (instances may belong to more than one cluster), probabilities of cluster membership are associated with each instance, and hierarchial structures, e.g., tree-like dendograms (any given cluster may consist of subclusters, or instances, or both).

Hierarchial clustering can be: agglomerative (bottom-up), which starts with individual instances and then groups the most similar; divisive (top-down), which starts with all instances in a single cluster and divides them into groups so as to maximise within group similarity; and mixed, which starts with individual instances and either adds to an existing cluster or forms a new cluster, possibly merging or splitting instances in existing clusters (e.g., CobWeb).

Non-hierarchial (flat) clustering can take either: a partitioning approach where k clusters are hypothesised, and then cluster centres are randomly picked, and instances are iteratively assigned to the centres, and the centres recomputed until stable, and; probabilistiv approaches, which hypothesises k clusters each with an associated (initially gussed) probability distribution of attribute valyes for instances in the cluster, then the cluster probabilities for each instance are iteratively computed, and the cluster parameters recomputed until stability.

Another taxonomic attribute to consider is incremental vs. batch clustering - are clusters computed dynamically as instances become available, or statically on the presumption that the whole instance set is available?

Agglomerative Clustering

Divisive Clustering

Similarity Functions

Non-hierarchial Clustering

k-means Clustering

Probability-based Clustering and the EM algorithm

Bootstrap aggregating ("Bagging") is a process whereby a single classifier is constructed from a number of classifiers. Each classifier is learned by applying a single learning scheme to multiple artificial training datasets that are derived from a single, original, training dataset.

These artificial datasets are obtained by randomly sampling with replacement from the original dataset, creating new datasets of the same size. The sampling procedure deletes some instances and replicates others.

The combined classifier works by applying each of the learned classifiers to novel instances, and deciding their classification by majority vote. For numeric predictions, the final values are determined by averaging the classifier outputs.

Bagging produces a combined model that often performs significantly better than a single model built from the original data set, and never performs substantially worse.

Bagging generates an ensemble of classifiers by introducing randomess into the learner's input. Some learning algorithms have randomless built-in. For example, perceptrons start out with randomly assigned connection weights that are then adjusted during training. One way to make such algorithms more stable is to run them several times with different random number seeds and combine the classifier predictions by voting or averaging.

A random element can be added into most learning algorithms.

Randomisation requires more work than bagging, because the learning algorithm has to be modified, however it can be applied to a wider range of learners; bagging fails with stable learners (those whose output is insensitive to small changes in input), however randomisation can be applied by, e.g., selecting differently randomly chosen subsets of attributes on which to base the classifiers.

Like bagging, boosting works by combining (via voting or averaging), multiple models produced by a single learning scheme. Unlike bagging, it does not derive models from artificially produced datasets generated by random sampling, instead if builds models iteratively, with each model taking into account the performance of the last.

Boosting encourages subsequent models to emphasise examples badly handled by earlier ones. This builds classifiers whose strengths complement each other.

In AdaBoost.M1, this is achieved by using the notion of a weighted instance. The error is computed by taking into account the weights of misclassified instances, rather than just the performance of the misclassified instances. By increasing the weight of misclassified instances following the training of one model, the next model can be made to attend to these instances. The final classification is determined by weighted voting across all the classifiers, where weighting is based on classifier performance (in the AdaBoost.M1 case by the error of the individual classifiers).

AdaBoost.M1

Bagging and boosting combine multiple models produced by one learning scheme. Stacking is normally used to combine models built by different learning algorithms. Rather than simply voting, stacking attempts to learn which are the reliable classifiers using a metalearner.

Inputs to the metalearner are instances built on the outputs of level 0, or base level, models. These level 1 instances consist of one attribute for each level 0 learner - the class the level 0 learner predicts for the level 1 instance. For these instances, the level 1 model makes the final prediction.

During training, the level 1 model is given instances which are the level 0 predictions for the level 0 instances, plus the actual class of the instance. However, if the predictions of the level 0 learners over the data they were trained on are used, the result will be a metalearner trained to prefer classifiers that overfit the training data.

In order to avoid overfitting, the level 1 instances must either be formed from level 0 predictions over instances that were held out from level 0 training, or from predictions on the instances in the test folds, if cross-validation was used for training at level 0.

Stacking can be extended to deal with level 0 classifiers that produce probability distributions over output class labels, and numeric prediction rather than classification.

Whilst any ML algorithm can be used at level 1, simple level 1 algorithms such as linear regression have proved best.

One possibility is to couple a probabilistic classifier (such as naive Bayes) with Expectation-Maximisation (EM) iterative probabilistic clustering. If we suppose we have some labelled training data L and some unlabelled training data U, then we proceed as follows:

Train naive Bayes on L
repeat until convergence:
    (E-step) use the current classifier to estimate the component mixture for each instance (i.e., the probability that each mixture component generated each instance)
    (M-step) re-estimate the classifier using the estimated component mixture for each instance in L + U
output a classifier that predicts labels for unlabelled instances.

Experiments show that such a learner can attain equivalent performance to a traditional learner using < 1/3 the labeled training examples together with 5 times as many unlabled examples.

Suppose that there are two independent perspectives or views (feature sets) on a classification task, then co-training exploits these two perspectives.

We train model A using perspective 1 on the labeled data, and then model B using perspective 2 on the data. The unlabeled data is using labeled using models A and B separately. For each model, we select the example it most confidently labels positively, and the one is most confidently labels negatively, and add these to the pool of labeled examples. This process is then repeated on the augmented pool of labeled examples until there are no more unlabeled examples.

There is some experimental evidence to indicate co-training using naive Bayes as a learner outperforms an approach which learns a single model using all features from both perspectives.

Co-EM trains model A using perspective 1 on the labeled data, and then uses model A to probabilistically label all the unlabeled data. Model B is then trained using perspective 2 on the original labeled data, and the unlabeled data tentatively labeled using model A. Model B is then used to probabilistically relabel all the data for use in retraining model A. This process then iterates until the classifiers converge.

Co-EM appears to perform consistently better than co-training (because it does not commit to class labels, but re-estimates their probabilities at each iteration).

Both co-training and co-EM are limited to applications where multiple perspectives on the data are available. Some recent evidence suggests that this split can be artificially manufactured (e.g., using some random selection of features, though feature independence is preferred) and some recent arguments and evidence that co-training using models derived by different classifiers (instead of from different feature sets) also works.