The perceptron algorithm training

A question concerning the perceptron training is how many iterations over the training examples gives the best output accuracy.

Some criteria can be used. For example, the number of iterations can be fixed from the development tests. Alternatively, a set of examples can be taken out of the training data from the test set, and using those for testing and the rest for training, the number of iterations determined by the corresponding observations. Still an alternative is to check the training error. When the training error is below a certain proportion of the training data, the learning process stops. The last method assumes that the perceptron model converges.

I have seen some example where the first method is far from optimal. This happens in a case where the size difference between the development data and the test data is huge. It seems that the second method is a comparatively sensible choice.

some examples to illustrate that Chinese is more semantic than syntactic

Try to do the following sentence comprehensions:

(1.1) 我挠的他很痒
Who is itchy? (a) 我 (b) 他

(1.2) 我找的他很苦
Who is anxious? (a) 我 (b) 你

(2.1) 我们大胜对手
Who won? (a) 我们 (b) 对手

(2.2) 我们大败对手
Who won? (a) 我们 (b) 对手

(3.1) 他高中，我本科。
What verb is omitted?

(3.2) 他宝马，我夏利
What verb is omitted?

(3.3) 他志强，我志国
What verb is omitted?

(4.1) 他吃面包
What did he eat?

(4.2) 他吃饭馆
What did he eat?

(5.1) 我们擦玻璃了
Who did what to who?

(5.2) 地板擦干净了
Who did what to who?

What happens when there are a lot of features

For discriminative structural prediction, the system might have quite a lot of feature templates. Do more features increase overfitting, or do they reduce the accuracy given limited training data because they make the model harder to converge? This appears to be an interesting research question.

I doubt whether the maximum entropy (log-linear) methods and the perceptron algorithm will be the same, but my work has been primarily focused on the perceptron learning.

I have two observations:
1. Some preliminary results by online learning show that more features can reduce the accuracy on the first training iteration, but "catch up" with more iterations.
2. When the number of features reach certain levels, additional features will not help further improve the accuracy. The added features may not be good enough, but it still looks possible that a system does have a capacity for features - at least with limited examples. This means that many subsets of features can do as well as all the features.

The following statement is absolutely true for the perceptron, but not necessarily true for maximum entropy learning algorithms:

A very specific feature will increase overfitting. One extreme example here is using the complete output as a feature. Such features will be sufficient to make the training converge, for they remember the output for each training input. However, it is apparently useless when testing. A more detailed example might be the feature [word trigram and current tag] for tagging.

Discriminative learning according to the loss function

Many machine learning methods reduce to the constraint miminization problem. Examples include the maximum entropy model, the conditional random field, the support vector machines, the maximum margin markov network and the margin infused relaxed algorithm, just to name a few. Most of the problems can be solved by lagrangian multiplier.

For the largin margin learning methods, the learner tries to find the parameters that maximises the score difference between the correct answer and all the incorrect answers. It's the same for both structural prediction and simple classification. In the implementation, the margin (i.e. score difference) must be defined. It can be simply 1, as the classic SVM does, or other functions, especially in structural prediction. Here is a good tutorial.

The interesting idea from the tutorial is viewing many discriminative learning algorithms as special loss minimisation problems - with different loss functions.

Maximum entropy modelling

Entropy is the measure of the uncertainty of some information. The bigger the entropy is, the more uncertainty it has, and therefore more bits are needed to encode such information with binary encoding, for example.

It’s worth noticing that entropy is also the measure of how uniform a distribution is. This is not contradicting the above conclusion. The less uniform a distribution is, the less uncertain it is. In the extreme condition, {0, 1} -> {0, 1} mapping always outputs 1. 0 bit is needed.

Maximum entropy models study the conditional probability distribution p(y|x). Given a set of training examples (xi, yi), where xi are observations and yi are outputs, it tries to find a distribution p behind, by supervised learning.

A unique property of maximum entropy modelling is the use of features. Instead of computing p(y|x) directly from the examples, it maps the training data into a set of features. Each feature indicates the occurracnce of a certain pattern in the data, and a feature from (x, y) can be written as f(x, y). The motivation of features is easy to understand - instead of naive Bayes counting, features are a means to explore deeper the factors behind the observed data. As a natural consequence, we assume that the frequency of features in the training data is the same as the feature frequence in the model. This is the constraint equation for maximum entropy models.

Given the constraint, the model finds the distribution p(y|x) that gives the highest conditional entropy to corpus. The math deductions including the lambda exponential form of p(y|x) can be found from (berger, 96)

Generative models and discriminative models - comparison

Given a set of samples (x1, y1) ... (xk, yk) , try to find a model behind them by supervised learning.

Both the generative and the discriminative models assume that there is an underlying probability distribution P(x, y) that generates the samples, however,

- The generative models try to find exactly the distribution P(x, y)
examples: Bayesian models
structural prediction: find a probabilistic model that simplifies P(x,y), usually by the chain rule / Bayes theorum / Independence assumption.

- The discriminative models find some distribution with low error rate on the training examples
examples: support vector machines
structural prediction: find a feature vector representation of the structures of Y.

Daume III (2006) gave an example where a generative model makes much worse error expection than a discriminative model (chap 3).