Friday, September 7, 2007

Reactions to Class 2 and to reading for Class 3

The title says it all....I've posted some comments on the initial 'Reactions to Class 1 and Reading for class 2' and simply didn't think of initiating the post.


sarah a. goodman said...

So here are the comments made on another thread. They should go here, however. I've just copied and pasted:

So I've just read the Turing Machine article. I've got a question about the halting machine defined near the end of the article. Take this passage:

This composed machine, call it M, halts if the machine with the input code n does not halt on an initial tape containing n (because if machine n does not halt on n, the halting machine will leave TRUE on the tape, and M will then go into its infinite sequence.) and vice versa.

Is there a typo here? It seems to say first that M halts if n does not halt, and then in the parenthetical say that M will not halt if n does not halt. I didn't think this was the ad absurdum part of the reducutio ad absurdum, that that part was reserved for the following paragraph about running M's code on M rather than n's code.

Any thoughts?

September 7, 2007 5:03 PM

So now I've read the Church-Turing article, and I found reference to something that's been nagging me about so-called computational modeling of human cognition -- the mind existed long before a modern computer. The computer as we know it could have taken different forms, organized along different architectures, languages, operations, and so on. So why do we try to delineate parallels to familiar technology in an effort to replicate what the brain does, like so-called Phonological Learner I once read about? We could be disastrously wrong in that, and any such enterprise, to me, just seems misdirected. Technology may be able to approximate human cognition in using operations completely distinct from neural analogues, but replicating cognition is a completely different story.

Maybe I've misinterpreted what some people are attempting, I'm not sure. Maybe neuroscience should lead the way in this respect, and technology could simply catch up at some later date.

bdillon said...


There are a couple of things here. One, the fact that the mind existed before the computer really says nothing about how appropriate it is to model cognition as a computer; I'd gather that airplanes make use of lift in flight in a way similar to birds despite the fact that birds have been around far longer. Doesn't mean we can't talk about the same principles at work in bird and airplane wings.

Second, I don't think anyone is saying the mind is a computer in a way that parallels your desktop's architecture to the very last transistor. In fact, it's a lot more abstract and general than that: the claim is that various parts of cognition make use of a formal symbol manipulation in a way similar to the way that (theoretical) computing machines do. We try to find parallels with familiar technology because it is just that: familiar. Both the abstract notion of computation, and the desktop you own, have well defined properties that are very useful in providing a metaphorical framework for formalizing cognition. I don't think it's misdirected at all to try and see how far you can get with familiar, well-understood tools.

Also, if I'm not mistaken, even among hardcore proponents of the CTM, no one believes that all of the mind can be modeled in this way.

Tim Hunter said...

I thought I would try to clear up any confusion which may have arisen from the discussion about functions and relations I started last week, now that we've had the terminology formally introduced.

The two things I wanted to point out were just:
1. A Marr level one description of a process is usually taken to be a function (eg. from an array of light beams to a mental representation of the seen part of the world)
2. The relation specified by the language faculty with sounds as its domain and meanings as its range, is not a function; it's (only) a relation

So I don't think we can just put together the idea "We want to analyse language" with the idea "These levels Marr came up with are interesting/useful" and ask ourselves the question "What's the level one/two/three description of language?" Marr's levels are for describing processes, and language is not a process. Processes can be most abstractly characterised as functions, i.e. Marr's level one. Of course, there are processes that the brain carries out which linguists sometimes get interested in, like figuring out what a person means when he/she says something. This can be characterised as a function, because it's a process. But its domain is not just the set of sounds, because it's got all sorts of non-linguistic input too, like knowledge about the speaker. The relation specified by the language faculty between sounds and meanings will no doubt be a handy thing to be aware of when figuring out what a person means when he/she says something, but it's not "what's getting computed".

As Philip pointed out, for any relation from A to B there's a corresponding function from AxB to {0,1}. So, if you like, you can take the relation from sound to meaning specified by the language faculty, and create the function from (sound,meaning) pairs to {0,1}. This emphasises the fact that we shouldn't talk about just "whether language is a function or a relation", because there are no functions or relations until you specify a domain and a range: if you take sounds as your domain and meanings as your range, then the language faculty isn't going to give you a function, only a relation, but if you take (sound,meaning) pairs as your domain and {0,1} as your range, then there's a pretty obvious function.

