Crow Intelligence

Consider this thought experiment. If you, with your current mind, were suddenly trapped in a crow’s body, would you ever be able to convince any humans that you were intelligent? Maybe not.

Real crows, of course, have some huge disadvantages. They don’t speak English, they don’t understand English, they don’t have other crows who can teach them how to communicate with humans.

When I was a kid, we learned in school that a key difference between humans and other animals is that humans were intelligent enough to use tools, and other animals could not. That lesson was slightly out of date even in the 80’s, as some examples of chimpanzees using tools had already been discovered. In the age of cheap, portable cameras, we’ve discovered a lot more.

Crows

Personally, I’m interested in crows because there are a lot of crows in the East Bay hills. They fly around my backyard, cawing at each other, and I keep wondering if there’s some underlying code to it.

You can sink a lot of time into watching videos of crows using tools. They can carve sticks into hooks, drop rocks into a pool to raise the water level, and manipulate sticks in their beak in various ways.

How smart are crows, really? In AI we have the idea of a Turing test, where something is human level intelligent if it seems just like a human through a written channel. Crows can’t pass a Turing test, primarily because they can’t even take a Turing test. They can’t communicate in a written channel in the first place.

I feel like it should be possible to demonstrate that crows are far more intelligent than people thought, by teaching a crow to perform… some sort of intelligent action. Like Clever Hans doing arithmetic, but not a scam.

Things That Aren’t Crows

Are crows the right animal to try out intelligence-training? Wikipedia has an interesting page that claims that forebrain neuron count is the best current predictor of animal intelligence and lists off animal species.

The most interesting thing about this list to me is that humans are not the top of the list! Humans are pretty close, with 20 billion forebrain neurons, but killer whales have twice as many, 40 billion forebrain neurons.

What if killer whales are actually smarter than humans? We don’t really understand whale communication. Project CETI is working on it - to me, it seems like the key limiting factor is data gathering. It’s just incredibly time-consuming to collect whale communication because you have to go boat around looking for whales. No matter how fancy your AI techniques are, at the end of the day if you have on the order of hundreds of communications, it seems hard to extract data.

I think you really need some sort of interaction with the intelligent creatures - children don’t just quietly listen to adult speech and suddenly understand it. They start talking themselves, you use simple words communicating with them, you do things together while talking, et cetera. All of that is just really hard to do with killer whales.

So most of the species with a similar number of forebrain neurons to humans are aquatically inconvenient. Killer whale, pilot whale, another type of pilot whale, dolphin, human, blue whale, more whales, more whales, more whales, more dolphins, more whales, more whales. Then you have gorillas, orangutans, chimpanzees, and another bunch of just extremely large animals. The Hyacinth macaw might be more promising. Only three billion forebrain neurons to a human’s 20 billion, but at least they are small.

Crows Again

Checking down this list, the smartest animal that actually lives near me is the raven. Basically a big crow - I think crows are similar, Wikipedia just lists ravens but not crows. Around a billion forebrain neurons. Squirrels can get through some complicated obstacle courses and crows are maybe 20 times smarter. I wonder if there’s some sort of clever obstacle course I could set up, have crows do it, and demonstrate they are intelligent.

As I type this, the crows have started to caw outside my window. I like to think they are expressing their support….

Lines And Squiggles

I previously wrote about searching for signals from other planets in radio telescope data, and thought I’d write about my current thinking.

We have lots of data coming in from the Green Bank telescope, and some other folks and I have been working on the data pipeline. Rather than collecting lots of data and having grad students manually analyze it months or years after the fact, we want to have the whole analysis pipeline automated.

I think for both scientific projects and corporate ones, the best part about automating your data pipeline is not just that you save a lot of human work, it’s that making it easy to do an analysis makes it easy to do an iterative loop where you do some analysis, realize you should change a bit of how it operates, then redo the analysis, and repeat to make your analysis smarter and smarter.

Current Problems

The best way for checking radio telescope data for this sort of signal over the past ten years or so has been a “cadence” analysis. You expect a coherent signal from another planet to look like a diagonal line on the radio telescope data. But you sometimes also get squiggles that look like diagonal lines from noise. So you point the telescope in a “cadence” - toward planet A, then toward random other target B, then back to A, then to random other target C, in a total of an ABACAD pattern.

The traditional algorithm is you write something to detect how “liney” a particular area is, and then you look at the cadence to find a sequence that goes, line, not line, line, not line, line, not line. And then everyone writes lots of papers about how precisely to detect lines amidst a bunch of other noise.

