Formal cognitive reasoning

As a book selector for my university library, I find out about numerous books that would remain unknown to me otherwise. One interesting book which we recently bought is Cognitive Reasoning: A Formal Approach by Anshakov and Gergely. This book presents a massive effort to systematize a formal logical framework which is seriously intended to model cognitive reasoning. It is, in one sense, an amplification of the typical efforts to devise a "logic of knowledge and belief" within AI, but this description does not really do any justice to the efforts documented.

The book relies on "a long prehistory" of work carried out in Russia and Hungary over many years, founded on the plausible reasoning methods of so-called JSM systems (named after John Stuart Mill because of the close affinity with his logical proposals). The formal logics underlying the technique are versions of "pure J-logics." These are multi-valued logics with two sorts of truth values called "internal" and "external." The external truth values are just the usual two, but the internal truth values can be a very rich (countably infinite) set. The logics contain J-operators, which are characteristic functions of subsets of the internal truth values. All this machinery is used to devise a sophisticated logic of knowledge updating which "permits one to describe the history of cognitive processes." The objective is to model the reasoning process which moves a cognitive agent "from ignorance to knowledge," and so the system is a dynamic logic as well. The formalism also involves a new kind of syntactic entity in the logic, a "modification inference" which can add new formulae by nondeductive rules and thereby modify constituents which are already established in the inference.

I have not finished reading this book, but I believe that it is very important for anyone interested in logic-based AI or cognitive science. It provides a rich and technically interesting set of formal methods for seriously trying to model cognitive reasoning.

Robot language acquisition

I discovered an interesting research program going on currently in the Adaptive Systems Group at the University of Hertfordshire, UK. A representative paper is "An integrated three-stage model towards grammar acquisition" by Yo Sato and colleagues, that appeared in the 2010 IEEE International Conference on Development and Learning. The paper documents an experiment in "cognitive robotics" where a robot is situated in a realistic language-learning environment.

According to the abstract, "the first, phonological stage consists in learning sound patterns that are likely to correspond to words. The second stage concerns word-denotation association. . . The data thus gathered allows us to invoke semantic bootstrapping in the third, grammar induction stage, where sets of words are mapped with simple logical types." This work is especially interesting to me because the grammar induction uses a semantic bootstrapping algorithm related to one which I developed, and published in 2005 (Journal of Logic, Language and Information).

In a discussion following my previous post, I offered the opinion that as computing power increases, we will (I hope) see more efforts to implement theoretically inspired learning algorithms that are quite intractable. This robotics paper represents one such effort, which I am very pleased to see. Yo Sato tells me that they are now looking at incorporating the improvements I have recently made to the original semantic bootstrapping algorithms. It's always gratifying to see an application inspired by my theoretical developments, since this is really why I pursue the work, but I am not sufficiently capable or interested to carry out the applied work that is then called for.

Niyogi's analysis of Principles and Parameters learning

In this post I will summarize Chapter 4 of Niyogi (1998) The Informational Complexity of Learning. In it, Niyogi emphasizes the importance of going beyond theoretical learnability when analyzing a grammatical paradigm. "One also needs to quantify the sample complexity of the learning problem, i.e., how many examples does the learning algorithm need to see in order to be able to identify the target grammar with high confidence."

He sets his sights upon the Triggering Learning Algorithm, put forth by Gibson and Wexler as a learning scheme for the grammatical "parameters" within the Chomskyan Principles and Parameters framework. For those unfamiliar with the background, this is a theory of language that posits a Universal Grammar underlying all natural languages (the principles), and then a finite set of variable parameters which account for the differences among languages. The "parameter setting" is really the sole learning task for the developing child on this account.

I think that in the beginning, this theory was put forth in an effort to address the supposed "poverty of the stimulus," with the hope that the resulting learning problem would be tractable, even easy. Niyogi, however, manages to demonstrate that Gibson and Wexler's assumption of the existence of "local triggers," i.e. a path through the parameter-setting space from the initial hypothesis to the target, is not even sufficient to guarantee learnability at all (though it was believed sufficient by Gibson and Wexler), much less tractability. He further demonstrated the surprising theorem that, for all its carefully thought out design, the Triggering Learning Algorithm is less optimal than a random walk on the parameter space!

At the time of Niyogi's writing, he judged that the Triggering Learning Algorithm was a preferred explanation of language learning in psycholinguistics. His results should really have killed it, but as far as I can see they have had no such effect. In fact, Google Scholar finds only 12 literature citations of his entire book, most of which are due to the author himself. This is hardly a flurry of activity; only one other author writing on problems of natural language learning appears to be among the citations.

Pregroup grammars' generative capacity

There has been a movement within mathematical linguistics toward Lambek's pregroup grammars, which were mentioned in one or two earlier posts. The book Computational Algebraic Approaches to Natural Language (Casadio & Lambek eds., 2008) collects a number of papers on this subject, and this is recommended for those who wish to catch up on the trend. The book is also available as a free download directly from the publisher Polimetrica. Myself, I am somewhat ambivalent about the framework, but there does seem to be some confusion in the literature about its generative capacity.