This is exactly why we shouldn't just jump into talk of Marr's levels unless we have a domain and range in mind (i.e. what the process is going to start with and what it's going to end with), because until you do that you don't have a function. Of course, if we have the relation from sounds to meanings, we can come up with the function in the last paragraph with {0,1} as its range, which brings it into line with a Marr-style analysis, but by choosing that function you're choosing to do a Marr-style analysis of the process of giving a perfect grammaticality judgement (something which we may or may not actually be able to carry out, but so be it), and not of any other process. There's no way to "transform" the language faculty's relation from sounds to meanings into a Marr-analysable thing without committing to a particular task. So in this sense I don't think it's a complete red herring to note that the relation with sounds as its domain and meanings as its range is not a function.

sarah a. goodman said...

I suppose the airplane-to-bird analgoy is apt here, but I also suppose I don't think computational cognitive modeling should be done in a vacuum, as the point would simply be lost on me. For instance, someone at ULCA attempted a Phonological Learner that I can't really say actually went anywhere. If the goal was to show that Windows 2000 could guess that s->es/{x,ch..}_, then fine, but would this experiment actually benefit kids with language disablities or give insight into what it is that we as humans do at a young and tender age? Probably not. If the results were paired with neurobiological data, or data on what parts of the brain are used to learn, or what it means to learn, or something a bit more foundational than the standard handbook to a C compiler, then maybe I'd consider it having attained some prize closer to its stated goal. It might still be useful in its current form--say for aiding the induction of morphophonemic rules for use in an MT engine, but I wouldn't call it a tool for the psychological community.

Second, while we can talk about how both a bird and an airplane wing make use of lift and areodynamics, we can't say that a bird's wing functions in the same way that its artificial counterpart does. One flaps and the other does not, for starters. I just fear that the second statement is what's floating around out there when it comes to cognitive modeling--that it's not just the abstract principles applied in different incarnations or in fundamentally different physiological implementations, but rather there's something about how a computer (as we know it) that's functioning as a nearly identical process or manner in the human mind. I don't think we're even close to figuring out how thought is evoked, and, as I've stated, the computer could have been realized in a different form and functional capacity. Claiming that one and the other might be similar is still a bit of a leap, in my opinion.

Philip said...

I want to push a little more deeply on TimH's assertion that "Marr's levels are for describing processes, and language is not a process". It seems to me that one could just as easily take the same stance about vision, e.g. vision is not a process, it's, say, a relation between raw inputs (pixels) and internal representations of objects.

One thing you'll have seen from reading about Turing machines is that computations are characterized in terms of inputs and outputs; Marr's process-oriented stance is no accident. Certainly, as you point out, this can still be used just as well to characterize a relation, e.g. characterizing addition as function f from triples of real numbers RxRxR to {0,1}, so that f(2,2,4)=1. But if the goal is modeling an observed phenomenon, e.g. trying to understand the underlying principles of a cash register by looking at cash register transactions, I find it a whole lot more natural, at least in the first instance, to create a more direct mapping between the observed phenomena and the computational abstraction. E.g. thinking of addition as a function whose range is the real numbers -- if someone's already rung up 5 dollars in purchases, and they add a candy bar that costs a buck, 5+1=6 is more intuitive than +(5,1,6)=1 even if they're formally equivalent.

All that said, I think you're exactly on target when you observe that taking Marr's approach -- and, I would argue, taking a computational approach at all -- requires "committing to a particular task". But I think it's worth discussing, rather than assuming, that the task to choose is mapping from (PF,LF) pairs to Boolean values. The characterization of capital-L Language as a relation between strings and meanings strikes me as reasonable, but certainly not the only possibility worth considering.

Tim Hawes said...

Sarah said, “…it's not just the abstract principles applied in different incarnations or in fundamentally different physiological implementations, but rather there's something about how a computer (as we know it) that's functioning as a nearly identical process or manner in the human mind.”

I think that this feeling stems from the mutual misunderstanding, in many ways along the lines of the “Misunderstanding of the Thesis” discussion in the Church-Turing article. Much of the misunderstanding follows from different uses from “computer”. Like Brian said, no one is claiming that the desktop is a perfect parallel to a desktop computer. But, that doesn’t stop people from getting carried away with their analogies, and saying things that could be taken to be makeing this claim.

That aside, I don’t think attempts at cognitive modeling are only useful as something that you can plug into an engineering problem. If someone makes a model that replicates some observed process, what they’ve shown is that processes can be achieved in the way that they have done. Further analysis of that model (for example of the time scale that the process operates on, or where the major changes take place), then, lets you decide how good a fit that model actually is for the process it replicates. I think that the potential differences in the process are far more important when judging the quality of a model than the differences in the hardware. Even functional differences in hardware don’t worry me that much, unless you start talking about differences in computational power.

All this also has to do a bit with what your question is. If you want to know what it takes to “fly like a bird” (taken literally), you are going to be going down the wrong road studying planes. But, if you want to know what it takes to fly, planes are a perfect model to use. Similarly, if your question is “how can you do language like a human brain” computational models definitely deserve some hesitation. But if your question is “how can you do language” there is nothing wrong with using computational models. Of course, you could also argue the two can’t be separated…but I’m not ready to agree to something like that.

Tim Hunter said...

Philip wrote: "It seems to me that one could just as easily take the same stance about vision, e.g. vision is not a process, it's, say, a relation between raw inputs (pixels) and internal representations of objects."

We certainly can talk about the declarative, non-procedural knowledge underlying vision if we want, and if we did this I think we'd be talking about the aspect of vision which most closely parallels the (declarative, non-procedural) sound-meaning relation in language. But Marr is specifically talking about how we use that knowledge to map an array of beams of light to mental representations of objects, and this is the process which he seems to be calling "vision" (and what he applies the three-level analysis to). In some of the discussion he/we might overload the term "vision" to refer to the underlying declarative, non-procedural knowledge too. That doesn't cause too many problems in itself because he's specified which process/task he's talking about, so when he seems to be talking about "vision, the process", we know he means the process of mapping an array of beams of light to mental representations of objects, and when he seems to be talking about "vision, the knowledge/faculty", we know he's talking about the declarative, non-procedural knowledge. The danger I'm trying to point out is that we shouldn't overload the term "language" in this way, unless we're prepared to commit to a particular task, the way Marr committed to the task of mapping an array of beams of light to mental representations of objects.

Philip wrote: "taking Marr's approach -- and, I would argue, taking a computational approach at all -- requires "committing to a particular task". But I think it's worth discussing, rather than assuming, that the task to choose is mapping from (PF,LF) pairs to Boolean values."

I totally agree with the first point, but I didn't mean to suggest that we should choose one task where language seems to be involved, and take that task/process to be all there is to study. Far from it! I don't think there's really a question of what "the task to choose" is; there's a bunch of interesting tasks, each one amenable to Marr-style analysis.

So-One said...
This comment has been removed by the author.
So-One said...

Input-output, domain-range, and sound-meaning, respectively, all seem to be interchangeable terms in our discussion so far of language.

This is not the model of the current theory of syntax if one reads carefully, however. What if the relation of sound and meaning exists because BOTH are the OUTPUTS of the system? This is depicted in the Y-model. Can someone confirm/clarify for me whether this is the Boolean version of the story? I see that the (sound, meaning) pair is the domain and the Boolean values {0, 1} the range, so perhaps in technical computational terms, perhaps the (sound, meaning) pair should be called the input rather than output – but is the idea the same? Or, is this difference from the dual output version, as characterized by the model of syntax, a problem? I admit that with this dual output view or Boolean value output version of language as a function, my concerns about directionality should no longer be relevant. In that case, my worries would have to shift towards the unification problem of it all in processing – in the algorithmic side of things.

Even if we were to agree that language is the function that gives Boolean values as outputs for a (sound, meaning) pair, I would still want to know what happens at one level of computation before – what was the computation behind the generation of the (sound, meaning) pair itself. I would also want to know whether they were generated as a pair (like a coin with two sides) or whether there are separate computations behind the generation of each item.

Both outputs (let’s stick with the Y-model view instead of using the set-theory terminology for now since my confusion about their interchangeability has already been explained) must be in a form that is interpretable by the interfaces – the bare output constraints. Syntax may provide the relation between sound and meaning by either generating both or by generating a structure that is interpretable by both ends of the interfaces. My description of how these are not the same scenarios is to give an analogy of a construction company whose task is to build buildings A and B which are basically adjoined (the point of juncture being a system-internal hinge) and it has to make the buildings stable given the landscape. In other words, the interface constraint is the ground the buildings are built upon. Also, because both buildings are built together, one does not exist without the other – like the two sides of a coin. There could be another construction company whose task is to build a pedestrian bridge between the two buildings that were built by different construction companies. The interface constraint for this task is the shape of the buildings that are already there. These buildings can exist independently of each other, but the task of building the pedestrian bridge is definable because both exist at the same time. If these are two of our options for the computational task, isn’t it important to know which is the object of study – and thus to state it as a goal to find out?

Today’s characterization of narrow syntax takes at least building B (meaning) to be something that must be built in the task. This is built out of a numeration, and more specifically, out of sub-numerations. Thus the computational task is defined as taking a very well organized list of morphemes and to combine them (through Agree, Merge) into a hierarchical structure. In this description, there is no discussion of sound. Perhaps it just so happens that this resulting structure has a hinge to connect it to sound. Both the building and the hinge are important objects of study – if they are different objects of study.

One has to start somewhere – with a set of assumptions that can be tested and revised. Intuition does have a place in science because it provides us with a place to start - an assumption that should not be immune to the scientific method.

What are our assumptions about what language is – in this class at least – going to be? Everyone seem to have their own while all claiming to study the same thing. What’s the point of debating and disagreeing when it turns out people are studying different things?

Chris said...

I'm going to break from the current discussion here a little bit and post some comments about complexity analysis (big-O notation, etc), since it seems to me that as linguist the resource requirements underlying linguistic computations must be of some interest.

The first point I wanted to make is to ask whether big-O is necessarily the best kind of analysis we can do for linguistic theorizing. Big-O says what the absolutely worst kind of input will do to the system. For example, the intersection of two finite state machines is an important and well understood algorithm (and conceivably one that might be implemented in the brain for a task such as word recognition). In its worst case, its running time and memory usage are exponential in the number of nodes, O(2^n). However, in many cases, intersection can occur much more efficiently (often linearly in the number of nodes/arcs in the smaller of the two machines), and therefore the exponential label is perhaps misleading. Would average case running time be more appropriate for us to consider?

The second point I wanted to make is that Turing machines have always been fascinating and somewhat mysterious to me since they separate the question of computability from the time and space that it takes to compute something. There is an interesting variant of the classical Church-Turing thesis that starts to unify the two. The Extended Church-Turing thesis states that if some machine (an abacus, a pocket calculator, a tinker-toy tic-tac-toe player, perhaps the mind) can compute something given input of length n in time f(n), then a Turning machine can do it in at least f(n)^k where k depends on what is being computed, not n. This is interesting, because it says that no matter what the function that is computed by Turing-equivalent machine, a Turing machine can do it in a bounded length of time. It is even more interesting because it emphasizes the effect of the computational primitives on resource requirements. What may be an easy computation with one system (multiplying by 2 in binary) may be difficult in another (multiplying by 2 in Roman numerals). This strikes me as significant, since it seems to me as linguists we spend a lot of time worrying about the level in the Chomsky hierarchy of particular features of language and not enough worrying about what the computational primitives of the system are. The algorithms that operate over structures at any level in the Chomsky hierarchy might be potentially exponential (as demonstrated with the intersection example in the previous paragraph and suggested by the ECT in this one), so maybe a better question for us is to explore what the computing primitives of the symbolic machines that make up the linguistic faculty are, since they will ultimately have at least as much to say about the resources required by a given computation.