Computational Structure of Human Language

The central thesis of this report is that human language is NP-complete. That is, the process of comprehending and producing utterances is bounded above by the class NP, and below by NP-hardness. This constructive complexity thesis has two empirical consequences. The first is to predict that a linguistic theory outside NP is unnaturally powerful. The second is to predict that a linguistic theory easier than NP-hard is descriptively inadequate. To prove the lower bound, I show that the following three subproblems of language comprehension are all NP-hard: decide whether a given sound is possible sound of a given language; disambiguate a sequence of words; and compute the antecedents of pronouns. The proofs are based directly on the empirical facts of the language user's knowledge, under an appropriate idealization. Therefore, they are invariant across linguistic theories. (For this reason, no knowledge of linguistic theory is needed to understand the proofs, only knowledge of English.) To illustrate the usefulness of the upper bound, I show that two widely-accepted analyses of the language user's knowledge (of syntactic ellipsis and phonological dependencies) lead to complexity outside of NP (PSPACE-hard and Undecidable, respectively). Next, guided by the complexity proofs, I construct alternate linguisitic analyses that are strictly superior on descriptive grounds, as well as being less complex computationally (in NP). The report also presents a new framework for linguistic theorizing, that resolves important puzzles in generative linguistics, and guides the mathematical investigation of human language.

The Individual is Nothing, the Class Everything: Psychophysics and Modeling of Recognition in Obect Classes

Most psychophysical studies of object recognition have focussed on the recognition and representation of individual objects subjects had previously explicitely been trained on. Correspondingly, modeling studies have often employed a 'grandmother'-type representation where the objects to be recognized were represented by individual units. However, objects in the natural world are commonly members of a class containing a number of visually similar objects, such as faces, for which physiology studies have provided support for a representation based on a sparse population code, which permits generalization from the learned exemplars to novel objects of that class. In this paper, we present results from psychophysical and modeling studies intended to investigate object recognition in natural ('continuous') object classes. In two experiments, subjects were trained to perform subordinate level discrimination in a continuous object class - images of computer-rendered cars - created using a 3D morphing system. By comparing the recognition performance of trained and untrained subjects we could estimate the effects of viewpoint-specific training and infer properties of the object class-specific representation learned as a result of training. We then compared the experimental findings to simulations, building on our recently presented HMAX model of object recognition in cortex, to investigate the computational properties of a population-based object class representation as outlined above. We find experimental evidence, supported by modeling results, that training builds a viewpoint- and class-specific representation that supplements a pre-existing repre-sentation with lower shape discriminability but possibly greater viewpoint invariance.

Component based recognition of objects in an office environment

We present a component-based approach for recognizing objects under large pose changes. From a set of training images of a given object we extract a large number of components which are clustered based on the similarity of their image features and their locations within the object image. The cluster centers build an initial set of component templates from which we select a subset for the final recognizer. In experiments we evaluate different sizes and types of components and three standard techniques for component selection. The component classifiers are finally compared to global classifiers on a database of four objects.

Applying the Lessons of “Lean Now” to Transform the US Aerospace Enterprise

Lean is common sense and good business sense. As organizations grow and become more successful, they begin to lose insight into the basic truths of what made them successful. Organizations have to deal with more and more issues that may not have anything to do with directly providing products or services to their customers. Lean is a holistic management approach that brings the focus of the organization back to providing value to the customer. In August 2002, Mrs. Darleen Druyun, the Principal Deputy to the Assistant Secretary of the Air Force for Acquisition and government co-chairperson of the Lean Aerospace Initiative (LAI), decided it was time for Air Force acquisitions to embrace the concepts of lean. At her request, the LAI Executive Board developed a concept and methodology to employ lean into the Air Force’s acquisition culture and processes. This was the birth of the “Lean Now” initiative. An enterprise-wide approach was used, involving Air Force System Program Offices (SPOs), aerospace industry, and several Department of Defense agencies. The aim of Lean Now was to focus on the process interfaces between these “enterprise” stakeholders to eliminate barriers that impede progress. Any best practices developed would be institutionalized throughout the Air Force and the Department of Defense (DoD). The industry members of LAI agreed to help accelerate the government-industry transformation by donating lean Subject Matter Experts (SMEs) to mentor, train, and facilitate the lean events of each enterprise. Currently, the industry SMEs and the Massachusetts Institute of Technology are working together to help the Air Force develop its own lean infrastructure of training courses and Air Force lean SMEs. The first Lean Now programs were the F/A-22, Global Hawk, and F-16. Each program focused on specific acquisition processes. The F/A-22 focused on the Test and Evaluation process; the Global Hawk focused on Evolutionary Acquisitions; and the F-16 focused on improving the Contract Closeout process. Through lean, each enterprise made many significant improvements. The F/A-22 was able to reduce its Operational Flight Plan (OFP) Preparation and Load process time of 2 to 3 months down to 7 hours. The Global Hawk developed a new production plan that increases the annual production of its Integrated Sensor Suite from 3 per year to 6 per year. The F-16 enterprise generated and is working 12 initiatives that could result in a contract closeout cycle time reduction of 3 to 7 years. Each enterprise continues to generate more lean initiatives that focus on other areas and processes within their respective enterprises.