So in practice if you just set your threshold for “lininess” very high, you can get less data to look through, and so you just raise that threshold until the total output is human-manageable. I think in theory this is not quite the right thing to do - there end up being cases where you would clearly evaluate a single image as a line that are below this threshold. Lowering the threshold, though, you get false positives like this:

This is essentially a “threshold effect” - if we just categorize line versus not-line, then wherever we set the threshold, there will be some region that is noisy enough that the lines are only detectable half the time. And then in 1/64 of those cases, the coins happen to flip heads-tails-heads-tails-heads-tails and it looks like a cadence. But, humanistically, we see, oh this is really one single line that spans through all six of these images.

Maybe what we need to be doing is, rather than a two-way classification of “line” versus “not line”, we do a three-way classification of “line” versus “squiggle” versus “nothing”. And then for a cadence we really want line-nothing-line-nothing-line-nothing, maybe we would also be interested in line-nothing-squiggle-nothing-line-nothing, but line-squiggle-line-squiggle-line-squiggle is just uninteresting.

Maybe this example is more a “dot” than a “squiggle”, but I think in practice dots and squiggles are pretty similar. Both of them are things that don’t really look like lines, but also don’t really look like nothing, so it would be an unusual coincidence for one of them to occur where we expect nothing.

Perhaps I’ve lost all my readership at this point, but this is one of those blog posts where the primary value is clarifying my own thinking rather than educating you the reader per se.

Another way of thinking about this problem is, traditional methods of training a classifier don’t really make sense when your labeled data is all negatives. We need to break it down into sub-problems where we actually do have negative and positive examples. But we are breaking it down into the wrong sub-problems, because we need to be able to convert every vague sense of “we should have been able to automatically exclude this case” into an error in sub-problem classification.

To be continued…

Visiting SFMOMA

Near the end of Proust’s In Search Of Lost Time, the main character realizes that his own life can be the inspiration for a great work of literature. During this epiphany, Proust makes a brief digression to talk about art, and how to appreciate art you really need to pay attention not only to the art itself, but also the memories it triggers or the impression that it makes in you, the viewer.

Let me quote a few sentences.

Even where the joys of art are concerned, although we seek and value them for the sake of the impression that they give us, we contrive as quickly as possible to set aside, as being inexpressible, precisely that element in them which is the impression that we sought, and we concentrate instead upon that other ingredient in aesthetic emotion which allows us to savour its pleasure without penetrating its essence and lets us suppose that we are sharing it with other art-lovers, with whom we find it possible to converse just because, the personal root of our own impression having been suppressed, we are discussing with them a thing which is the same for them and for us. Even in those moments when we are the most disinterested spectators of nature, or of society or of love or of art itself, since every impression is double and the one half which is sheathed in the object is prolonged in ourselves by another half which we alone can know, we speedily find means to neglect this second half, which is the one on which we ought to concentrate, and to pay attention only to the first half which, as it is external and therefore cannot be intimately explored, will occasion us no fatigue. To try to perceive the little furrow which the sight of a hawthorn bush or of a church has traced in us is a task that we find too difficult. But we play a symphony over and over again, we go back repeatedly to see a church until - in that flight to get away from our own life (which we have not the courage to look at) which goes by the name of erudition - we know them, the symphony and the church, as well as and in the same fashion as the most knowledgeable connoisseur of music or archaeology. And how many art-lovers stop there, without extracting anything from their impression, so that they grow old useless and unsatisfied, like celibates of art!

The rest of the paragraph is pretty good, too.

Anyway, I used to think that when you looked at art you should use some sort of “evaluating art” skill, the way I would look at the design for a new database and think about whether it seemed like a good database design or not. And it just seemed like I lacked this skill, or found the development of this skill uninteresting. After reading this book I was curious to try out this “Proustian” way to appreciate art, where instead of wondering whether the art was good or not, you just look at it and if it triggers any memories, you think about those memories, see what things you can remember that you haven’t thought about in years, see if the art relates to those memories and if you can dig in somehow.

So last weekend I took a trip to SFMOMA with my 9-year-old son, and I really enjoyed this exhibit of American abstract art, which I never really appreciated very much before.

This piece reminds me of the blackboard in the first math class I took in college. The professor would get really emotionally engaged in writing things on the blackboard while talking about them, and in the process he would seem to stop paying attention to the blackboard itself. Often it would be impossible to distinguish different Greek letters, or different parts of a formula would run into each other.

Rather than completely erase the board, the professor would sort of quickly swipe an eraser and then start writing something else. The blackboard became like the catacombs beneath Mexico City, new buildings constructed on top of the ruins of past generations, with the clever archaeologist able to discern layers of different lemmas and corollaries.

