News for hackers. Stuff that matters.
Re:Douglas Hofstadter: The Shallowness of Google Translate (... by YeGoblynQueenne on Tuesday November 19, 2019 @06:42AM (#21572137)
So I think I really screwed this one up, by assuming a common background. Your comment about aⁿbⁿ being a "simple regular grammar" stuck with me and I realise that we do not have any common background and I should have done a better job of putting my example in context.

It was my mistake to agree that aⁿbⁿ is a "simple" grammar. It looks simple and it's simple for a human.

But, aⁿbⁿ is a context-free language and as such it can only be learned "in the limit", i.e. by a number of positive and negative examples approaching infinity. It cannot be learned by positive examples only, not even in the limit. This is part of Gold's result [1], a famous result from Inductive Inference, the field that essentially predated Computational Learning Theory. Gold's result was that anything more complex than a finite language can only be learned in the limit and anything above regular languages requires both positive and negative examples.

Gold's result had a profound effect on machine leargning [2] and was a direct cause of the paradigm shift that came with Leslie Valiant's paper that introduced PAC Learning [3]. Valiant's paper placed machine learning on a new theoretical foundation where it's acceptable to learn approximately, under some assumptions (particularly, distributional consistency between examples and true theory). This is how machine learning works today and this is why machine learning results are accepted in scholarly articles, not because they are useful in the industry or make nice articles in the popular press.

Where aⁿbⁿ comes into all this is that it's one of a group of formal languages that are routinely used to assess machine learning algorithms. Keeping in mind that grammars for CFLs are impossible to learn precisely from finite examples, the point of the exercise is to show that some learning algorithm can learn a good approximation that generalises well from a small number of examples.

This is how formal languages are used in neural networks research also. For a recent example from the literature see [4].

The example in my comment shows instead that our algorithm can learn aⁿbⁿ precisely, not approximately, from only three positive examples. This should be surprising, to say the least. Gold's result says that this should not be possible, at all, ever, until hell freezes over. Why it is possible in the first place is another long discussion that I was hoping to have the chance to make here, but instead I allowed myself to be drawn into an adversarial exchange I should have avoided.

To put an end to it: neural nets have produced some spectacular results, and I don't want to discount them, but it is important to understand what those results mean, in the grand scheme of things. The fact that there is a machine learning paradigm that outperforms neural nets on a very hard problem (simple as it may look) means that the same paradigm may outperform neural nets on those other things that they do so well, like image recognition and speech recognition. Or it may just mean that different learning paradigms have different strengths that must somehow be combined (a more popular view for sure).

Anyway, sorry to spread noise and confusion in this thread when my goal was to do the opposite. I have a rubbish way of communicating.

_____________________

[1] Language identification in the limit:

https://www.rand.org/pubs/research_memoranda/RM4136.html

[2] And a few other fields besides. Noam Chomsky used Gold's result to argue for a Universal Grammar enabling humans to learn natural languages. This all is really groundbreaking stuff and a real shame that it's not more widely known in machine learning circles.

[3] A theory of the learnable:

https://web.mit.edu/6.435/www/Valiant84.pdf

[4] LSTM networks can learn dynamic counting:

https://arxiv.org/abs/1906.03648

There are no comments on this comment yet.