Machine learning and generalisation

When are machines (read computers) said to learn ? 数据挖掘工具

Machine learning is concerned with computer programs that allow better performances as they gain experience. Hence, lauching twice the same program might give different results if a learning process has taken place. Such software provides with betters answers as more information is fed into it. As for humans, computers can either learn 'by heart', like short-term learning people tend to resort to before exams, or they can learn 'in the long term', being able to infer new knowledge from known facts. This is called generalisation. 数据挖掘工具

By-heart learning 数据挖掘研究院

Computer learn 'by heart' when they need new information to address new situations. The typical example is the anti-virus software. Anti-virus software are better as more information, in this case virus signatures, is provided. When the software downloads, periodically, news virus signatures, or definitions, it is able to spot and eliminate more and more viruses. It is therefore learning in the sense we juste defined.

It is however learning 'by heart' as it can now only detect viruses for which a signature was provided. It is not able to detect and remove a new virus without downloading its corresponding signature file. It the signature is known, the virus will be detected 100% of the time. 数据挖掘工具

Other examples of by-heart learning are the auto-completion capabilities of most web browsers, and Windows' Start menu, which proposes a list of frequently used softwares, depending on the user.

数据挖掘实验室

Generalisation

数据挖掘研究院

Computer programs are said to generalize when they are able to deal with new situations without the need for new information. The typical example is the anti-spam software. Spam filters get better and better as more examples of both spam and legitimate emails are provided to them, increasing their percentage of correct classification. 数据挖掘研究院

Spam filter are indeed able to generalize the concept of spam. When a new email arrives, most probably different from any other email already received, the spam filter estimates the degree of probability that this particular email is a spam, without the need for a specific signature file describing all possible spam messages, as is the case with viruses. It is therefore sometimes making mistakes, marking as junk a legitimate email, or conversely marking as legitimate a spam email. But mistakes get fewer as more and more example are provided. 数据挖掘交友

Other examples include recommendation systems for online shops, and optical character recognition software. 数据挖掘论坛

Reasoning by analogy and inductive reasoning 数据挖掘论坛

Generalisation corresponds thus to the process of reasoning by analogy, and inductive reasoning. New elements can be processed even though the software was not told explicitely how to process them. Spam filters compare new emails with past email which have been confirmed by the user as spam, and decided, based on the similarities, to classify the new email as junk or not. Spam filters furhtermore build dictionaries of words that often appear in spam messages and use this dictionary, which can be different from one user to another, to estimate the degree of 'spamness' of an email.

Conclusions

数据挖掘工具

By-heart learning is only concerned with reasoning by analogy, but only with situations which have already been encountered, or which have been explicitely described.

数据挖掘研究院

Generalisation is thus a very interesting ability to achieve, but also, of course a very challenging mathematical and computational problem. 数据挖掘论坛

Interested readers can refer to the following books: 数据挖掘论坛

machine learning in general : Machine Learning, Tom Mitchell, McGraw Hill, (1997)generalisation : Statistical Learning Theory, Vladimir Vapnik, Wiley-Interscience, (1998), 数据挖掘交友