depth first search

One of the most exciting things about Google is that even when they do cost cutting, they innovate.

I’m stuck on what should be the easiest section of my proposal to write because it is the only section I’ve already published. The problem is that, in the time since I worked on that paper, my whole conception of “what’s going on” has changed. At least I had the presence of mind at the time to coin the phrase “sensorimotor embedding” in a way that is quite similar though much less precise than what I’m doing in my proposal.

The problem is that I have a number of equations that describe how saccades (quick eye movements) can affect sensor activation if the sensor has a foveated structure (more resolution in the center and less resolution on the periphery — just like your eyes and mine). These equations all reference the state of the system, which is really just the sensor pose. The problem is that the whole point of the paper is to infer the pose, because the agent does not know the pose.

So I have all these equations that utilize unknown sensor pose to describe how an agent can learn the sensor pose, which ends up being sort of circular unless you understand clearly where the dividing line is between what an agent knows and what an agent is trying to learn. This problem keeps cropping up in my proposal. I need to figure out a way to make if clear that the point is to figure out a way to infer the unknown from the known, and what parts of the model the agent is “filling in” when it goes about learning. It’s gotten so bad that I am basically highlighting unknown parts of the model in red.

Is there a better way? I know in graphical models there’s a specific notation for observed variables versus hidden variables. But I’m not using graphical models (for reasons that are somewhat too complicated to explain in one post), so is there a notation that I can use in (not necessarily probabilistic) formulas directly that doesn’t involve drawing a bunch of graphs like in graphical models?

The doctrine that we could not perceive the world around us unless we already had the concept of space is nonsense. It is quite the other way around: We could not conceive of empty space unless we could see the ground under our feet and the sky above. Space is a myth, a ghost, a fiction for geometers.

J.J. Gibson

The Turing Test is a famous test of machine intelligence. In the basic setup, a human communicates with an agent through some kind of computer terminal (so the agent is never visible). The human is tasked with determining whether the agent is a machine or another human. The goal of machine agents is to imitate natural conversation to the point of being indistinguishable from a human participant.

Like many good ideas, this test has caused a lot of controversy over the years, and as artificial intelligence has moved away from the study of the mind and into concrete application areas, discussions about intelligence tests (Turing and otherwise) have languished somewhat. There are occasionally some exceptions to this general trend. For instance, at this years ICDL in Ann Arbor, Jivko Sinapov and Alexander Stoytchev presented an intelligence test for robots in their award winning paper, “The odd one out task: Toward an intelligence test for robots.”

One property that intelligence tests seem to all share is that they depend critically on human observers building internal models of agents that are indistinguishable from the models human observers build for other humans. Even in constrained situations like the odd one out task, these kinds of assessments usually take the form of specifying a task that human and other agents can both perform. Our interpretation of the functional nature of the performance becomes the basis for assessing whether the agent has “passed” the test.

This seems to lead to a number of interesting problems. For one, there is a many-to-one correspondence between methods and results (many methods may yield the same behavior), so our “attributing” human-like models to agents may in fact be a faulty attribution (the agent could be doing something simple but demonstrating the correct contextual behavior). Of course there’s the opposite problem of recognizing that intelligent behavior may not necessarily look like human behavior, and so even if we fail to attribute human-like models to artificial agents, we may be missing other signs of intelligence. I imagine that this kind of error gives science fiction authors and people searching for other intelligent life in the universe headaches.

There have been a number of alternate proposals for intelligence tests geared towards developmental agents, most recently in a paper by Paul Cohen. In that paper, Cohen summarizes a number of possible replacements for the venerable Turing Test:

1. Robot soccer
2. Never ending language learning
3. A virtual third grader

Unlike these proposals, the new body problem lacks a easily describable goal. This seems to arise naturally in any relatively task-free scenario, and many of Cohen’s examples skirt the issue by incorporating a variety of task or task-like elements in each test. The new body problem simply states a desire to learn about a new body starting from scratch. It’s simple but the criterion for success if still vague. What ought an agent that can solve the new body problem be able to achieve? Certainly we can imagine any number of tasks that we could use to test an agent, but any restraint on the tasks would lead us back into the morass of subjectively attributing human like models of intelligence to agents.

Here’s a possibility that I’m currently considering. What if the end goal of an agent solving the new body problem is to describe itself? We would have to apply subjective kinds of judgments to the descriptions provided (e.g. a low level inventory of raw sensors and motors is not really demonstrative of the kind of development we would like to see). On the other hand, we do not seem to have the same kind of a priori biases in evaluating an agent describing itself than we would evaluating an agent within a particular task domain. In other words, we would have an open ended evaluation for an open ended learning problem, which strikes me as precisely the kind of particularist approach we would ultimately need if we ever wanted to truly test for intelligence.

Today is full of minor little administrative details that need attention and always seem to correlate with 1) the beginning of the classes and 2) returning to Austin after having been away all summer. The end result of all of this is that my mind is all over the place right now, and not nearly in the necessary shape to work on revising my proposal. So instead I’ll leave you with one more comically vague question to ponder.

What is knowledge?

