depth first search

In an otherwise interesting but ill-thought-out comparison of cuckoldry and rape, I found this little nugget:

We all know that women tend to be more expressive about their complaints – you can’t beat ‘em for wailing and gnashing of teeth.

Really? That hasn’t been my experience. And anyway, even by the flimsy standards of economics this particular claim is entirely unsupported.

This serves to reinforce my outsider view of the discipline: you folks spend all your time trying to formulate counterintuitive claims that you can support with limited data and faulty statistics. In the process you routinely boil morality, ethics, and the human condition down to single estimates of utility in conveniently succinct but laughably unsupportable ways. Then, model in hand, you commit the cardinal sin of economics: you confuse your model with reality.

Jeebus. Doesn’t the other 90% of your intellect tell you that your conclusions are totally ridiculous? When I get to such a perverse place in my own thinking I usually ask myself where I went wrong instead of tumbling forward like some goddamn moron.

UPDATE: Because economists might read this let me be a bit more explicit for the slow folks in the room. I often write so as to simulate precisely what I’m writing about, so my universal statement “economists are terrible people” is intended to evoke the precisely kind of distaste that the quoted comment above would. It’s a subtle point that individuals with decent reading skills (who must not be economists [I did it again!]) would understand.

I keep hearing about this problem of communicating with people in the future about dangerous radioactive waste storage sites. My solution to the problem is to make the sites as desolate and unremarkable as possible. Given our natural curiosity, putting up elaborate structures seems like more like an invitation than a prohibition, even if those structures are designed to be foreboding or menacing.

And if people of the future happen upon this desolate and unremarkable wasteland, what then? Well, some of them get sick and die. We have  to trust that humanity’s ability to formulate causal models from that kind of data remains intact, and so the rest will relearn the forgotten lessons of the past. In other words, the best way to communicate with the future by doing nothing special and trusting that they will figure it out.

UPDATE: Ana called me out for not reading the linked article (just the pull quote). This is one of those cases where a piece of news is making multiple circuits around the web, and I had assumed (wrongly) that the links led to an article I had read awhile ago, and not the current (and quite interesting) interview.

I also have to revise my own plan somewhat. A Rosetta stone like monument is clearly the best bet for the short term, assuming some language survives. Though computational linguistics is making progress decoding languages with no Rosetta stone analogue, the ability for future generations to interpret signs increases dramatically if one of the available languages is known.

The case where no language survives in its current form is more complex. Here’s were my plan makes a bit more sense. You have to weigh the probability of discovery against the probable protocols future humans (or others) might employ should the site be discovered. I was imagining an ideal scenario where the site could avoid detection for a million years.

But what if it is discovered? I think the best result is to have some kind of subtle but lasting monument, and let the experience of exploring a radioactive hot zone (and the inevitable bad result) lead future explorers to the correct conclusion about the meaning of the monument. Basically, if people find the repository, we want to make sure they explore it, and by exploring it, learn the nature of the danger. This avoids the terrible case where people settle the area without any knowledge of the danger lurking underneath.

I’ve been traveling a great deal recently, first to the AAAI Fall Symposium then to EpiRob. One of the most interesting days of all this conference travel came at the tail end of the EpiRob conference, which coincided with the beginning of the workshop on intrinsic motivation called IM-CLeVeR. Part of the appeal was the presence of so many luminaries in my particular field (the reinforcement learning community was particularly well represented, as Andrew Barto and Richard Sutton were both in attendance).

I’m still compiling my notes from both conferences, and hope to distill some of those ideas into entries, but I thought I’d start with an intriguing idea from Professor Barto, that “motivation is the gradient of the value function.” One approach to reinforcement learning, where an agent tries to act so as to maximize reward over time, is to compute value functions, which assign values to each state of the world that are intended to reflect estimates of future rewards agents can hope to achieve from those states acting as they are. Though I think this description is accurate, it is certainly horribly concise, so I’d recommend the book if you are intrigued enough to learn more.

Anyway, if an agent has a value function that represents the best an agent can expect in terms of future rewards for any state, then an agent has enough information to act optimally, since it simply needs to look to the next state with highest value. The gradient, or change in value from state to state, drives the choice of agent actions, and so can be considered a kind of motivation. We should probably complicate this further by noting that agents have to learn value functions, and that not all value functions are created equal. In fact, there’s a unique value function, the optimal value function, that represents the best an agent can do from any particular state. If the agent is gifted with this value function, then gradient as motivation makes sense. If not, then we have to consider the need to change the value function to better approximate the optimal, alongside the need to follow the value function in some greedy way.

