Data sparseness and multiple inconsistent sets
Rob Freeman
On 9/26/07, David Brooks <d.j.b...@cs.bham.ac.uk> wrote:
> ...van Zaanen's thesis, Section 7.3 [p.101-102] suggests that
> clustering is a viable approach to resolving the following case (from
> ATIS corpus):
>
> show me the _nonstop_ flights
> show me the _morning_ flights
>
> He argues that distributional analysis over the words in question would
> lead us to think that they are in separate classes. My earlier point
> about data-sparsity (especially hapax legomena) is relevant here: if
> these are the only occurrences of the words, how do you determine that
> they belong to different syntactic types? I can't see how a set-based
> view such as that expounded by Rob would resolve this problem, unless
> there is much more data about the words in question.
I agree. I don't think my argument will solve the data sparseness problem.
There may be no absolute solution to data sparseness. There is always
going to be only a limited amount you can say about a word you have
only seen once. (Perhaps ad-hoc generalization gives a slight
advantage, because at the moment we throw away lots of "incongruent"
information because it does not fit. Personally I think the solution
will be some kind of secondary generalization on contexts, whether
this secondary generalization is equated with "meaning" or not.)
But data-sparseness is a different point from grammatical
incompleteness. My point about grammatical incompleteness is only that
there is far more complexity than we have guessed in the data we do
have. I think we need to address this by treating syntax as a search
for patterns, ad-hoc, at run time, rather than trying to summarize all
the relevant patterns in a single complete grammar.
Data sparseness may remain as a problem after we have done this. If so
that is another problem. I'm just saying that the grammatical
incompleteness problem is more immediate, and the solution is obvious.
-Rob
David Brooks
> There may be no absolute solution to data sparseness. There is always
> going to be only a limited amount you can say about a word you have
> only seen once. (Perhaps ad-hoc generalization gives a slight
> advantage, because at the moment we throw away lots of "incongruent"
> information because it does not fit. Personally I think the solution
> will be some kind of secondary generalization on contexts, whether
> this secondary generalization is equated with "meaning" or not.)
Right, but that's the point of syntax, isn't it? I mean, you may
encounter a sentence with a new word in it, and clearly you cannot
relate that word to past experience, but if you have established a
syntactic pattern for interpreting the rest, you can have a guess at
what the word's syntax is, and hopefully what it might mean.
> But data-sparseness is a different point from grammatical
> incompleteness. My point about grammatical incompleteness is only that
> there is far more complexity than we have guessed in the data we do
> have. I think we need to address this by treating syntax as a search
> for patterns, ad-hoc, at run time, rather than trying to summarize all
> the relevant patterns in a single complete grammar.
I happen to think that interpretation relies on many different channels
of information (though "channel" perhaps conveys the idea that they are
necessarily distinct and distinguishable, which is not a necessity), and
that the language faculty is a combination of different analysis
mechanisms - a complex system!
I agree with Iain that we are missing some of these channels when
handling language on machines, but I agree also with Rob that we may not
need all of them - I think there is probably enough redundancy in the
information (when viewed in the right way) to give a good account of
most structure, even in the absence of a decent theory of
meaning/pragmatics.
I don't happen to agree that all sentences are stored verbatim in human
language, but I don't think that should preclude such an approach for
computers. As I said earlier, I think humans balance their effort
between abstracting to a model and storing verbatim when they cannot do so.
What I would like to see is a set of very simple mechanisms for dealing
with language, configured in such a way that they are used in
combination to interpret utterances. The important questions then relate
to what that set should be, how they should be proposed/learned, how
they are applied, etc.
I can fully appreciate why a fully specified formal model might be seen
as the end-goal for such a system, because once you start saying "it
must allow adjacent words to be related; it must allow valency" or
similar statements, I think the natural next step is to try to unify
them into a single model. The problem comes that as you add expressive
capability, you also introduce large numbers of parameters and ramp up
the learning difficulty.
If you are proposing what I think you are proposing - a system where we
have a set of simple analysis tools that we use in combination, and we
extend them only when absolutely necessary to deal with new utterances -
then I'd say we are in agreement about what the goal should be. This is
only incomplete insofar as it allows an entirely novel construction to
be introduced at any point, without redefining a single formal theory.
I'm not sure if this accords with your definition.
How you actually realise all this algorithmically is another matter...
D
Rob Freeman
>
> I happen to think that interpretation relies on many different channels
> of information (though "channel" perhaps conveys the idea that they are
> necessarily distinct and distinguishable, which is not a necessity), and
> that the language faculty is a combination of different analysis
> mechanisms - a complex system!
>
> I agree with Iain that we are missing some of these channels when
> handling language on machines, but I agree also with Rob that we may not
No, David, don't credit me with ignoring other forms of context. As I
said to Iain in messages on Sept. 19 and 20, and elsewhere, my point
is just that when we do consider broader information, we should
consider it in the form of examples, and generalize it in the same way
as text.
It is a beauty of what I am suggesting that we can integrate broader
sources of information naturally with a narrow model in terms of text.
The point I am making, one of incompleteness of generalization,
applies to both and all.
The fact that I equate meaning with organizations of examples doesn't
mean I want to ignore meaning. It just means I'm providing an
objective way to define it, and access it, for the first time.
> I don't happen to agree that all sentences are stored verbatim in human
> language, but I don't think that should preclude such an approach for
> computers. As I said earlier, I think humans balance their effort
> between abstracting to a model and storing verbatim when they cannot do so.
>
> What I would like to see is a set of very simple mechanisms for dealing
> with language, configured in such a way that they are used in
> combination to interpret utterances. The important questions then relate
> to what that set should be, how they should be proposed/learned, how
> they are applied, etc.
>
> I can fully appreciate why a fully specified formal model might be seen
> as the end-goal for such a system, because once you start saying "it
> must allow adjacent words to be related; it must allow valency" or
> similar statements, I think the natural next step is to try to unify
> them into a single model. The problem comes that as you add expressive
> capability, you also introduce large numbers of parameters and ramp up
> the learning difficulty.
>
> If you are proposing what I think you are proposing - a system where we
> have a set of simple analysis tools that we use in combination, and we
> extend them only when absolutely necessary to deal with new utterances -
> then I'd say we are in agreement about what the goal should be. This is
> only incomplete insofar as it allows an entirely novel construction to
> be introduced at any point, without redefining a single formal theory.
> I'm not sure if this accords with your definition.
I'm afraid I don't think it does.
I'm not saying that language is mostly described by a complete
grammar, but can be extended if you come across something odd. I'm
saying every bit of it requires different grammatical perspectives of
the same data, all the time.
This appears to be a really hard idea for people to grasp. Which is
weird, because the possibility, a machine producing strings which are
grammatically incomplete, is hidden deep within computational theory.
Indeed it was this possibility which spurred Turing to investigate
what was computable and what was not.
But we are not talking about that any more. We are talking suddenly
about data sparseness.
Which is something people have been discussing for decades. An
argument framed in terms of the same tired old assumptions of grammar
and how it relates to the world.
On the other hand no-one has explored where grammatical incompleteness
might lead us. How it suggests a natural definition for meaning, for
instance. One which could be integrated with broader sources of
information.
-Rob
David Brooks
> No, David, don't credit me with ignoring other forms of context. As I
> said to Iain in messages on Sept. 19 and 20, and elsewhere, my point
> is just that when we do consider broader information, we should
> consider it in the form of examples, and generalize it in the same way
> as text
I was trying to say "we can do a reasonable job of interpreting
structure with the resources that we /can/ record in corpora" (as
opposed to making an unreasonable requirement of fantastic models of
pragmatics). I didn't mean to imply that you thought other forms of
context are irrelevant.
> It is a beauty of what I am suggesting that we can integrate broader
> sources of information naturally with a narrow model in terms of text.
I was actually arguing for incorporating other contextual sources, and
not against your model, because I believe there to be useful information
in all of it. I am aware that you acknowledged Iain's concerns. That was
what I was agreeing with (and also saying to Iain that I don't
necessarily think we need all the information).
> I'm not saying that language is mostly described by a complete
> grammar, but can be extended if you come across something odd. I'm
> saying every bit of it requires different grammatical perspectives of
> the same data, all the time.
I see patterns in language at many different levels and I think there is
redundancy amongst these levels. One successful application of this has
been in shallow parsing: chunking was devised on the basis that
intonation patterns hold clues to phrase boundaries.
I'm not sure if these are "different grammatical perspectives" to you,
but to me they are different ways of analysing the data. I see /all/ of
them as important to some degree, but I think (as I've said above) that
an approach that integrates most of them will do a serviceable job. I
don't believe that this constitutes a complete grammar to be augmented.
I believe it to be many simple components, interacting. I'd say these
components are fallible behaviours that might be overridden, ignored or
considered with uncertainty. This allows for incompleteness of the
components in terms of coverage (in fact, massively so, since the
components would fail to account for quite a lot) of the language. Maybe
I've misunderstood what "completeness" means, I was under the impression
that it meant "describes all sentences of a language".
However, where we do differ seems to be in when and how that analysis
occurs. You seem to be saying "all the time, starting from scratch each
time", and I'm saying "only if necessary". I think that models are
learned on the fly, and once reinforced they are used in preference to
complete reanalysis from scratch. This is because I think humans are
pretty lazy with language (witness my lazy use of words above).
I don't happen to believe that humans store data verbatim or work from
scratch, so I do have a very fundamental disagreement with you. I
certainly don't believe that all reanalysis is done from scratch every
time, nor do I believe that most alternatives are actively considered in
some intense-effort algorithm. But again, that is not to say that the
model won't work for computers.
> On the other hand no-one has explored where grammatical incompleteness
> might lead us. How it suggests a natural definition for meaning, for
> instance. One which could be integrated with broader sources of
> information.
To start off such an exploration, you need to present something that
does it, show how it works, and allow us to argue the merits. It's quite
difficult to discuss the merits without seeing results, examples, or
other forms of evidence. That's why I asked to see some, because I am
prepared to be convinced, and I am also interested where it might lead us.
D
Rob Freeman
>
> ... Maybe
> I've misunderstood what "completeness" means, I was under the impression
> that it meant "describes all sentences of a language".
No, no.
This is important. It is absolutely central to what I am trying to
say. Incompleteness in this formal sense _does not_ mean some
sentences are left out.
Sentences are not left out. They are used over and over again.
Leaving some sentences out would imply there was a lack of
information. There is no lack of information. Formal incompleteness
means there is _too much_ information, not too little.
That is where the incompleteness comes from, there is nowhere for all
this information to go. The patterns are folded in, and back over the
same symbols. Each symbol in every sentence is used in more than one
pattern. This gives us ambiguity.
Each symbol is used in more than one pattern, but it can only be used
in one pattern at a time. Hence its use is ambiguous, and any single
description of that use is incomplete.
But the incompleteness is one of description. The information is not
incomplete. The information is surfeit. There is much more information
than when the system is merely formally complete.
Completeness, in cases where it applies, just means a language has a
_particularly simple_ formal description, viz. a formal grammar.
Note this harks back to definitions of randomness due to Chaitin and
Kolmogorov. They pointed out that the word "random" can be interpreted
to mean a string is maximally compact, not maximally empty. Compare
this with the popular sense of "random", informed by our classical
preconception that all information must be regular. In that classical
view a random string is assumed to have no information (because the
information is not regular.) Chaitin and Kolmogorov say, no, look,
there is more information. Random strings are _the most compact_
representation for information. (It is just the information is not
regular.)
> However, where we do differ seems to be in when and how that analysis
> occurs. You seem to be saying "all the time, starting from scratch each
> time", and I'm saying "only if necessary".
Yes, we are different. But the difference is not that I am saying
analysis must be done from scratch each time. I'm saying it is done
whenever we say, or hear, something new. It is not quite the same
thing.
In fact my model is lazier than yours. In my model if we never say
anything new, we never do any work. Your model requires us to make all
the generalizations we might need to make, long before we might need
to make them. (And it requires that they fit a particularly simple
form, so that this is possible.)
> I think that models are
> learned on the fly, and once reinforced they are used in preference to
> complete reanalysis from scratch. This is because I think humans are
> pretty lazy with language (witness my lazy use of words above).
In fact experimental evidence confirms the laziness is all of the form
of repeating examples verbatim. It is only when we produce stuff
corresponding to abstractions that work appears to be done. Processing
slows down considerably. There are hesitations, back-tracking.
If language is stored as abstractions, made long before they might be
needed, why don't we produce freely, and efficiently, within the
bounds of those abstractions?
> I don't happen to believe that humans store data verbatim or work from
> scratch, so I do have a very fundamental disagreement with you. I
> certainly don't believe that all reanalysis is done from scratch every
> time, nor do I believe that most alternatives are actively considered in
> some intense-effort algorithm.
This is a major disagreement. But it is only a belief on your part,
and one which should be tested.
We've been testing the hypothesis that only abstractions are stored
for 50+ years, without finding an adequate form for those
abstractions.
It seems only fair that we look at the hypothesis that examples are
stored and generalized ad-hoc, and see where that might lead us.
> > On the other hand no-one has explored where grammatical incompleteness
> > might lead us. How it suggests a natural definition for meaning, for
> > instance. One which could be integrated with broader sources of
> > information.
>
> To start off such an exploration, you need to present something that
> does it, show how it works, and allow us to argue the merits. It's quite
> difficult to discuss the merits without seeing results, examples, or
> other forms of evidence. That's why I asked to see some, because I am
> prepared to be convinced, and I am also interested where it might lead us.
I've been trying to do that. I've given examples where I can. Though
as a suggestion for a direction of research, obviously all the answers
are not known yet. I am only suggesting questions which need to be
asked. Whether you find my initial explorations and arguments
convincing you must agree that the questions deserve to be asked.
Historically they have not been.
I think a major barrier is understanding what formal incompleteness
means. That is where we should focus discussion.
Once this idea of formal incompleteness is understood, it is obvious
what the benefits might be: much more information for one thing. Like
the "random" strings of Chaitin and Kolmogorov, such a model of
language would be a maximally compact representation for meaning, much
more compact than if language obeyed the simplicity condition of being
formally complete.
I can't imagine why we have always assumed natural language should be
formally complete.
-Rob
David J Brooks
Rob Freeman wrote:
> On 9/28/07, David Brooks <d.j.b...@cs.bham.ac.uk> wrote:
>> ... Maybe
>> I've misunderstood what "completeness" means, I was under the impression
>> that it meant "describes all sentences of a language".
> No, no.
well, I can safely say you should discount most of the questions I'm
asking then...
> I think a major barrier is understanding what formal incompleteness
> means. That is where we should focus discussion.
Agreed. Can you post some links to material that would help me
understand the definition of incompleteness you are describing? I
appreciate the examples you are offering, but when I don't understand
things I need to read more...
Cheers,
D
--
David Brooks
Teaching Instructor
http://www.cs.bham.ac.uk/~djb
Rob Freeman
>
> Rob Freeman wrote:
> >
> > I think a major barrier is understanding what formal incompleteness
> > means. That is where we should focus discussion.
>
> Agreed. Can you post some links to material that would help me
> understand the definition of incompleteness you are describing? I
> appreciate the examples you are offering, but when I don't understand
> things I need to read more...
I'm not sure if you will find much from exactly the point of view I'm
presenting. Everything done on incompleteness seems to have been done
from the point of view of abstractions about strings of symbols,
especially as such strings of symbols can be interpreted in terms of
logic.
Very little seems to have been done from the point of view of actual
strings of symbols.
That is perhaps not surprising. Because the interesting strings of
symbols are by definition random, and so naturally hard to think
about!
The idea that our familiar natural languages might be a prime examples
of such strings seems to have been completely ignored.
Anyway, there is a lot about the provable limitations of logic, and
not much about the corresponding power of systems which are not
logical.
I think this is very much by way of the same problem we have when we
think about the full power of a Turing machine. Remember, Turing
showed that in theory a computational machine has all this power, his
Universal Machine. But no-one knows how to deal with it, it is too
powerful. How do you program such a thing? So in practice all
computers are built to implement only logic.
So in fact the best reference is probably Turing, because he was the
guy who took the idea of strings of symbols, which it had been assumed
would submit to logic (but proven otherwise), and showed exactly how
much power they can have.
You can see the full theoretical power of Turing's Universal Machine
again up the top of Chomsky's hierarchy. Ignored because it is too
powerful.
Anyway, everything is from the point of view of logic, and its limitations.
That said, I found this transcript of a talk given by Greg Chaitin in
2000 very readable, albeit once again from the point of view of
limitations on abstract "knowability":
http://www.cs.auckland.ac.nz/CDMTCS/chaitin/cmu.html
(N.B. read it lightly, it is his perspective you want first, not the details.)
For a discussion getting closer to strings you should search on
Kolmogorov complexity (which was independently defined by Chaitin.)
I also found Hofstadter's description of formal systems in his famous
Goedel, Escher, Bach, book very readable, and exceptional for its rare
focus on their untapped power. (E.g. GEB p.g. ? "...any formal system
which is powerful enough contains models not just of itself but of an
infinite number of other formal systems. That is essentially what
Goedel realized.")
I don't know if this is the same as Turing's idea that a Universal
Turing Machine can simulate any other Turing machine.
Basically formal incompleteness is at the core of the theory of
computation. Universally acknowledged, but not much talked about. Any
good text on the theory of computation should at least mention it.
What is important to realize is that a formal system which is
incomplete, like a Universal Turing Machine, is much more powerful
than one which is merely formally complete.
So formal incompleteness means power. (And such a system is
compressed, random as compressed systems are random, and folding a lot
of information into the same symbols, or sentences, over and over
again, as compressed systems fold a lot of information into the same
symbols.)
-Rob
alexs...@googlemail.com
context of natural language.
I understand logic and Godel's theorem and so on, and the traditional
definition of incompleteness, but I don't understand what this has to
do with the topic under discussion. These are mathematical concepts
here, and you can't rip them out of there context and apply them
metaphorically.
Alex
On 29 Sep, 06:44, "Rob Freeman" <gro...@chaoticlanguage.com> wrote:
Rob Freeman
>
> Please give a definition of what you mean by incompleteness in the
> context of natural language.
> I understand logic and Godel's theorem and so on, and the traditional
> definition of incompleteness, but I don't understand what this has to
> do with the topic under discussion. These are mathematical concepts
> here, and you can't rip them out of there context and apply them
> metaphorically.
These concepts apply to all computable strings.
Formal incompleteness is at the top of the Chomsky hierarchy, but it
is in the Chomsky hierarchy.
But see my immediately preceding (logical incompleteness and
"syntactic incongruence") post for a more detailed discussion.
-Rob
alexs...@googlemail.com
the notion of decidability, and computability
makes sense in this context,
to be explicit: the decision problem is "is w in the language", I
still don't know what you mean by completeness.
Could you give a formal definition of what you mean?
If you use Turing Machines then yes, there could be Turing Machines
where you can't decide whether a string is in the language. Are you
claiming that we would have to use a TM where this is undecidable?? Is
this what you mean by incompleteness?
On Sep 30, 7:47 am, "Rob Freeman" <gro...@chaoticlanguage.com> wrote:
Rob Freeman
> the notion of decidability, and computability
> makes sense in this context,
>
> to be explicit: the decision problem is "is w in the language", I
> still don't know what you mean by completeness.
>
> Could you give a formal definition of what you mean?
>
> If you use Turing Machines then yes, there could be Turing Machines
> where you can't decide whether a string is in the language. Are you
> claiming that we would have to use a TM where this is undecidable?? Is
> this what you mean by incompleteness?
Decidability is a lesser condition. However if a theory is incomplete,
clearly it is also undecidable.
To give Janiczak's definition of incompleteness in its broader context:
A Remark Concerning Decidability of Complete Theories Antoni Janiczak
The Journal of Symbolic Logic, Vol. 15, No. 4 (Dec., 1950), pp. 277-279
"A formalized theory is called complete if for each sentence
expressible in this theory either the sentence itself or its negation
is provable.
A theory is called decidable if there exists an effective procedure
(called a decision-procedure) which enables one to decide of each
sentence, in a finite number of steps, whether or not it is provable
in the theory.
It is known that there exist complete but undecidable theories."
It is perhaps the equivalence I draw between incomplete theories and a
Universal Turing Machine which is confusing.
The power of a Universal Turing Machine and incompleteness are
related. If a program were complete, it would be possible to prove it
would halt.
Chaitin, Complexity magazine special issue on ``Limits in Mathematics
and Physics'' (Vol. 5, No. 5, pp. 12-21, May/June 2000).
http://www.cs.auckland.ac.nz/CDMTCS/chaitin/cmu.html
"...if you had a formal axiomatization of mathematics that enabled you
to always prove whether a program halts or not, that would give you a
mechanical procedure, by running through all possible proofs in size
order, to decide whether a program will halt or not. And Turing showed
that you can't do it. His proof, by the way, involves Cantor's
diagonal argument --- all these ideas are connected..."
Anticipating Chaitin I think this is really the power of a random
string to store information.
All of this is looking at the power of different kinds of strings to
store information. That is what is at the heart of theories of
incompleteness and theories of computation. And a random, or formally
incomplete, string, can store the most.
Incompleteness really means ambiguity. And ambiguity means you can
code more information into the same symbols, which become random.
Chaitin characterizes a trilogy of incompleteness results, starting
with Goedel, continuing with Turing's halting problem, and finishing
with his own randomness. He says:
"With Gödel it looks surprising that you have incompleteness, that no
finite set of axioms can contain all of mathematical truth. With
Turing incompleteness seems much more natural. But with my approach,
when you look at program size, I would say that it looks inevitable.
Wherever you turn, you smash up against a stone wall and
incompleteness hits you in the face!"
Think of the discussion about formal incompleteness as a discussion
about capacity of different kinds of strings to store information, and
I think the relationship to computability and the Universal Turing
Machine will become clearer.
-Rob
alexs...@googlemail.com
You say that language is incomplete; and when I ask for a definition
you give this statement below.
What do "truth" and "provability" refer to when you are talking about
natural language? What are the sentences of the formal system that you
claim is incomplete? Are they just the sentences of natural language?
In which case what does negation refer to?
(BTW I think the discussion of complete but undecidable theories is
really off the wall here. If you have a consistent and complete finite
formal system, then you can enumerate all proofs and thus decide
whether anything is true or false easily enough).
Rob Freeman
>
> A final attempt:
>
> You say that language is incomplete; and when I ask for a definition
> you give this statement below.
...which is a definition of completeness.
I'm not quite sure what you are expecting. You seem to think that
natural language is some special case to which formal results do not
apply.
Considered as a formal system, formal results apply to natural language.
Now, there are schools of linguistics which reject the idea natural
language can be considered as a formal system. Functional and
cognitive linguistics spring to mind.
If you reject the idea natural language can be examined as a formal
system, please say so. Then we can examine your premises. I'm
particularly interested in the reasons functional and cognitive
linguistics rejected formal analysis. However, simply pretending not
to understand how there can be any basis for examining natural
language as a formal system, ignoring 50 years of tradition in
generative linguistics, gets us nowhere.
Unless you are really unaware of the generative tradition in
linguistics. In which case we have a bigger problem.
> What do "truth" and "provability" refer to when you are talking about
> natural language?
Exactly what they mean when you are talking about a formal language.
> What are the sentences of the formal system that you
> claim is incomplete? Are they just the sentences of natural language?
Yes.
> In which case what does negation refer to?
A sentence which does not belong to the language.
> (BTW I think the discussion of complete but undecidable theories is
> really off the wall here. If you have a consistent and complete finite
> formal system, then you can enumerate all proofs and thus decide
> whether anything is true or false easily enough).
You must argue with Janiczak about that. I have very little interest
in the decidability of complete theories per se. It just happens to be
the title of the book where Janiczak's defined completeness.
All evidence indicates complete but undecidable theories exist, however.
As Yorick Wilks pointed out on Corpora, there was in earlier years a
considerable body of literature within generative linguistics which
discussed decidability, and as far as I know all the systems
considered were complete.
If there were any systems considered which were not complete I would
like to know, because that is what I am arguing we should consider
now.
alexs...@googlemail.com
> > What do "truth" and "provability" refer to when you are talking about
> > natural language?
>
> Exactly what they mean when you are talking about a formal language.
>
What do "truth" and "provability" refer to when you are talking about
a formal language.
Consider the formal language { a^n b^n | n > 0 }. What does truth and
provability mean in this context?