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.

Building Grounded Abstractions for Artificial Intelligence Programming

Most Artificial Intelligence (AI) work can be characterized as either ``high-level'' (e.g., logical, symbolic) or ``low-level'' (e.g., connectionist networks, behavior-based robotics). Each approach suffers from particular drawbacks. High-level AI uses abstractions that often have no relation to the way real, biological brains work. Low-level AI, on the other hand, tends to lack the powerful abstractions that are needed to express complex structures and relationships. I have tried to combine the best features of both approaches, by building a set of programming abstractions defined in terms of simple, biologically plausible components. At the ``ground level'', I define a primitive, perceptron-like computational unit. I then show how more abstract computational units may be implemented in terms of the primitive units, and show the utility of the abstract units in sample networks. The new units make it possible to build networks using concepts such as long-term memories, short-term memories, and frames. As a demonstration of these abstractions, I have implemented a simulator for ``creatures'' controlled by a network of abstract units. The creatures exist in a simple 2D world, and exhibit behaviors such as catching mobile prey and sorting colored blocks into matching boxes. This program demonstrates that it is possible to build systems that can interact effectively with a dynamic physical environment, yet use symbolic representations to control aspects of their behavior.

Geometric and Algebraic Aspects of 3D Affine and Projective Structures from Perspective 2D Views

We investigate the differences --- conceptually and algorithmically --- between affine and projective frameworks for the tasks of visual recognition and reconstruction from perspective views. It is shown that an affine invariant exists between any view and a fixed view chosen as a reference view. This implies that for tasks for which a reference view can be chosen, such as in alignment schemes for visual recognition, projective invariants are not really necessary. We then use the affine invariant to derive new algebraic connections between perspective views. It is shown that three perspective views of an object are connected by certain algebraic functions of image coordinates alone (no structure or camera geometry needs to be involved).

Computational Models of Object Recognition in Cortex: A Review

Understanding how biological visual systems perform object recognition is one of the ultimate goals in computational neuroscience. Among the biological models of recognition the main distinctions are between feedforward and feedback and between object-centered and view-centered. From a computational viewpoint the different recognition tasks - for instance categorization and identification - are very similar, representing different trade-offs between specificity and invariance. Thus the different tasks do not strictly require different classes of models. The focus of the review is on feedforward, view-based models that are supported by psychophysical and physiological data.

Geometric Aspects of Visual Object Recognition

This thesis presents there important results in visual object recognition based on shape. (1) A new algorithm (RAST; Recognition by Adaptive Sudivisions of Tranformation space) is presented that has lower average-case complexity than any known recognition algorithm. (2) It is shown, both theoretically and empirically, that representing 3D objects as collections of 2D views (the "View-Based Approximation") is feasible and affects the reliability of 3D recognition systems no more than other commonly made approximations. (3) The problem of recognition in cluttered scenes is considered from a Bayesian perspective; the commonly-used "bounded-error errorsmeasure" is demonstrated to correspond to an independence assumption. It is shown that by modeling the statistical properties of real-scenes better, objects can be recognized more reliably.

Public and student awareness science: recreational science as a catalyst

When discussing the traditional and new missions of higher education (1996 Report to UNESCO of the International Commission on Education for the 21st Century) Jacques Delors stated that "Excessive attraction to social sciences has broken equilibrium of available graduates for workforce, thus causing doubts of graduates and employers on the quality of knowledge provided by higher education". Likewise, when discussing the progress of science and technology, the 1998 UNESCO World Conference on Higher Education concluded that "Another challenge concerts the latest advancements of Science, the sine qua non of sustainable development"; and that “with Information Technology, the unavoidable invasion of virtual reality has increased the distance between industrial and developing countries". Recreational Science has a long tradition all over the Educational World; it aims to show the basic aspects of Science, aims to entertain, and aims to induce thinking. Until a few years ago, this field of knowledge consisted of a few books, a few kits and other classical (yet innovative) ways to popularize the knowledge of Nature and the laws governing it. In Spain, the interest for recreational science has increased in the last years. First, new recreational books are being published and found in bookstores. Second the number of Science-related museums and exhibits is increasing. And third, new television shows are produced and new short science-based, superficial sketches are found in variety programs. However, actual programs in Spanish television dealing seriously with Science are scarce. Recreational Science, especially that related to physical phenomena like light or motion, is generally found at Science Museums because special equipment is required. On the contrary, Science related mathematics, quizzes and puzzles use to gather into books, e.g. the extensive collections by Martin Gardner. However, lately Science podcasts have entered the field of science communication. Not only traditional science journals and television channels are providing audio and video podcasts, but new websites deal exclusively with science podcasts, in particular on Recreational Science. In this communication we discuss the above mentioned trends and show our experience in the last two years in participating at Science Fairs and university-sponsored events to attract students to science and technology careers. We show a combination of real examples (e.g., mathemagic), imagination, use of information technology, and use of social networks. We present as well an experience on designing a computational, interactive tool to promote chemistry among high school, prospective students using computers ("Dancing with Bionanomolecules"). Like the concepts related to Web 2.0, it has been already proposed that a new framework for communication of science is emerging, i.e., Science Communication 2.0, where people and institutions develop new innovative ways to explain science topics to diverse publics – and where Recreational Science is likely to play a leading role

Investigating legal aspects of cyberbullying

Resumen tomado de la publicaci??n