[Aside: Thinking off the cuff, we can view the need to properly approximate the optimal value function as part of a kind of meta-value function, which doesn't just consider the values of world states relative to the reward function, but also considers the value of proper value function estimation. And so on down the rabbit hole...]

But all this complexity seems to avoid the tricky issue of motivation. For one thing, we, as the specifiers of the algorithm, are setting up the agent to follow value function gradients (or exploratory gradients) as a consequence of the way the problem is set up. In some sense, this is unappealing since it leaves aside any explanation for why an agent should follow value functions in the first place. Put another way, value function gradients as motivation for behavior only make sense in the context of a reward function that indicates good outcomes (if not the method of achieving those outcomes). So this just begs the question, where do rewards come from? This is a question that reinforcement learning conveniently avoids answering by assuming from the outset (at least in theory) that rewards are given.

“Where do rewards come from?” was, not surprisingly, the title of Andrew Barto’s workshop presentation, so I may very well just be recapitulating his own line of reasoning on the matter. His talk summarized a very interesting piece of work that looked at how evolution can act on reward functions that result in learning agents with better fitness. The presentation made a point about reward functions that I’ve thought of independently, but which psychologists have already enunciated in various forums. The point is this: reward signals are nothing special to the world, even though they are special to the agent. The universe does not care that you go hungry; you care that you go hungry. Drawing rewards as a distinct signal in standard reinforcement learning diagrams does not make sense. Rewards are just normal state signals with a special (internal and evolution-mediated) interpretation by the agent.

My wife is one of those ferociously intelligent people who asks questions until she fully understands something. That really minimizes my opportunities for bullshit around the apartment. On the plus side, I end up understanding what I claim to understand just by virtue of being forced to think clearly enough to explain it. This is, as you might imagine, sometimes a stressful process. I consider it a rule that if you are not walking a tightrope right at the edge of your own understanding (and hence in real risk of falling off, should you meet a true skeptic along the way), you aren’t really doing your job as an intellectual or academic (if that is your job).

If you understand everything you are doing, you are a clerk. Nothing wrong with that. Clerks run most things.

[ Aside: I should note that I'm not protectionist with regards to titles like "intellectual." You can clerk by day and intellectualize by night, or on weekends, or when fishing. It's not the kind of club that has membership dues. If you struggle to understand new things, even old things that are new to you, than you are in. If you don't you're not. ]

Anyway, I was pressed into service to explain the meaning behind quotes from the other day.

[ Aside: Here I should pause to mention that my wife sometimes forces me to explain things she already understands, or that she doesn't have time to read herself. ]

I thought I did an okay job of it, so I thought I’d share with you what I understand so far of Karl Popper’s The Logic of Scientific Discovery. The first thing you should know about this book is that it basically is the foundation of our modern understanding of science. If you ever hear about falsifiability as a criterion for scientific theory, you have Popper to thank. The ideas of TLSD are so pervasive in how scientists now view their own work, that one wonders if Popper hasn’t done the unthinkable and settled a philosophical question for good. Since I’m not plugged into the larger philosophy of science community I don’t really know if that is a correct characterization of TLSD or not, but it certainly is an influential text.

So what was Karl Popper’s project? His goal was to characterize science. To do this he tried to identify the formal logic (or rules) that govern the scientific process. Anything that follows the logic of science can rightly be called science, and anything that does not cannot. The logic of science, once identified, characterizes science. This probably seems like a daunting task, but TLSD is written in a way that when read it is at once both obvious and airtight. Part of the trick on Popper’s part is to conveniently avoid some of the harder questions, like where scientific theories come from (e.g. creativity?). In doing so, he is able to assume that there are things called scientific theories, and explore what properties we expect them to have.

One of the first schools of thought that Popper has to deal with when exploring the logic of science, is the idea that science, rather than being entirely logical, contains a psychological or interpretive component (beyond those that Popper has already conceded). If this is true it is problematic for the project, because then any logic of science would also have to include a logic of psychology, thus enlarging the original problem and removing all hope of tractability. Popper sidesteps this problem by noting, as in the first quote, that while observations and perceptions are psychological, observability is not. Observability is a property of the world. The trick here, is that when describing the logic of science, and just the logic, observability is enough. Observability is one (conveniently non-psychological) property of basic statements about the world needed to falsify theories.

[ Aside: I'm being somewhat vague about basic statements. Popper is very careful defining the concept, and to do so with any rigour requires the many pages Popper spends on the topic. For our purposes,  you can think of basic statements as things that are observable, and that if observed, may falsify a theory. Interestingly, there is a kind of dual relationship between basic statements and theories, since theories have to be constructed in order to have falsifying basic statements. There's no circularity in Popper's definition, however, since basic statements exist independent of theories. Theories just partition an already existing set of basic statements into falsifying and non-falsifying ones. ]

By setting up this framework of basic statements and the partitioning power of theories, Popper is then able to argue that theories are an essential part of science, and in particular, just collecting facts about the world is not enough. That is the meaning I draw from the second quote. It is here, however, where I think Popper gets away with too much. He ignores the interesting question of where theories come from. They certainly don’t spring fully formed from the mind. It seems entirely plausible that theories form through some process running in our heads as we are “collecting and arranging our experiences.” But once we have a theory, we are definitely able to explore the world with a purpose.

Observations and perceptions may be psychological, but observability is not.

The Logic of Scientific Discovery, pg. 103

Thus the real situation is quite different from the one visualized by the naïve empiricist, or a believer in inductive logic. He thinks that we begin by collecting and arranging our experiences, and so ascend the ladder of science. Or, to use the more formal mode of speech, that if we wish to build up a science, we have first to collect protocol sentences. But if I am ordered: ‘Record what you are now experiencing’ I shall hardly know how to obey this ambiguous order. Am I to report that I am writing; that I hear a bell ringing; a newsboy shouting; a loudspeaker droning; or am I to report, perhaps, that these noises irritate me? And even if the order could be obeyed: however rich a collection of statements might be assembled in this way, it could never add up to a science. A science needs points of view, and theoretical problems.

Ibid., pg. 106

At the beginning of the summer, I always plan on reading all the things I did not quite get to during other seasons of the year. Though I am often too ambitious, I am making some progress on a number of fronts. The first is Karl Popper’s landmark The Logic of Scientific Discovery. As I read through Popper’s ideas on the logic of science I am struck by how pervasive his ideas have become among the scientific establishment. No, that’s not quite right, his ideas are a pervasive part of our cultural view, not the establishment, of science. I’m not sure if Popper was the first to formulate falsifiability as a rigorous philosophical criterion demarcating scientific hypotheses, but reading his clear exposition of the concept certainly makes his ideas ring true.

I will note that one question Popper does not seem to consider is: “What makes a particular scientific pursuit interesting?” I’ve been struggling with this question in my own research, as I sift through a number of silos of work in machine learning and robotics, looking for both the big picture and the motivations behind each community effort. I do think it is possible to pose scientific questions that meet all the criteria of demarcation that Popper spells out, which fail as scientific questions simply because nobody else cares. Indeed, I think such “trivial” science actually comprises the near totality of posable scientific hypotheses. We don’t notice this because of a combination of our own bias and the natural selection bias that any peer reviewed scientific community uses as an organizing social and meritocratic engine.

I really cannot comment on the Iranian election itself, but I think I can comment somewhat on the popular pundit reaction to the election. Fortunately, Matthew Yglesias captures most of my thinking in < 140 characters:

People who now think Obama is insufficiently concerned with the Iranian people used to think we should drop bombs on them.

I’m not sure that one party in the dispute is particularly better from the point of view of American interests. From what I’ve read the opposition party is somewhat more moderate (whatever that even means in the context of a theocratic dictatorship). The fact that there are protests at all, and relatively non-violent protests (compared to the size of the demonstrations) as far as I can tell, seems like a good thing for Iranian liberals (whatever liberal means in Iran).

My point in making these observations is that all wonkish terms that we would normally use to describe the ebbs and flows of western style democracies don’t seem to fit this scenario, and reading the news analysis on this issue is more a study in failures of translation and the corresponding deconstruction of political language than an informative view into what is really going on.

Of course, given my lingering discomfort with religion, I’m sort of the last person who could hope to understand any side of the Iranian mindset.

ASIDE: Is it ironic that Iranians are relying on methods of communication that are a product of American entrepreneurial and technological ingenuity? Nevermind. This question sounds too much like “America is the best country on earth” and not enough like what I was trying to ask, which is whether we can conclude from Iranians’ use of things like Twitter whether they have a pro-western stance or not.

In a recent conversation the idea of performance criteria as a measure of success in artificial intelligence came up. The context, if I recall, was whether intelligence is best understood as the end result of optimization, where the intermediate and final solutions may resist direct scrutiny, or as a sequence of representations (designed, learned, or both) with which an agent can act intelligently and robustly.

In some sense, these two approaches are both overly reductive, and not entirely exclusionary. I would not say they are orthogonal, but I do suspect that non-trivial intelligent systems of any kind require a fairly heterogeneous set of approaches. I’m immediately suspicious of any kind of universal framework for understanding intelligence. A lot of research focuses on parts of the intelligence problem, suitably constrained so as to admit the easy specification of performance criteria. Less research seems to focus on the ways in which these parts are intended to interact as complete agents that we hope would exhibit a kind of general intelligence.

As an example, the thermostat in this room meets a performance criteria. I can measure temperature deviations over time and develop a fairly accurate measure of how the thermostat is doing. The problem with performance measures, is that as a criteria for intelligence, these measures alone are incomplete. If you buy into the optimization view, then your work really only begins after the tricky problem of establishing a problem and a metric for performance is already complete. You are just evaluating thermostats, no matter how internally complex they might end up being.

If, on the other hand, you take a more representational view, then in designing the representational target, you are essentially exploring the problem and performance space (deciding for instance, that temparature control is sort of trivial, and can be left out), leaving aside till later the difficult learning problems that result only after the proper targets have been identified. This approach is not quite as clean cut, but it has the benefit of exposing the subjective, political nature of the discipline right up front, instead of burying that aspect of AI research in the group think of acceptable problems.

I have been thinking a bit about what constitutes successful artificial intelligence research. I have heard the usual saying that once a problem in artificial intelligence is solved it is no longer considered AI. I think we can unpack this dictum a bit more. First, I do not think that successful research in artificial intelligence necessarily requires that some “real” world problem be solved. The goal of AI should be to better understand the phenomenon of intelligence. This is a goal shared by other disciplines as well (and as a consequence AI is becoming very interdisciplinary), but the AI approach to this question seeks to model intelligence using computation.

Now getting back to the fallicy that AI needs to solve problems in the real world, consider that the real world does not care whether the solution to a problem is “intelligent.” What makes a line of research successful by the standards of the real world are

1. that there is a real need for a solution to a particular problem
2. that research uncovers a sufficiently good solution.

You’ll notice that neither of these criteria actually requires that we understand intelligence. To put this in more concrete terms, consider Google. The success of search on the web is a product both of the need for automated search and the ability of page rank to generate good search results, but should we expect that a clear and complete understanding of how Google search works also conferes a deep understanding of intelligence?

One particularly important critique of this view is that we should expect research in AI to yield systems of increasing intelligence, and since many currently open problems can be solved by more intelligent systems, we should expect that AI results in “real” world solutions in addition to a deeper understanding of intelligence. The former is an epiphenomena of the latter. Without observing the growth of practical solutions, we should rightly doubt progress in the field. The problem with this view is that practical solutions to problems seem to be punctuated (requiring a precise alignment of criteria 1 and 2 above), whereas our understanding of intelligence can increase gradually over time.

Now it is far from obvious, from a logical point of view, that we are justified in inferring universal statements from singular ones, no matter how numerous; for any conclusion drawn in this way may always turn out to be false: no matter how many instances of white swans we may have observed, this does not justify the conclusion that all swans are white.

–Karl R. Popper, The Logic of Scientific Discovery

This passage caught my eye over coffee this morning. I had lunch the day before with Benjamin Kuipers and Satinder Singh Baveja along with associated graduate students. The lunch led to a lively discussion about the notion of “object” in artificial intelligence, and in particular, whether objects provide any durable power in artificially intelligent systems.

Part of the problem seems to be that the term object is difficult to define precisely. My own view (influenced heavily by Ben’s) is that an object is some heterogeneous collection of properties that explain part of the sensory state of a robot, and that a learning process that generates object concepts is some still not well understood collection of perceptual compression and bias. In any event, this somewhat more structured concept of object seemed to satisfy the critique brought up by Satinder, though its hypothetical nature certainly does not rule out alternative approaches.

So what does this have to do with the example above? The problem is with the word swan. What Popper treats as a separate concept from the observations of color is, in my view, actually a composite of the perceptions that we associate with the object. If we consider the example above as involving an assertion about a complex composition of perceptions that comprise a swan, we may find that one particular criteria for being a swan (or more accurately, being labeled as a swan) is that the object in question be white. With this view, we have no need for induction. What we have instead is some sort of set membership, where the observer is simply remarking that the object swan contains the property white. We are replacing induction with affirmation. Color is not a property to induct over, but a percept that summarizes.

Now consider a competing view that discards the notion of object and opts instead for explicit inductive predictions. With this view, observing that the swan is white merely verifies a prediction based on the perceptual history of swans. This view seems to co-opt induction by explicitly representing concepts as things which can be reliably predicted from histories of percepts. Under a possible interpretation of this approach, seeing a white swan and concluding that all swans are white is precisely identical to the way the concept of the swan is built. Under this view, the induction and the swan concept are actually the same, and the example above becomes a truism.

So we have two alternative notions of the object swan, as a set, where induction is instead a kind of (possibly fuzzy) set membership test, and as a prediction based on histories, where induction is the same as the object itself. Both alternatives to Popper are compelling in that they seem to bypass entirely the problem of induction.