My wife and I were discussing something similar (specifically, whether knowledge could by copied or transferred) while driving home from Ann Arbor. I found out that navigating Dallas traffic was not conducive to having a good technical discussion. In any event,  to discuss how knowledge can be transferred, we would seem to require some basic understanding of what knowledge actually is.

As before, it’s probably a good idea to consider a specific example from a particular field of study. In reinforcement learning, the goal is to have agents learn policies, or ways of choosing how to act, that are somehow “optimal.” One way of doing this is to learn something called a value function, which roughly captures the intuitive notion of how being in particular states would benefit an agent over time. To someone studying reinforcement learning then, value functions reflect a certain kind of very important knowledge about how to act in the world. In addition, people have studied how to transfer the kinds of knowledge that are wrapped up in value functions to new agents in new domains. This area is known as transfer learning.

There is even a belief out there that all of artificial intelligence falls under the rubric of learning value functions. This is known as “the reward hypothesis” or “the value function hypothesis.” You can find a reasonably concise statement of that view here. I don’t really believe in any form of the reward hypothesis. Human intelligence does not seem confined by the narrow constraints that this particular view would necessarily imply. For instance, language acquisition and use almost certainly cannot be satisfactorily explained via some form of adaptive optimal control. If you don’t believe me maybe you’ll believe Noam Chomsky.

• At the laundromat because the only washer in my building broke. #noredundancy #noclothes #nothappy #
• Laundromat has wifi but no beer. So better than NYC but worse than New Orleans. #
• After the laundromat I'm heading to Walmart. #realamerica #
• Sunday afternoons at a laundromat are *prime* people watching hours. #

David Vernon’s opening keynote at this year’s ICDL included a lot of information about the iCub, a serious effort to create a standard platform for developmental robotics. The talk was in part a review of a road map for developmental robotics that iCub researchers have been working on. They have a compelling story, one that I find very interesting.

After the talk there was a brief Q&A session, and one of the audience members asked an interesting question. If developmental robotics is so great, how do we demonstrate it for the vast majority of still skeptical roboticists? I didn’t like the answer Vernon gave, so I thought I’d provide my own. First, I don’t believe that in terms of what roboticists are trying to do at the present moment, developmental approaches are the way to go. To put this another way, if you want to build an autonomous tank, you are better off applying careful engineering than trying to structure some kind of developmental process that starts with a “baby” tank that grows into an “adult” tank. Second, as more and more problems get moved into the “solved” category through some combination of careful engineering and learning, the remaining questions will only get harder, and eventually the developmental approach will surpass careful engineering.

One possible future includes robots with innumerable differences in configurations (for example, consider the individual variations in humans). This differs from the view that robots will be constrained to certain models like automobiles. In one case, engineering each model would be feasible, in another, the development would rapidly eclipse the benefits of careful engineering.

These possible futures point to a problem we can consider in the present to demonstrate the necessity of the developmental approach, much in the same way the ‘kidnapped robot problem‘ crystallized research into autonomous mapping and navigation. For lack of a better name, I call this the “new body problem.” The basic problem statement is, starting with an uninterpreted sensory and motor interface, learn to complete simple tasks as instructed by a human.

To be concrete, consider that an uninterpreted sensor interface is just a time sequence of vectors where each . A motor interface is a similarly general sequence of vectors where each motor variable can be set by the agent. Solving this problem as stated would require development, but we can certainly imagine modifications to the problem that would allow the agent to wake up with slightly more semantic sensor and motor knowledge that would still require substantial development before being able to take instructions and perform simple tasks. The point is that by framing the problem this way we are explicitly identifying dual goals, to increase the competencies of the learned robot at the end of development, and to decrease the necessary prior knowledge needed at the beginning of development. Developmental robotics considers both goals.

In a previous post I mused on the recent proof attempt. As a practical matter, complexity theory is very different from what I do, so even though I’m a graduate student in computer science, my ability to comment on the internal dynamics of the discipline is quite limited. My opinions are really a result of the few graduate theory courses I took and my amateur but continuing interest in the area, combined with a bunch of offhand comments theory researchers and student have made in my department.

In my previous post I implied (I think correctly) that nobody works on proving anymore, but I attributed this to there being very little funding in theoretical computer science. In fact, the reason nobody works on the problem is that nobody knows how to work on the problem. This state of affairs is mainly due to the fact that complexity theorists have been a little too successful in ruling out plausible approaches to the problem as doomed to fail. The fact that nobody funds direct attacks on the problem is largely due to the demonstrated barriers and not any kind of growing disinterest in the status of the question.

Finally, for those of you who do not follow theory of computing blogs there are calls for Deolalikar to withdraw his claim due to insurmountable errors in the proof attempt. So that’s that.

… in the 1960s almost no one realized that machine vision was difficult. The field had to go through the same experience as the machine translation field did in its fiascoes of the 1950s before it was at last realized that here were some problems that had to be taken seriously. The reason for this misperception is that we humans are ourselves so good at vision. … the idea that extracting edges and lines from images might be at all difficult simply did not occur to those who had not tried to do it.

– David Marr, Vision

I saw the following “proof” (meant to illustrate — not as a serious claim) that in these slides.

Suppose . Then clearly for all oracles . Since we know that for at least one oracle , it follows that .