It’s like the subject itself, abstract algebra. Theorems about rings, laid on top of theorems about fields, on top of integers, on top of groups, all above a historical process of figuring this stuff out that resembled the eventual outcome but shuffled around and with a bunch of false starts mixed in there.

Meanwhile, my son enjoyed the sculptures that looked like the sort of armor a bug monster would wear. The only flaw of the trip was the cold and terrible pizza from the kid’s menu at the cafe. Next time, I will encourage him toward the chicken tenders.

Gödel's Incompleteness Theorem, in Bash

Gödel’s first incompleteness theorem states that there are mathematical statements that can neither be proven or disproven. His proof is fairly difficult to understand - it involves prime numbers, factorization, all this number theory. Gödel’s proof had to be complicated because in 1931, computer algorithms hadn’t really been invented.

Turing machines would only be invented in 1936, five years later. When Turing proved the halting problem was undecidable - that there is no program that can decide whether another program will ever finish - Gödel’s work was an inspiration to him. Historically, Gödel clearly came before Turing. But in the modern day, for people who already understand the concept of a “computer program”, it’s a lot easier to understand the theory the other way around. Turing first, then Gödel.

Seeking Paradox In Bash

Many software engineers are aware that a program can run on other programs. For example:

$ wc ./my_program.sh

This elite “metaprogramming” technique uses the program wc to tell you how many lines of code there are in the my_program.sh script.

You can go even deeper into this running-programs-on-programs, and run a program on another program that’s running on another program. For example, if you want to know how long it takes to count the lines of code in my_program.sh:

$ time wc ./my_program.sh

Now imagine a script called behave_differently.sh. When you run it on another program, it outputs something different than that program does. For example:

$ ./behave_differently.sh ./my_program.sh ./my_input.txt

This can output anything at all, as long as it is different from the output of ./my_program.sh ./my_input.txt.

If we can just write behave_differently.sh, then we can write the script paradox.sh:

#!/bin/bash
./behave_differently.sh $1 $1

For any script, paradox.sh my_script.sh behaves differently than running my_script.sh my_script.sh. So what happens when you run ./paradox.sh ./paradox.sh? It’s a logical impossibility. It must be impossible to write behave_differently.sh.

Sanity Check

It doesn’t really seem impossible to behave differently than another script. What goes wrong with the naive approach?

#!/bin/bash
if [[ `$*` == "YES" ]]
then
  echo NO
else
  echo YES
fi

When you run ./paradox.sh ./paradox.sh, the script simply goes into an infinite loop, outputting nothing. You can check my work - the code is on GitHub. The reason it is so hard to behave differently from another script is that you can’t tell, when it goes into a long and silent loop, if that loop is really infinite or not.

The Halting Problem

If we had a script halts.sh that could tell if a program would halt, we could use it to write behaves_differently.sh.

#!/bin/bash
if [[ `./halts.sh $*` == "YES" ]]
then
  while true ; do continue ; done
fi

So it must be impossible to write halts.sh. There you go - that’s the impossibility of the halting problem, which Turing proved in 1936.

Proving an Infinite Loop

Once you see that the fundamental impossibility is writing behaves_differently.sh, it starts to make sense how you can generalize the halting problem a little bit.

Sometimes, you can prove a program goes into an infinite loop. A smart compiler can figure out that some areas of the code are unreachable. If all the parts of the program that exit are unreachable, then a program must go into an infinite loop.

You don’t need to understand all the details, here, you just need to know that it’s possible to build some tools around these proofs. You can represent these proofs in a .proof file format, and there’s a validation script that checks the proof. So when we run:

$ ./validate_proof.sh ./my_program.proof ./my_program.sh

If it returns YES, that means that ./my_program.sh goes into an infinite loop. If the proof isn’t valid, the validator returns NO. The validation script never goes into an infinite loop itself.

The other tool we need is a way to generate all possible files. It can be super slow, that’s fine. So let’s say that this generates a file by converting a big integer to its binary representation:

$ ./generate_file.sh <number>

Putting It All Together

We can try to behave differently from a target script by searching for a proof that it goes into an infinite loop.

#!/bin/bash
i=0
while true; do
  ./generate_file.sh $i > ./possible.proof
  if [[ `./validate_proof.sh ./possible.proof $*` == "YES" ]]
  then
    # The target goes into an infinite loop. Let's behave differently
	exit 0
  fi
  i=$(( i + 1 ))
done

If there is any proof of the target script going into an infinite loop, then this program will eventually find it, and stop. If there is no proof, then it will loop forever searching for a proof.