The first paper in the mentioned volume is "Pregroup grammars and context-free grammars" by Buszkowski and Moroz. This paper relies on a result by Buszkowski (published in the Logical Aspects of Computational Linguistics proceedings in 2001) showing the weak equivalence between pregroup grammars and context-free grammars. Yet Greg Kobele and Marcus Kracht did a paper (unpublished) showing that pregroup grammars generate the recursively enumerable languages. I asked Greg about this, and he explained (as does his paper with Kracht) that key elements of the Buszkowski result are excluding the empty string from the context-free languages, and using only free pregroups. Kobele and Kracht showed, on the other hand, that by allowing all pregroups and also allowing the empty string, one achieves Turing-equivalence, generating all r.e. languages.

This is all esoteric stuff which is nevertheless important to have nailed down when one is working with a grammar formalism. Another issue with pregroup grammars is that they deny the existence of syntactic constituents in the normal sense. But that discussion has to wait for another post.

Russell's "No Class" theory

A fine paper by Kevin Klement on Bertrand Russell's "No Class" theory is published in the Dec. 2010 issue of the Review of Symbolic Logic. Klement outlines a sympathetic reading of Russell's attempts to eliminate actual "classes" as objects in his logical theory, showing along the way how the many high-profile criticisms of Russell (which were mostly swallowed whole by the community) fail to dislodge the No Class theory on any philosophical grounds.

Without going into technical details, Russell tried to define "propositional functions" as being open sentences of logic, such as a predicate applied to a variable as in Mortal(x). While a complete logical sentence such as Mortal(Socrates) makes the statement that Socrates is mortal, the open sentence Mortal(x) has usually been construed as equivalent to a function which maps things (substituted for x) to the statement that they are mortal. Because such a function essentially classifies things according as the resulting statement is true or false, it ends up with classes. Russell wanted to see such an expression as not involving a function or class literally, but rather as just an open sentence at face value.

I wanted to point this out here because the dichotomy between realism and nominalism is central to Klement's discussion of the No Class theory. Klement argues that while a realist philosophy compels one to accept that an open sentence is something, a nominalist position permits the consistent disavowal of that assertion. The realist, being thus compelled, is then forced to identify an open sentence with the function classifying things that could instantiate the variable, since the two are extensionally equivalent. For the realist, then, the No Class theory of open sentences is a chimera because it collapses into the same thing as having classes in the first place. The nominalist, however, permits himself to have an expression like an open sentence that doesn't correspond to something which "exists", and then is not led to an identity between open sentences and functions as maps.

The moral, for linguistic theory, is that it can be very important foundationally whether one construes a theoretical construct as representing something which exists.

This sentence is false.

A new publication by Philippe Schlenker ["Super Liars" in Review of Symbolic Logic 3(3)] presents an excellent new treatment of that old chestnut, the Liar paradox (exemplified in my post title). Schlenker's insight is to develop a technical logical semantics which, rather than trying to solve the paradox, tries to account for how human languages cope with the paradox while devising a sane system of truth values for human languages.

Schlenker begins with a now standard assumption that an account of Liars and other paradoxes in natural language requires a third truth value. He then shows in an easily readable fashion how this step leads directly to the need for allowing ordinal-many truth values, with a sort of infinite hierarchy of so-called "super liars" arising as well. The resulting treatment is as expressively complete as can be expected, providing the ability for a language to express that any given "super liar" sentence is something other than true.

The semantics of paradox must eventually be integrated into a functioning semantic theory for natural language; this paper makes a good start.

Proof nets for grammatical logic

A "proof net" is a kind of compressed proof that was developed for linear logic in the late 1980s. They have been studied a great deal ever since for a number of reasons, one of which is that linear logic is a close relative of the Lambek logics that are useful in linguistic syntax under the modern-day rubric of type-logical grammar. A good source to learn about type-logical grammar and linguistics is my now passé 2004 book (not in most libraries but available cheaply as an ebook, though try to ignore Ch. 6), but also Glyn Morrill's 1994 book (not available cheaply but found in many libraries). For learning about linear logic, type-logical grammar, and proof nets all under one roof, the one and only source is Richard Moot's PhD dissertation, a real tour-de-force. My own dissertation (which grew up into the book) is quite embarrassing compared to this masterpiece, which is still available here.

I'm currently working on a survey paper about proof nets and other proof "compressions." I've actually been working on this paper for about ten years, but I really feel I might finish it soon. The purpose is to highlight the subject for the broader logic community, and to focus primarily on how the proof compressions become more and more geometrical as the logic gets stricter control over the arrangement of formulae. For classical propositional logic, the most compressed proof object is a "matrix" of atoms derived from the formula tree. The condition ensuring provability of the formula is basically set-theoretical, there is not much geometry to it. For linear logic, one keeps track of multisets of formulae (counting occurrences), and so the proof net provability condition is more graph-theoretical. For the associative Lambek logic we no longer have commutativity of the formulae, and the corresponding proof net condition comes to involve "planarity" of the graph. This is fundamentally a geometric condition that can be expressed using topology. The most restricted logic of all is the nonassociative Lambek system, and extending the proof nets to this case has to involve more specific topological conditions which I am still working out for my paper.

All of this seems important to me because if linguistic grammar is to be modeled type-logically, the "proofs" of sentences should be able to be carried out in a highly compressed fashion if the system is to have cognitive relevance. Generally, the brain's innate computational abilities seem to invoke highly efficient methods that are implemented in the neural "analog computer." But that leads me to a discussion of analog computation in the brain, which should be left to another post.