An interesting paper on unsupervised knowledge

Data-driven models are much sensitive to the gengre and domain of training data, while the use of knowledge or unsupervised data may improve the robustness of them. This paper is worth noticing in the area.

Somewhere between dynamic programming and beam search

Recently forest based reranking has gained more attention. Instead of reranking at the root of N different parse trees, the decoder can rerank local candidates at different nodes that are generated during the dynamic programming process. This method combines some advantages from dp (i.e. memoisation) and beam-search (i.e. faster decoding).

Thinking about the multiple beam decoder I used for joint segmentation and tagging, I find some similarities in thinking. Our decoder is not a reranking algorithm, it can be viewed as a reduced version of building a dynamic programming chart: instead of filling every cell in a chart, we only keep N-best items for each character. This is also somewhere between beam-search and dynamic programming.

There is always a balance between efficiency and accuracy, particularly when we want to use discriminative training with wide-coverage features. The disadvantage of using a beam, as one can argue, is the loss of optimality. But the effectiveness of NLP is not totally dependent on mathematics in decoding; I think the model structure is much more important here. As I always reckon - we don't have to do a full chart parsing to understand sentences anyway.

More examples showing semantic ambiguities of Chinese sentences

饭我还没有吃。
Food I haven't eaten.

我饭还没有吃。
I food haven't eaten.

The first example can be understood with topicalisation: the object food is taken to the beginning of the sentence, and became the topic. The second example is hard to understand from a structural point of view. If the word taken to the beginning must be an object, then the semantic of the sentence would be some food eating me!

This is definitly hard for a pure syntactic grammar to handle -- at least for the not-so-lexicalised ones.

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.