Eric Baum wrote:
Sorry for my delay in responding... too busy to keep up with most
of this, just got some downtime and scanning various messages:
I don't know what you mean by incrementally updateable, > but if
you look up the literature on language learning, you will find >
that learning various sorts of relatively simple grammars from >
examples, or even if memory serves examples and queries, is
NP-hard. > Try looking for Dana Angluin's papers back in the 80's.
No, a thousand times no. (Oh, why do we have to fight the same
battles over and over again?)
These proofs depend on assumptions about what "learning" is, and
those assumptions involve a type of learning that is stupider than
stupid.
Ben> I don't think the proofs depend on any special assumptions about
Ben> the nature of learning.
Ben> Rather, the points to be noted are:
Ben> 1) these are theorems about the learning of general grammars in a
Ben> certain class, as n (some measure of grammar size) goes to
Ben> infinity
Ben> 2) NP-hard is about worst-case time complexity of learning
Ben> grammars in that class, of size n
These comments are of course true of any NP-hardness result.
They are reasons why the NP-hardness result does not *prove* (even
if P!=NP) that the problem is insuperable.
However, the way to bet is generally that the problem is actually
hard. Ch. 11 of WIT? gives some arguments why.
If you don't believe that, you shouldn't rely on encryption.
Encryption has all the above weaknesses in spades, and plus,
its not even proved secure given P!=NP, that requires additional
assumptions.
Also, in addition to the hardness results, there has been considerable
effort in modelling natural grammars by linguists, which has failed,
thus also providing evidence the problem is hard.
Eric,
You quoted Ben above and addressed part 2 of his response, without
noticing that he later retracted part 1 ("I don't think the proofs
depend on any special assumptions about the nature of learning.") and
therefore, because of that retraction, made the part 2 points irrelevant
to the argument we were discussing.
The result of all that is that your own comments, above, are also
stranded out on that irrelevant subbranch, because I have already
pointed out that all the efforts of the linguists and others who talk
about "grammar learning" are *indeed* making special assumptions about
the nature of language learning that are extremely unlikely to be valid.
The result: you cannot make any sensible conclusions about the
hardness of the grammar learning task.
Here is my previous response to Ben's points that you quote above,
together with his reply:
Ben Goertzel wrote:
>> > I don't think the proofs depend on any special assumptions about
>> > the nature of learning.
>>
>> Richard Loosemore wrote:
>> I beg to differ. IIRC the sense of "learning" they require is
>> induction over example sentences. They exclude the use of
>> real world knowledge, in spite of the fact that such knowledge
>> (or at least <primitives involved in the development of real
>> world knowledge>) are posited to play a significant role in
>> the learning of grammar in humans. As such, these proofs
>> say nothing whatsoever about the learning of NL grammars.
>>
>> I agree they do have other limitations, of the sort you
>> suggest below.
>
> Ben Goertzel wrote:
> Ah, I see.... Yes, it is true that these theorems are about grammar
> learning in isolation, not taking into account interactions btw
> semantics, pragmatics and grammar, for example...
>
> ben
As I said before, since your arguments are based on these same
assumptions, your claims about the learnability of grammars are
completely spurious.
If you can show an analysis that includes the impact of real world
knowledge on the learning mechanism, and prove that the grammar learning
problem is still hard, you might be able to come to the conclusions you
do, but I have never seen anyone show the remotest signs of being able
to do that.
Richard Loosemore
-----
This list is sponsored by AGIRI: http://www.agiri.org/email
To unsubscribe or change your options, please go to:
http://v2.listbox.com/member/?list_id=303