If every program that infinite loops has a proof that it infinite loops, then we have just written behave_differently.sh. We know that’s not possible. So, no matter what proof system we use, there must be some program that never terminates, but there is no proof that it never terminates. There must be true but unprovable statements, which is what Gödel proved in 1931.

Conclusion

Gödel’s incompleteness theorem is fundamental to the philosophy of mathematics. It demonstrates the mismatch between our ideas of truth and our ideas of proof. It shows us that there will always be a difference between the theoretical idea of truth and the practical set of mathematical statements that we know are true.

I hope that this exposition was helpful to people. Personally, I think we should set aside Gödel’s original number-theory-based proof as an artifact of history, the way we no longer use Isaac Newton’s original notation for calculus. We should accept that the concepts of mathematical proof and computer algorithms are intertwined at their heart, teach the halting problem first, and teach the incompleteness of mathematical proof second.

The Unreality of Pi

To me, there is a mystery at the heart of mathematics. Why does it work? Why does it tell us useful things about the world?

One philosophy is that mathematical truth is like Plato’s Forms, an abstract, perfect truth that exists outside of physical reality. You can think of mathematics as a type of language; it’s language with a convention that any possibility of error is completely forbidden. As Wittgenstein suggests, things we cannot speak of we must pass over in silence. Mathematical language cannot say anything about politics, about current events, about the precise nature of a real-world cannonball lofted through the air, because it’s possible that our observations about these things are mistaken. Burn all this away, and what is left is the mathematics.

This way of looking at mathematics is powerful, but it’s missing something. Think of the greatest drama of historical mathematics, the rise and fall of Euclidean geometry. For about two thousand years, Euclid’s Elements was the main textbook for teaching mathematics. Euclid started with a few axioms for geometry, and proved vast swaths of geometry from these axioms. The one aesthetically displeasing part was the fifth axiom - if you have points ABCD, and ABC and BCD are acute angles, then the rays BA and CD must intersect. In other words, the “parallel postulate” - that for every line and a point not on that line, you can only draw one parallel line through that point.

People thought this axiom was obvious for a long time, and it was only considered aesthetically displeasing that it was so much more complicated than the previous axioms. Mathematicians tried to prove it from the other axioms for a long time, but it turned out this was impossible.

In fact, this axiom is worse than aesthetically displeasing. This axiom is false. With the discovery of special relativity, scientists realized that space is not flat. It is curved. You can draw multiple parallel lines through a point. They just have to be really, really close to each other.

It’s worse than that. “Real numbers” are also not real. Quantum mechanics now tells us that the precision of a measurement is limited. But the rigorous definition of “real numbers” requires an infinite sequence of numbers getting closer and closer. The mathematics doesn’t work if small numbers are prevented from going smaller than the Planck length. A circle of radius 1 doesn’t really have an area of pi - it’s a little bit off.

Euclidean geometry is also no longer considered to be the highest standard of rigor. It’s interesting to look at a modern mathematical computer formalization of geometry, like Lean’s geometry library. Euclid took all sorts of theorems for granted, that the computer insists we prove. How do we know that the angle ABC is equal to the angle CBA? How is the angle ABB defined? If you say it can’t be defined, then every single time you use the angle ABC, you need to prove that A does not equal B, and B does not equal C. Euclid basically ignored this issue, and got lucky in that it never led to a bug in his proofs. Lean decides that the angle ABB should be considered to be a 90 degree angle. But from a modern point of view, geometry is hopelessly messy to make rigorous. It is far cleaner to build up integers, sets, rationals, real numbers, real analysis, and then tack on geometry at the end.

Euclidean geometry ends up being far from abstract mathematical truth. With modern progress in mathematics, we see that Euclidean geometry is not a great approximation of the world, and it isn’t the most rigorous area of mathematics either. We keep it around for historical and teaching purposes, basically.

So how can we explain the fact that for thousands of years Euclidean geometry was the pinnacle of mathematics? We could have another mathematical revolution, where we discover that our current mathematics methods are not great approximations to the world, and they aren’t sufficiently rigorous, either. The value of mathematics cannot lie in the fact that it is an abstract truth. It is the quest for this abstract truth. And the quest for this truth is a human activity. This quest would not exist without people to go questing.

Personally, I suspect that mathematics is on the verge of another revolution like the non-Euclidean revolution. Software will eat mathematics. The standard for mathematical rigor will rise again - any proof that cannot be checked by a computer will be considered insufficiently rigorous. It will be obvious there is a mathematical revolution once the computers knock off a few of the longstanding open problems. Just like nowadays many subareas of physics basically require that you write a decent amount of Python code and become a decent software engineer, in the future mathematics will also grow much more intertwined software engineering.

That’s my prediction, anyway.