Over these past few years I've become increasingly interested in the question of how to learn good compressors. Early on I thought that the problem of figuring out how to make a good compressor for a data stream was "simply" a problem of figuring out how to make a good probabilistic model of the data stream. But after wrangling with the problem for a while I have come to prefer to think about it as learning how to play a peculiar class of 2 player games.

The Structure of Compression Games¶

A compression game is a game with two players. The the first player is called the compressor C and the second player is called the decompressor D. The players take alternating turns.

Before the game starts an external actor picks a message to compress, call it m, which is provided in its entirety to C only. C's turn consists of providing a hint to D which can depend on m and need not be deterministically generated. During D's turn they provide a message to C dependent on the current history of hints, call these messages notions. The game ends when a pre-agreed upon condition is met. For example D sends a special message indicating the end of the game, or perhaps the first hint was of a form indicating the total number of turns to take, etc. After the end of the game the history of messages passed between the two players is fed into a reconstruction process which generates an estimate of the message $\hat{m}$.

At this point the game is scored by assigning an encoding cost to the sequence of hints generated by C. The form of the encoding cost function requires some knowledge about the form of the hints, so I will defer making explicit choices about how to measure encoding costs until after discussing specific compression games. If the rules of the game are such that it is possible for $\hat{m}$ to differ from the original message then you can also add in a penalty term for any differences, in which case you are dealing with lossy compression.

Turning a Compression Game into a Compression Algorithm¶

It may not be immediately clear that you could turn such a game into a usable compression algorithm. The turn structure and the messages sent back from the decompressor to the compressor during the process seem to mess things up.

The usual way of thinking about things is that you can think of the compressor and decompressor as a pair of functions that are approximate inverses of each other. If you wanted to frame this as a turn based game it seems like the natural way to do it is to make the compressor and decompressor each get only exactly one turn, and to let information only get sent from the compressor, no information should come back from the decompressor.

Also, in order to make a useful compression algorithm you need the decompressor player to play deterministically. Since you wouldn't be guaranteed to get the same output file each time otherwise. Which effectively turns the 2 player compression game into a single player game. Since effectively the second player just follows the instructions of the first. That sort of compression game doesn't seem like it would be a very fun game to play (though potentially still a very fun game to design the rules of).

But actually if you take a moment to think about it once you have required that the decompressor should behave deterministically you actually no longer need to require that there should just be one round of turns and/or no 2 way communication. In principle everything the decompressor knows at any point the compressor player also knows. So if the behavior of the decompressor is deterministic and known beforehand, then the compressor can just run an emulation of the decompressor as they play in order to figure out what messages a compressor would send back to them after each turn.

Then the compressor player could just output the resulting stream of hints from the whole multi-turn game on their very first turn, since they can just figure out how the game would play out without needing to actually consult with player 2. So with the additional requirement that player 2 plays deterministically (and their strategy is known to player 1) the multi-turn 2-way communication compression game is equivalent to the single turn single communication direction sort of compression situation that may seem more familiar.

An Aside on Extra Notional Communication Channels¶

I feel it is helpful here to pause for a moment to talk about the absence of a notional communication channel running from the compressor to the decompressor. After all the very same argument about determinism allowing the messages to be passed via emulation of the process that generates them still applies, just so long as those messages don't directly depend on the input target to be compressed. This is certainly true and earlier versions of my thinking about how to best think about compression as a game with learnable strategies included this extra channel of information.

But during deterministic compression mode "notions" aren't really passed from the decompressor to the compressor (though they can be actually passed along when learning to play the game). These messages, and the whole turn based structure, are just one possible way to do a mental decomposition of the compression process. I find that thinking about there being this extra communication channel from player 2 to player 1 helps me think clearly about what is going on, as well as to think creatively about what those messages could be.

While in principle you can also have this extra channel of notional messages passed from compressor to decompressor I found that while I was thinking of these messages as being the responsibility of the compressor to generate, I was constantly wanting to make those messages depend on the incoming message somehow. But that obviously isn't allowed, since the decompressor must be able to reconstruct them purely from the current hint stream history in order for the process to correspond to an implementable compression algorithm.

But if these messages must be always able to be deterministically generated by the decompressor player at any point. Then it seems clear that really there is no effective difference between messages notionally being passed one direction versus the other direction. Both players can have full access to the current stream of such notional messages at all times. So the idea that one or the other player is responsible for generating some portion of those messages is really just a trick of the mind. To me it seems simpler and more clarifying to make all such messages the responsibility of the decompressor, which makes the allowed input domain of those messages obvious. But there are certainly plausible strategies for which it might make sense for some of these messages as being generated by the compressor player. Either way the expressive power of the game is the same.

Example Compression Games¶

Lets take a moment to put some standard compression algorithms into the form of a compression game.

A common framework for a compression algorithm is to utilize a probabilistic next symbol predictor which takes the recent symbols as input.

How does this look in terms of a compression game? One way to do it would be to make the hints emitted by the encoder be the rank order of the correct next symbol. Where the ranks are determined by the predicted conditional probabilities of the next symbol.

Although you could incorporate the calculation of those probabilities into the operation of the compressor I think it is much more natural to give that task to the decompressor. At each step the decompressor considers the current sequence of known symbols and makes a prediction for the conditional probability of the next symbol. The probability distribution over those symbols can then be passed back to the compressor as part of its notion message.

For convenience sake you can consider the decompressor to also pass along its current estimate of the reconstructed message using the hints provided so far. Prior to applying the next symbol predictor each turn the decompressor simply grabs the symbol whose probability rank was indicated by the most recent compressor hint and adds it to the end of its estimated message. Which can then be fed as context input to predict probabilities for the next symbol, and both probabilities and predicted message are passed back to the compressor as the next notion. Then when the estimated message is equal to the true message the compressor can emit a special hint to indicate the end of the game.

That describes the structure of the compressor and decompressor but the complete specification also requires a specification for how to score the hint stream. Even if the next symbol predictor is very accurate we won't achieve any compression simply by replacing the message with a sequence of hints indicating that the top ranked prediction was always correct. We need to somehow decide how many bits on average we should pay for each hint. Arithmetic coding is a method to turn a set of symbol probabilities (potentially changing over time) into a bit stream which uses those probabilities to encode a stream of actual symbols.

You can think of arithmetic coding as being a method that enables you to pay just $-log_2(q)$ bits on average for encoding an event that has an estimated probability of $q$. If it turns out that actually the true probability of those events really was $q$ then this achieves the Shannon limit (Hooray!). If $p \neq q$ then you will end up paying close to on average $E_{x \sim p}[ -log_2(q(x))]$ bits per symbol. Which is the cross entropy between your estimated probability distribution and the true probability distribution.

To carry out scoring you could actually carry out the arithmetic coding procedure and take the length of the resulting sequence as the encoding cost. But the actually achieved encoding length is just an upper bound on the cross entropy. But there is no reason that you couldn't just use the cross entropy directly $\sum_i -log_2(q(x_i | x_{j<i}))$. Since that gives a continuous and differentiable entropy estimate and avoids any sharp edge cases where you end up needing one bit more or one bit less to encode any particular sequence.

Simpler more directly algorithmic compression schemes can also of course easily be turned into compression games. For example in run length encoding (RLE) the hints are tuples of a symbol and a number of times to copy that symbol into the output. Again in this scenario I think it is convenient to make the notion message of the decompressor be equal to the current estimate of the message and the compressor stops when the estimated message and the true message are equal.

This time we don't have access to any estimated symbol probabilities so we can't directly utilize the empirical cross entropy of our predictive model as an encoding cost. One natural encoding cost for run length encoding (or for that matter many possible compressors) is the length of the resulting hint sequence. If we want the encoding cost to be comparable to other methods then it would also be important to multiply by an appropriate proportionality constant. For example if our basic symbols are bytes and we are ok with limiting ourselves to a maximum run length of 256 at a time then we could encode each (symbol, run length) pair using 2 bytes, in that situation we could multiply the total number of such hints by 16 to get a result measurable in bits.

Adaptive Empirical Scoring Methods¶

The selected scoring method is a proxy for the length of a compressed version of the hint stream if we were to go to the trouble of actually implementing a dedicated encoder for it. The nature of that encoder is a very important consideration and significantly changes the structure of the game. In general you will get very different behaviors from using encoders which are indifferent to the actual hint stream from using more adaptive encoders. The strategy of using arithmetic coding on forward prediction probabilities and the 2 byte RLE encoding strategy just mentioned are fixed encoders. Such encoders may work well if we know the statistical properties that the hint stream is likely to have and tailor the encoder to that. But it will often be more desirable to use an encoder that adapts an empirical probability distribution from the hint stream to determine the encoding cost for each hint. For example one could assign to each hint a probability which is equal to the recent frequency of that particular hint in the hint stream.

Such empirical entropy measures have the major advantage that they don't rely as greatly on the accuracy of an predictive probability distributions being used by the compressor/decompressor. So even when our compressor/decompressor is implicitly using a certain probability to predict the next symbol it may actually be better to use a smoothed empirical probability distribution for specific hints learned from the hint stream.

Consider the case of the forward predictive based compressor from before, where the compressor outputs the rank order of the true symbols as hints. If the predictor gives accurate probabilities then choosing to encode the ranks using an arithmetic coding scheme customized to the predictive probabilities will give optimal encoding results. But if there are inaccuracies in the probabilities yielded by the predictive model then we end up paying an overhead in the encoding cost. Suppose for example that we have a model that achieves very good predictive accuracy, ranking the true next symbol first 75% of the time. But it is also very overconfident assigning a probability of 99.999% to all of its top predictions. The 75% of the time that the model turns out to be correct we pay almost no bits to encode that fact. But the 25% of the time that the model is wrong we will end up paying an absolute minimum of $log_2(0.99999) \approx 16$ bits and may end up paying more depending on exactly how unlikely the model thought that symbol was. Adding those two costs together with the appropriate probability weightings gives an estimate of at minimum 4.6 bits to encode each symbol. You can reduce the cost of such overconfidence by smoothing your probabilities to be more uniform but then you also start cutting into the maximum possible compression you may achieve.

Compare this to the use of an empirical entropy scoring method where we simply let each hint have a cost proportional to the logarithm of the frequency with which that exact hint has appeared previously in the hint stream. In that case since our model will give the top rank to the correct symbol 75% of the time then we should expect to pay roughly $-log_2(0.75) \approx 0.4$ bits per correct symbol and at least $-log_2(0.25) = 2$ bits for incorrect top predictions yielding an overall average of 0.8 bits per symbol. Effectively for this ranking kind of hint stream we then end up paying a number of bits which is determined by the empirical error rate of the predictive model on this particular message, which can protect us from paying large encoding overhead costs when encoding messages which don't closely match the probabilities implied by the model. Such empirical entropy measures of the hint stream also have the advantage that they don't depend on the internals of the compressor/decompressor being used and so can be used in any situation.

When using such empirical measures of entropy it is important that you also either are careful to only use entropy measures which use only the past of the hint stream to estimate future probabilities, and or add some amount of cost for encoding the parameters of the assumed underlying probability distribution as a necessary overhead independent to the cost of encoding each individual symbol. For example consider the seemingly innocuous choice of using an empirical hint probability model simply be equal to the empirically observed frequencies of hints over the whole hint stream. If you don't also consider the cost to encode the possible hints and their probabilities then a single hint consisting of the entire message to be transmitted would have a predicted probability of 1 and so have 0 encoding cost for that specific hint. That is fine as far as it goes, but in order for that to make sense one must also pay some number of bits to encode the table of hints which would of course in that particular case make up all of the encoding cost for that hint stream.

There is, of course, a standard set of systems that learn empirical distributions of data streams and then use them to come up with efficient ways of encoding those data streams, those would be compression algorithms. So one may also opt for a scoring method where the hint stream is first serialized in any convenient manner, for example as a json object, and then fed to some standard compression program, for example gzip. The encoding cost is then the size of the resulting artifact. This may seem like cheating since we have used a compression algorithm to score a compression algorithm but really it is just a nice way to keep from having to fuss over all the details of getting a robust entropy estimator just right for each and every possible hint language we might want to play with. If ever we find a compression game strategy with a json->gzip scoring method we can be confident that it will be possible to make a high performing compressor from this strategy by just utilizing gzip as a post processing step.

One may be tempted to think that using a more powerful compressor to carry out the scoring would also tend to yield superior results, but one must consider the fact that complex compressors also imply complex structures that achieve maximum compressibility. With a compression scorer the purpose of the compressor does not become to make the hint stream as short as possible but rather the task becomes to make the hint stream have a structure which is as compressible as possible taking the scorer into account. For this reason it may actually be desirable to err on the side of making the scorer utilize only very simple kinds of statistical structure, as this may simplify the problem of learning to make hint streams which mesh well with the scoring method.

Why Think of Compression as a Game¶

So we can turn most (if not all) existing compression algorithms into the form of a turn based compression game. But why would we go to the trouble of thinking about the game as though it were multi-turn when the space of possible single turn and multi-turn compression functions are the same either way?

I think there are a couple different advantages. This method of mentally partitioning a compression algorithm into different responsibilities, hint generation, notion generation, and hint stream encoding, is very helpful for me personally. While it isn't too hard to come up with interesting compression algorithm ideas when thinking in terms of a monolithic compressor -> decompressor sort of execution structure, I find that it is much much easier to come up with a wealth of ideas when thinking about things with the richer structure imparted to the problem by thinking about it as a compression game.

I find that my thoughts go to much more interesting places when I start by asking; What could a language of hints or a language of notions possibly look like? Rather than by starting to ask a question like; What are flexible and efficiently estimable probability distributions for my data? It is that second mindset of explicitly modeling probability distributions, which I think is the default mindset for thinking about compression within a ML framework. But although there might always be some sort of implicit probability distribution underlying the rules of any compression game we can come up with that doesn't mean that we need to understand that distribution in order to make compressors that work well. In fact, if I try to think of rules for a compression game that might be fun for two humans to play, they correspond to completely analytically intractable probability distributions. But games like Chess and Go are also analytically intractable (that is what makes them fun to play) but that hasn't stopped us from learning to make AI that can play them.

Also although thinking about how to model the probability distribution for our data, is very interesting and very important. But direct explicit probabilistic modeling of our data should not be the only sort of learning technique in our repertoire when thinking about learning to compress. Compression games don't require thinking about things from a probabilistic perspective at all, though they also very easily accommodate probabilistic thinking if desired. So compression games seem to me to be a more general sort of framework for thinking about learning to compress than can be accommodated simply by learning predictive probabilities.

Similarly in both the purely algorithmic setting and the probability distribution centered ML setting it seems that either the compressor or decompressor tends to be "dumb". By which I mean that either the compressor or the decompressor tends to act in a deterministic manner which is simple to understand and reason about. Then with the behavior of one of the two possible players in the compression game fixed you can begin to reason from first principles about how the other player should play in order to achieve optimality.

In the algorithmic setting I would say that the compressor tends to be where all the complexity lies, with the decompressor simply being a simple program that follows the instructions of the compressor blindly. In the typical ML scenario on the other hand in my way of thinking of things the complexity is almost all in the decompressor. Because as I have already talked about, carrying out probabilistic predictions about the data content seem most naturally to be a task carried out by the decompressor and sent as a notion to the compressor player. Which makes the task of the compressor to simply mindlessly compare the predictions to the actual message and indicate how well they line up.

But intuitively this seems like a huge waste of possible directions for optimizing performance. We shouldn't just fix the strategy of the compressor or decompressor and then only optimize the other one. If we simultaneously optimize both the compressor and decompressor strategies to work well with each other we may be able to achieve much better performance than if we only ever think about optimizing one or the other.

Superintelligence by Nick Bostrom is a book tha makes the argument that it is of extreme importance that we proceed cautiously when trying to make AI that may become more intelligent than we humans are. I completely agree with that general premise but I disagree with the details of almost every argument in the book. That isn't to say that I think that the book is badly written, nor necessarily poorly reasoned, but I think some of the underlying assumptions are flawed. Most of my disagreements with the arguments in the book come from the primacy given to the nature of goals and the implicit connection to utility as a decision making or motivational framework. But Superintelligence certainly isn't missing an in depth discussion of goals and their nature that is very much a central theme of the book. But I also can't easily and concisely give a critique of exactly why I think that we need to replace the theory of goals and utilities in thinking about AI. My thoughts on that are still in flux and a decent treatment of my thoughts there might require more of a book length treatment rather than a blog post like this one.

However there was one topic that I feel is incredibly important to the discussion in the book which which doesn't get anything more than passing mention. That topic is computational complexity, more specifically, the question of whether or not some questions are irreducibly computationally hard or not which usually goes by the short hand of the P vs NP problem.

Bostrom's Superintelligence in a Nutshell¶

The argument in Superintelligence runs something like this;

1) We should expect the growth in the level of intelligence of AIs to be exponential 2) So once AI is close to as smart as we are it will "shortly" be millions of times smarter than all of humanity put together 3) The capabilities of something millions of times smarter than all of humanity will be incredible! 4) Controlling something/someone much smarter than you is hard or perhaps impossible 5) So you should instead attempt to ensure that AI you make want things that you also want.

You can group the first three points together as saying that AI is likely to have what Bostrom calls a fast take off scenario, and the last two points are an argument in favor of focusing on what you can call the AI alignment problem.

I want to emphasize that I very much agree with the last two points. You can't or shouldn't want to try and directly control something that thinks much more effectively than you. Which means that what we really need is to figure out how to make intelligent agents which we are confident share our values. That is to say we really need to solve the alignment problem and the stakes are high.

A Digression on Utility and Rationality¶

I want to take a momentary digression from the main point of this post to say that to make progress on the alignment problem I think it is very important that we question more deeply what it means to have something as a goal or equivalently what it really means to "want" something.

Utility theory is a tractable mathematical model of motivation and it is the current defacto technical answer to the question of what it means for a machine (or a human) to hold a goal. But I have become personally convinced that we must at least partially abandon utility theory in order to make real progress on the alignment problem. There is strong evidence that human cognition does not respect the rules of utility theory. In the past violations of utility theory have been held up as evidence of human "irrationality". But we should be careful not to be tricked into thinking that to think "rationally" and to have behavior that is consistent with an abstract mathematical concept of a utility function is one and the same. The people that invented the utility theory of rationality did not think it was a completely valid model of human cognition!

But often the idea that there could be any other, non utility based, understanding of motivation and decision making is often just not considered at all in modern discussions of AI, Bostrom's Superintelligence is no exception. Although Bostrom mentions several alternatives to vanilla utility theory in the book they are all really just proposals for creating utility functions which are "safe" in some sense. So these alternatives to utility theory are really just adornments to it, but the underlying assumptions all still remain. In particular the assumption that no matter what the behavior of an agent, it is possible to think of that behavior in terms of an associated implicit function of "goodness" which dictates the decisions made. This need not in general be true, isn't true for humans and I have come to think that the focus on figuring out how to create good utility functions is mostly just a distraction. In my opinion the real challenge we should be tackling is learning to create AI that operate in the absence of explicit utility functions!

I have come to personally call agents whose behaviors can be completely reduced to a maximization of a utility "mercenary intelligences", because they only do what they get "paid" to do by their utility function. Much of Bostrom's Superintelligence can be seen as an extended argument that such creatures are very dangerous. The behaviors implied by utility functions are almost impossible to directly reason about because the optima of those functions may include almost arbitrarily bad unforeseen side effects. So we should be extremely leary to give a large amount of power to any agent whose behavior is dictated by any utility function even if that utility function seems to us to be innocuous.

The opinion expressed in the book is that this means we really need to ramp up our efforts in figuring out how to make AI with utility functions that are both safe and in alignment with desired futures. My opinion is that we should heed the warning that any creature whose sole motivation is the maximization of a definite utility is a potentially dangerous one. We can never be sure that any particular utility is safe or desirable no matter how we construct it. So what we really need to be doing is to figure out how to make intelligences that don't rely on utility as their motivational mechanism, only those sorts of AI have the potentiality to also be safe collaborators, mercenary intelligences will always require supervision and control to be safe.

You can expect more from me in the future on the topic of how one might tackle thinking about AI with motivational mechanisms which violate the axioms of utility theory but, for now, digression over.

The Missing Chapter, Computational Complexity¶

But even though I think a careful rethinking of utility and alternative motivational frameworks is very important, I can hardly fault Bostrom for not including it because utility based thinking has become so very dominant, and the alternatives are almost non-existent. However there is a very well established field of study which is barely mentioned but which has huge implications for the arguments in the book. That field is computational complexity. You could call computational complexity the study of how intrinsically difficult problems are to solve.

Without going into much technical detail you can partition well defined computational problems into "easy" problems, and "hard" problems. A problem is "easy" in some sense if it belongs to the class of problems denoted P and a problem is "hard" if it is in the class NP. Exactly what is meant by easy and hard or P and NP isn't really important at the moment. What is important is that it is known that if you could solve any of the hard problems in an efficient way then you can solve all the hard problems efficiently. That is because (to some extent just by the definition of the class of NP) you can always transform any NP hard problem into a special subset of these problems which are in some sense maximally expressive, these are the NP-complete problems, so called because they are flexible enough to encode any other NP complete problem. So if an algorithm exists to solve any NP-complete problem efficiently then that same algorithm would form a kind of "master algorithm" that could efficiently solve every sort of problem. The current thinking is that no such algorithm exists, though we don't actually have a proof of that. The hypothesis that some problems really are just intrinsically difficult to solve goes by the shorthand P $\neq$ NP and the hypothesis that there really does exist a master algorithm which would turn all hard problems into easy ones is the hypothesis that P=NP.

If a problem is in P then roughly speaking if you double the amount of computation you apply to the problem you also tend to be able to solve significantly larger instances of that same kind of problem. On the other hand for a problem in NP if you "only" double the amount of compute power you are throwing at the problem you will only be able to solve very slightly larger instances of it. Mathematically speaking the difficulty of solving problems in P increases like a polynomial (that is why that class is called P) whereas the difficulty of solving problems in NP is thought to increase exponentially (NP stands for non-deterministic polynomial, which essentially just means that the solutions to that problem are efficiently verifiable).

Up until I read Superintelligence I had been rooting for the underdog P=NP since if someone were to discover such a "master algorithm" it would immediately have massive applications in absolutely every field of human endeavor. It would suddenly unlock orders of magnitude improvements in the design and analysis of just about any technology imaginable. Up until reading superintelligence there was really just one down side that I could see to it turning out that P=NP was true, and that was that modern cryptography as we know it would essentially become impossible. The amount of chaos that would cause would be considerable but the benefit of being able to efficiently solve just about any imaginable problem seems almost unbounded in its potential upsides. But after reading Superintelligence I came to a somewhat startling conclusion, if P=NP then a fast take off AI scenario is plausible and a really powerful AI could experience an exponential explosion of capabilities in a short time which, as Bostrom argues, could be really quite a bad thing. Seen from this light the idea that probably P $\neq$ NP is actually something we should be very relieved that we think is actually true. Because it protects us from the possibility of an exponentially fast take off scenario of the sort envisioned in Bostrom's Superintelligence. Although I disagree in lots of the details I definitely do agree that such a scenario is unlikely to end well.

I can't help but quickly mention a surprising connection for me to the Fermi paradox here. Bostrom argues that it seems very likely that an AI could rapidly exceed our intelligence in all domains once it achieves something close to parity with our intelligence. Furthermore such an AI would then likely want to maximize some kind of intrinsic utility (an assumption that I have already signaled disagreement with in this post). In the quest to maximize just about any utility Bostrom argues that the AI would want to gather as many resources as possible because of the instrumentality of that goal (which is just a fancy way of saying that the more resources you acquire the better you can achieve any goal). These things together make an argument that a utility optimizing superintelligent AI would want to start dominating the solar system and then the Galaxy, so that it can put all its resources towards its goal (to reuse an example, the total number of paper clips in existence). But for me this immediately poses a kind of Fermi paradox, which is to say we see no evidence of poorly aligned maniacally utility optimizing superintelligences out there in the Milky Way. Which seems to be a point of evidence in favor of the idea that either fast take off AI scenarios like Bostrom envisions are either actually very unlikely, or possibly there just aren't any intelligent aliens out there (something which I find very unlikely). For reasons that I hope will be clear before the end of this post I take this lack of apparent alien superintelligences to be a kind of weak evidence that in fact P $\neq$ NP. Which I think is a very amusing connection.

Optimization Power and Recalcitrance¶

In Superintelligence Bostrom argues that the increase in intelligence (and therefore the increase in AI capabilities) is going to be exponential in time. The discussion in the book deals with a competition between two different kinds of forces which the author dubs optimization power, and recalcitrance. What he calls optimization power is a measure of effort applied to increasing the intelligence of AI. Recalcitrance is the force opposing the optimization power, in effect it is the amount of effort needed to increase the intelligence of an AI by the next little bit. If the recalcitrance is high relative to optimization power then the improvement in AI will proceed slowly and if recalcitrance is low relative to optimization power then improvement will be rapid.

Bostrom argues that we should expect the optimization power to increase exponentially over time. This is true for several reasons. Most obviously perhaps is just that recent decades have seen an exponential increase in computation power per dollar, and we have good reason to think that trend will continue at least for the short term. Also as AI is seen to be of increasing value we will put ever larger amounts of raw resources into working on AI, especially as it seems like the advent of something resembling superhuman intelligence may be achievable. Lastly and perhaps most importantly once an AI is at least as smart as the engineers working on it then the AI itself may become the most significant source of self optimization power and if we think that the AI is exponentially more capable over time then eventually this component of the optimization power could come to dominate. I think that the first two reasons are correct, but I take some amount of issue with the self improvement argument, about which more below.

To expand a little bit about the exponential increase in computational power over time, Moore's law is the most famous of these exponentially increasing computation related quantities, and one often hears that Moore's law is coming to an end (or has already come to an end). That statement is often taken to mean that we are coming to the end of the era of exponentially increasing compute power but this isn't quite right. Moore's law says that transistor density tends to increase exponentially in time, but that is just one of many different computation related quantities which has enjoyed a run of exponential improvements. Other kinds of computation related quantities have already stopped their exponential increase. For example Dennard scaling was the reason that the clock speeds of our processors used to be increasing in lock step with the increased density of transistors. But higher clock speeds also mean higher heat dissipation and our cooling solutions haven't kept up and so Dennard scaling stopped holding true around 2006. You might expect that to also have corresponded to a slow down in the rate of increase of compute power available per dollar at around the same time. But, actually if you take a look at the history of compute per dollar the rate of improvement actually sped up around 2006 instead of slowed down. The reason being that as it became increasingly difficult to make individual processors much more powerful we transitioned to leveraging hundreds of individually less powerful cores on the GPU. Simply increasing the total number of cores doesn't run afoul of any fundamental laws of nature (or at least not as quickly) and now we are up to thousands of cores on each individual chip, and soon advanced packaging techniques will mean we will have multiple chiplets per package as the norm. I wouldn't be surprised to find that a few decades from now it has become common for computers to incorporate parallel compute components like current GPUs which effectively have millions of small compute cores. But then again perhaps this trend of exploding core count will stop short for reasons that I just can't see clearly from my present perspective. But no matter what technologies and compute paradigms come to dominate in the decades to come clearly we are not yet close to saturating the exponential growth period of computational technologies.

Before tackling the question of how recalcitrance might evolve I think a little more discussion about how intelligence relates to capabilities is in order. When we talk about intelligence in humans it is usually assumed that as you increase intelligence you increase capability in many and various tasks. But intelligence doesn't universally improve performance in all tasks. Likewise improvements in capabilities to achieve certain classes of tasks don't necessarily indicate an increase in any sort of intelligence. So for example a smarter person is likely to be better at doing algebra but being smarter won't necessarily give increased capabilities in long distance running (though there are likely some second order effects here, e.g. better pacing, more effective training regimen, etc). Likewise great skill at, say, dancing isn't often summarized as saying that someone has great intelligence (though we may say they have great "kinesthetic intelligence" or that they are a "brilliant dancer").

Usually here one would invoke the idea of general intelligence. General intelligence is supposed to boost just about all activities (though perhaps not all activities equally) whereas specific kinds of intelligence (e.g. kinesthetic intelligence) boost only specific kinds of tasks. In humans there does tend to be a strong correlation between capabilities of various kinds, a person who is exceptionally good at one thing is often quite good at many things. But that correlation stops short of evidence of a causation and general intelligence in humans may well mostly be a confluence of joint causes of performance that just don't generalize outside of the context of our very human shell. For example, being well rested, being in generally good health, and even a small amount of short term stress all are known to correlate positively with (and one is very tempted to say that they cause) improved performance in all sorts of mental tasks. But even though being in generally good health and sleeping well cause strong performance correlations in many different tasks it feels strange to say that they constitute a kind of "general intelligence" factor. But then again in a machine context simply just upping the computational resources available to an AI (say by increasing the depth of some search or optimization process) would almost certainly increase performance in many different tasks and could also be said to form a basis for a kind of general intelligence factor amongst AI in a way not too different from the way that good health could be said to be a general intelligence factor in humans. This sort of general intelligence factor can be thought of in terms of just increasing the amount of resources being applied to achieve a task. Such an increase in applied resources should of course generally correspond with an increase in performance.

Usually though general intelligence is thought to be something more akin to a kind of efficiency of thought rather than in terms of total resources applied. If you think very efficiently then fewer resources of thought, be they biological or artificial, will be required to achieve any particular level of performance. One may suppose (as is often supposed) that general intelligence has a meaning which is closer to this concept of efficiency of thought. In humans it is difficult to try and disentangle resource based GI from efficiency based GI. We don't really have a human equivalent of number of compute cores or CPU clock speed, and really the best candidate for such a thing would be something like an IQ score which is supposed to be a measure of general intelligence. So we can't really compare two humans are known to have the same computational resources to try and figure out differences in how efficiently they think. Not to mention existing knowledge or priors about what sorts of things to think about may help in certain cases (and would dramatically increase apparent efficiency of thought in those cases) but may be a hindrance (and cause relatively lower apparent efficiency of thought) in other cases. Never the less it probably stands to reason that there likely are also factors of general intelligence which act primarily along this dimension of efficiency in some way. For example someone who has undergone training in analytical thinking is likely to be better at formulating good questions to ask themselves and that seems likely to be something that will yield performance increases in many different sorts of mental tasks, and so would also constitute a form of general intelligence factor. One which could operate in iso-resource situations and could make for a kind of efficiency of thought.

For the discussion in Superintelligence for the most part the question of exactly what constitutes general intelligence is eschewed in favor of simply discussing specific kinds of capability that an AI may have and the consequences of having such a capability improve exponentially over time. It is argued that many different kinds of capability, when honed to an extreme level, can actually substitute for other apparently different sorts of capability. For example consider the ability to quickly solve incredibly complex logic questions with billions of symbols and billions or trillions of clauses relating those symbols. Such an ability can rather obviously be used to solve something that we often think of as being "logic puzzle like" for example solve a sudoku. But it may be less obvious that you could use such a capability to also prove or disprove mathematical theorems, create efficient configurations for electrical circuits, or optimally solve very general kinds of general constrained optimization problem. This is because you can transform all of those kinds of problems into a representation as a kind of huge logic puzzle and then transform it back to a more natural problem representation after the solution. If this makes you think of the situation with NP-complete problems it should, it is precisely the same reasoning. But, now we have replaced the idea of a "master algorithm" with a "general intelligence". Now it should be noted that figuring out exactly how to formulate some real world context as a discrete symbolic problem is something that is currently mostly out of the reach of AI. Furthermore there are many many different sorts of mental task that we currently have no reasonable way to translate into a definite rigorous computational problem of any sort (e.g. we can't make acting as an empathetic therapist into a logic puzzle). So we should still view the idea that superintelligence of one sort is substitutable for other sorts. But even though there could still be thorns lurking it seems both plausible, and to my mind even likely, that this substitutability of capabilities holds true. Perhaps with some sort of high penalty for transforming between different sorts of complex task. This may not be the case but lets go ahead and grant this supposition for the moment. If it is not true then we would need to think differently about every sort of non-substitutable capability that AI might be able to gain and that is a long philosophical path that I am not going to even try to tread in this post.

Now finally we are in a position to talk about recalcitrance. Recalcitrance is just supposed to be the cost to increase intelligence by the next little bit, and now that we are allowing ourselves the assumption of substitutability of mental capabilities (at least when those capabilities are taken to extremes) we can see that the argument is that we don't really need to consider the recalcitrance of different capabilities separately, it suffices to just consider what is likely to be whatever is the path of least resistance. Bostrom tries to analyze the difficulty of increasing performance in several different sorts of hypothetical intelligences with different sorts of capabilities and comes to slightly different answers in different situations. But in general his analysis suggests that recalcitrance may grow only slowly and if that is the case then the capability of an AI would grow exponentially fast and that leads us to a place where humans are outclassed by AI in nearly every way and in a very short time frame.

P $\neq$ NP Implies Explosive Recalcitrance¶

But in order for the capabilities to be substitutable for other complex capabilities they must include as a subclass NP-complete problems. It wouldn't make any sort of sense if some superintelligent AI could write novels and proofs of deep mathematical theorems, but was for some reason completely unable to solve mildly difficult logic puzzles. Lots of things which we consider to be important mental capacities lie very close to the domain of some NP-complete problem or another, that is in part why we were studying those kinds of problem in the first place.

But taken from the perspective of computational complexity our current thinking about these sorts of problems has an immediate consequence for Bostrom's concept of recalcitrance. Recalcitrance should be expected to increase exponentially with linear increases in capability, if that capability is sufficiently flexible that it could be substituted for another complex capability. This is based on the idea that NP-complete tasks are a subclass of what you might call AI complete tasks and so recalcitrance in those tasks must in general be at least as hard as NP-complete tasks are. If the current consensus in computational complexity holds then P $\neq$ NP and the recalcitrance of these tasks therefore grows exponentially quickly with increased capability (technically just faster than any polynomial but lets not split hairs).

Which means that even in the face of exponentially increasing resources being devoted to AI (that is to say exponentially increasing optimization power to use Bostrom's terms) we should expect only linear increases in capabilities in general. There may be certain capabilities which could well explode exponentially, for example there is no reason that an AI couldn't recall exponentially increased amounts of information as its physical memory resources grow exponentially. We would of course expect that to be the case. But recall isn't a fundamentally hard problem and certainly by itself does not constitute a substitutable, or perhaps we should say AI complete, task. But many of the things that are seen as being of fundamental importance for high intelligence, for example planning and general kinds of optimization, do fall into the class of things that can improve only linearly over time, even in the face of exponentially increased applied resources.

Note that this is exactly what has been happening in the recent history of AI, we have been steadily improving performance in various kinds of metrics over time, but that improvement has usually been linear with exponentially increased applied resources not exponential. There have of course been specific sudden jumps in performance where we get large increases in performance at the same level of applied computational resources because of paradigm shifts in how we build models. For example the transformer paradigm has led to large jumps in performance (though some of that performance also could be attributable to the much larger compute footprint that transformer models tend to occupy). But such paradigm shifts could be seen as contributing to a sort of increase in the efficiency of thought that we considered earlier. While it is theoretically still possible that you could make enough improvements to that efficiency of thought that you could start solving fundamentally hard problems without requiring exponentially large computation resources such an increase in efficiency would imply that P=NP.

It is also worth taking a moment to think about how fundamentally difficult it is to give an AI some amount of cognitive improvement. If the task in question is simple and the relationship between the internal workings of the AI and its behavior is also simple then in many situations improving the performance of the AI would fall into the category of computationally simple problems. This is also consistent with the idea that it is very possible to make the performance of an AI increase exponentially with exponentially increased applied resources if the problem in question is simple enough. But of more interest is the question of how hard it is to increase the general intelligence of an AI, or somewhat equivalently, increase its performance on any one complex substitutable task. If the difficulty of that self improvement task is anything other than exponentially explosively difficult then the above arguments about the difficulty of other problems doesn't apply. But notice that by definition if such a computationally efficient self improvement algorithm were to exist it would constitute the aforementioned master algorithm that can solve NP hard problems quickly. The master algorithm being to just self improve an AI until that AI can solve NP hard problems efficiently. Again while it is theoretically possible that such a self improvement algorithm exists it would imply P=NP and so seems unlikely, and in light of the potential dangers of the rapid take off scenario of superintelligent AI we should probably be grateful that is so.

A question that I have recently been using to guide my thoughts about AI and intelligence in general has been to stop and ask myself whether or not I think some particular thing is absolutely required for recognizable intelligence.

In the past I was much more likely to be pondering a question more in the form of; "What are modern AI missing?". Framing the question this way invites me to think of any of the myriad slippery mental concepts that we tend to apply to humans or animals and then try to figure out which of these things is most valuable, and which of these qualities might potentially be made mathematically rigorous, measureable, implementable etc. But this well of thought is almost infinitely deep. You can very comfortably spend years reasearching mechanisms for memory, or symbolic reasoning, or something a little more off the beaten path like how to incorporate "playfulness" into an AI system.

You could call this mode of thought the "additive" approach to AI because you can just keep generating capabilities, or properties of AI that you might like to tackle and add them in to the AI toolbox one at a time. One hopes that when we have accumulated enough knowledge about enough mental capacities then we will have finally achieved understanding of what intelligence really is. Certainly if we somehow manage to figure out how to give a single AI all of the mental capacities that we have has humans then we certainly will have made an incredible stride towards the understanding of intelligence in general. Though I worry that even if such a feat were to be achieved the complexity of such a system may make the interpretation of exactly why and how it works almost as hard as figuring out what is really going on in the human brain.

But even more importantly the additive approach I think is actually a very poor guide as to what avenues of research are most promising to pursue. For example consider the three candidate mental capacities mentioned above; memory, symbolic reasoning, and playfulness. All of these seem incredibly important to my mind. I would have a hard time to pick just one of these three to pick as being more important than the others for future research (though just for the record I think I would have to pick the concept of playfulness because it seems to me to capture much of what modern AI are missing that biological RIs possess).

When stuck purely in the additive mode of thinking I might spend a lot of time thinking about exactly what the right way to make each mental capacity precisely measurable and also how one could implement such a capacity for an AI. I think that this mode of thinking is very natural and can be a very productive direction for research. But I have recently come to think that it is really important to also spend a moment to follow up and ask yourself the subtractive question, "Am I sure that this is really necessary?".

In fact I find that for myself personally a much more powerful version of this same question is;

Can I imagine a recognizable intelligence which does not have this mental capacity?

In this form the question has started to really change the way I think about what it means to be recognizably intelligent. Consider those three example mental capacities I mentioned above; memory, symbolic reasoning, and playfulness.

Memoryless RI¶

First up memory, is it possible for me to imagine an entity which I think I would clearly recognize as being intelligent if I was allowed to interact with them, but which does not have a memory? My gut reaction without putting much thought into it is that of course any RI would absolutely need a memory! If there is no memory then there can be no learning, which seems rather important. But I think it is good to give extra scrutiny to things which feel like the "must" be true but for which you have no hard proof. Putting a little thought into what a powerful but memoryless intelligence might be like one of the first things that comes to mind is actually the modern transformer based LLM. I want to stress that I'm not saying that modern LLMs pass the test of being recognizable intelligences (for me they do not yet qualify as RI). Rather I'm saying that I do not feel that I can rule out a possible future in which something very much like our current LLMs does qualify as RI, though I would be very surprised if that turned out to be true.

If we are including the training process as part of our considerations then I would definitely say that LLMs have some sort of memory, since they will learn to reproduce documents from their training data. But if you consider an LLM operating purely in inference mode with no updates to its weights then any text which was previously input to the LLM has no effect on future outputs and so in that sense an LLM can be said to have no memory. You could argue that the input contextual data is actually acting as the memory of the LLM since in principle it could be used to represent a history of interactions with the model. I think that is a fair argument in a sense but even if you want to think of it as acting as some sort of effective memory it certainly is a strange sort of memory. So I think one could make a strong argument that future very strong LLMs could eventually constitute an example of an RI which is also effectively memoryless.

But for me there is a much more compelling example of memoryless RI, humans brain damage that prevents memory formation. For example consider the story of https://en.wikipedia.org/wiki/Clive_WearingClive Wearing</a> who has short term memory of 20-30 seconds but who cannot form any long term memories. If I ask myself the question of whether or not I think Clive is really recognizably intelligent in the way that I am, I have to say yes.

To me this is an extremely surprising answer. Because it means that we can delete memory off of the list of things that an RI absolutely must have. There is of course an important nuance here since in both of the examples we just considered there is an initial learning phase during which some form of implicit or explicit long term memory was present and in both cases there is the presence of some sort of effective working memory (though that is debatable for the LLM). But even so this seems to me to be a compelling argument that actually even though memory is extremely important to the application of intelligence perhaps it isn't one of the single most important things that should be focused on if the goal is to create a minimal clearly recognizable intelligence.

Non-Symbolic RI¶

What about symbolic reasoning, could I imagine some sort of entity which to me would seem definitely recognizably intelligent but which was completely incapable of symbolic reasoning?

In the very most general sense I think there may be reason to argue that a "symbol" is anything which has a representational relationship with something other than itself. So by that very broad definition, yes, absolutely every intelligent entity must have symbols of some sort. Because an intelligence which couldn't represent anything couldn't think anything. Such an entity might be better regarded as constituting a part of the environment instead of being an agent acting in the environment.

But when I say "symbolic reasoning" I'm talking specifically about a kind of rule based manipulation of discrete objects and relationships between objects. So for example any sort of thing that might go by the name of an "algebra" or a "calculus" consists of ways of manipulating what I'm calling "symbols" and any system that can manipulate those symbols (well or poorly) has some level of symbolic reasoning.

The first place my brain goes thinking about this is to think about whether or not extremely sophisticated symbolic manipulation capabilities would tend to increase the likelihood that I personally might give some putative RI my stamp of approval. So for example suppose that I'm interacting with a system which has access to an integrated Boolean satisfiability solver. If that AI were also able to translate interesting real world questions into satisfiability problems (and to be clear this transformation would very frequently be possible since satisfiability problems are known to be NP-complete) then the ability to solve those problems would give the AI a boost. A not very powerful solver could find solutions to Sudoku puzzles, and in principle a very powerful solver (really almost infeasibly powerful) could be used in principle to play a perfect game of Chess or Go or any other deterministic perfect information two player game.

But I am suspicious that the thing which really looks like the sort of intelligence I could recognize is actually the ability to transform interesting real world problems into solvable Boolean satisfiability problems in the first place. So having extremely sophisticated logical capabilities could no doubt be very useful to an RI, however I'm not convinced that logical capabilities are actually necessary for an intelligent entity to be RI.

Another direction of thought which also makes me suspicious of the need for symbolic manipulation for RI is the historical overemphasis (in my opinion) of the importance of language to thought. Human language is very comfortably symbolic and likely our language influenced our invention of the more rigorous kinds of symbolic reasoning like logic and various kinds of algebras. Similar to this vein of reasoning I think that it is entirely plausible that creatures which are very smart but which do not have (so far as we can tell) any sort of complex language also may not have sophisticated symbolic reasoning capabilities. But never the less such creatures can pass the test of being clearly RI. The prime example of this for me is the octopus. Octopi do have a rudimentary sort of language based on displays which involve changing the color and texture of their skin and placement of their tentacles. But octopi aren't social creatures and it seems that there are just a hand full of kinds of sentiments, like threat displays, that they may want to communicate with each other. But despite an apparent lack of language octopi are very curious and like to solve puzzles. But those puzzles are physical in nature not logical in nature, give an octopus a fun little physical toy to play with that has a clever opening mechanism and they will probably figure it out. Try to teach octopi to solve sudoku puzzles for bits of fish and you will probably be out of luck.

So although I am not at all certain about it, I think that it is very plausible that RI do not require any sort of sophisticated symbolic reasoning capabilities.

Unplayful RI¶

Humans are playful (or at any rate the small ones are). Furthermore I think that playfulness is actually very key both to why humans ended up as intelligent as we are. Moreover it is a huge part of how I tend to recognize intelligence in other humans. Someone who has a compulsive tendency to tackle puzzles and/or invent puzzles of their own also tends to be someone with high intelligence. Though I think it is important to consider the argument that potentially the causal arrow in humans actually points the other direction. Perhaps the more intelligent you are the more likely you are to enjoy tackling puzzles. But really I'm not talking about high intelligence per say so much as I'm talking about just a compulsion to play with things, be they physical objects or mental constructs. You don't have to give a baby a reward in order to make them interested in stacking blocks, toggling switches, figuring out how to fit things together, etc, etc.

If I try to envision an intelligent entity without playfulness the purely logical robot characters of Asimov like https://en.wikipedia.org/wiki/R._Daneel_OlivawDaneel Olivaw</a> come to mind, or for a more recent reference someone like commander Data from star trek. But of course such fictional characters cannot give me much empirical evidence one way or another, they are just mental archetypes which I can't help but envision. Also because they are fictional characters it is easy to nearly completely separate the properties of curiosity (of which both of these aforementioned characters have in abundance) from the property of playfulness, but in AI we could build in reality those two properties seem likely to me to be very difficult to achieve independently from each other.

If it isn't already clear from the way I have talked about it so far, I am convinced that thinking carefully about playfulness is a potentially very important direction for future AI research. Of the mental capacities I've mentioned so far I think playfulness might be the most important one. However, I am not certain that playfulness is strictly required for RI. The argument is more or less the same as the argument for memory. Some amount of experimentation and or learning is probably very useful for achieving apparent intelligence. But just like memory if you turn off the tendency for experimentation and learning at some point that does not make the resulting entity unintelligent. To put it another way adults that have lost their sense of playfulness and/or curiosity about the world still retain a recognizable kind of intelligence. So even though I think playfulness may be an essential part of what has made humans the way we are, I again have to come to the conclusion that yes I think it is not hard to imagine entities that are not playful and yet are still clearly RI.

Minimal Capacity RI¶

This way of thinking inevitably gives rise to the question of what sets of mental capacities constitute a minimal set of capacities that an RI could have? I think this is very much in contrast to the usual way of thinking about making progress in AI in which we simply want to add more and more capabilities and mental capacities. From my perspective a completely minimal artificial RI (ARI) would likely tell us a great deal more about intelligence than an ARI which had enough mental capacities to pass the Turing test. The reason being that minimal examples are just much easier to analyze. But more importantly a minimal RI seems likely to be much easier to achieve than something as complex as human like cognition.

I think the process of trying to get rid of aspects of intelligence which may not be absolutely essential may be somewhat paradoxically just as fruitful and enlightening as continuing the more standard march forward to figure out how to incorporate ever more mental capacities into new AI using new approaches. This is not to say that I think there will be much of a cottage industry of papers where people remove capabilities from existing AI one at a time (though now that I say it who knows? maybe that would be enlightening). Rather I'm just trying to make an argument that carefully thinking about whether or not everything we associate with intelligence (human or otherwise) is really actually necessary to recreating it.

You would think that after 70+ years of the study of artificial intelligence (not to mention thousands of years of relevant philosophical discourse) we would at least have arrived at a usefully precise consensus definition of what "intelligence" really is. But unfortunately this simply isn't the case. I've been writing a lot about intelligence lately and I find myself constantly spending irksomely large amounts of time carefully considering what sort of adjectives to put in front of "intelligence" in order to make my point with sufficient precision. Am I talking about "general intelligence"?, "human-like intelligence"?, "human-level intelligence"? Inevitably, because I don't really have a good way to make absolutely rigorous definitions of any of those things, I find myself going back and changing the terms I'm using. Often completely rewriting what started out as relatively clear sounding sentences to remove troublesome words like "intelligence", "understanding", or "meaning". The rewritten sentences may have more rigor but they almost always suffer dramatically in clarity and brevity.

To help rectify this situation I'm going to start using "Recognizable Intelligence" or "Recognizably Intelligent" (RI) as a subjective term for talking about intelligences which either I, or an abstract reasonable expert human, would eventually come to regard as being intelligent with enough interaction and evaluation. That is to say an RI is a "know it when I see it" kind of intelligence. You could view RI as being intelligence that passes a kind of very relaxed version of the Turing test. Instead of requiring that a putative intelligent agent be able to perfectly indistinguishably emulate a human mind you just require that the expert judge would eventually give their stamp of approval of being "recognizably intelligent" whatever that means to that particular judge.

Examples of Recognizable Intelligences¶

Just to help elucidate what I mean by RI, I think it will be helpful to give some examples. Obviously humans of various flavors are clearly RI even though they can have dramatically different sorts of intelligence from each other. But for me personally I would also definitely include many animals, dogs, cats, octopi, ravens, etc. Your own personal evaluations may vary. Since RI is a subjective evaluation that is fine. For me I think that most insects simply wouldn't qualify. I am not at all convinced for example that a fruit fly is not just basically a set of finely honed reflexes and for me that is just not enough to qualify it. Likewise the most recent batch of LLMs like GPT-4 are clearly missing something that I think is important in order to give my whole hearted stamp of approval. It may well be the case that GPT-4 is smarter in some sense than your typical octopus but whatever that intelligence is I don't recognize it, it is in some ways perhaps an even more alien kind of intelligence than an octopus. I can reason about the goals and thoughts of an Octopus but LLMs just don't seem to think the way we do, if it is fair to say that they think at all.

Why not AGI?¶

I think the immediate first question a lot of people might have is why don't I use the phrase "General Intelligence"? There are two reasons; 1) We don't have any better definition of what it means to be "general" than we do what it really means to be intelligent, and 2) I'm not at all convinced that humans really do qualify as "general intelligences" or for that matter that a truly general intelligence (say an embodiment of an AIXI agent) would also necessarily be recognizably intelligent to us humans.

To elaborate a little on that first point, a really rigorous definition of "general" is either almost useless or itself not really rigorously definable. Without going into too much detail a perfectly good (but useless) definition of generality is that a "general" intelligence should be at least as good at predicting patterns as a completely random predictor (a consequence of the fact that almost all functions are Kolmogorov random). But this of course doesn't capture what we really mean when we say that an intelligence is "general". We of course want a general intelligence to be able to gainfully tackle "any" sort of problem but what we really mean is that it should be able to tackle just about any "natural" sort of problem. But then of course figuring out what the sort of distributions of "natural" problems looks like may very well be harder than figuring out how to make an intelligence that can solve problems like a human. For a much more in depth version of this argument and a discusion of various flavors of what "generality" really means consider giving Francois Chollet's "On the Measure of Intelligence" a read. He more or less comes to the conclusion that a good useful definition of what it means to be generally intelligent (though he does not actually employ that phrase) is to have priors that enable rapid learning of certain kinds of useful patterns. Since we really only have the one consensus example of human intelligence as to what such a set of priors might be he ends up supporting the idea that to tackle making truly general AI we should figure out how to tackle making AI that think in a human like way, with human like priors about the world. On this point I agree in principle. But as a guiding principle for new research I think we need to aggressively resist what I see as a rather myopic focus on intelligence as simply being defined as whatever it is that our human minds do.

Don't We Need a Rigorous Definition of Intelligence?¶

You may ask why on earth am I spending all this time trying to lay out an argument for an imprecise subjective definition of intelligence. If the problem is that we don't have a rigorous consensus definition of intelligence that will help us make progress in AI research shouldn't we be trying to better hone objective and rigorous definitions of intelligence?

Counterintuitively I think the answer to that question is no. I think the best way to make my argument might actually to be to go ahead and let none other than Alan Turing mock what is essentially what I have here called recognizable intelligence. This is the first few lines of the famous paper in which what we now think of as the "Turing test" was proposed.

I propose to consider the question, "Can machines think?" This should begin with definitions of the meaning of the terms "machine" and "think." The definitions might be framed so as to reflect so far as possible the normal use of the words, but this attitude is dangerous, If the meaning of the words "machine" and "think" are to be found by examining how they are commonly used it is difficult to escape the conclusion that the meaning and the answer to the question, "Can machines think?" is to be sought in a statistical survey such as a Gallup poll. But this is absurd.

Turing couldn't hope to cut through the millennia of philosophical arguments about what intelligence, understanding, meaning, or thinking etc really were simply by trying to make some set of rigorous definitions. It was clear to him that no such set of definitions could ever really even have a chance of achieving something like consensus without also first having achieved some sort of empirical support. So instead he tried to side step the need to talk about what really constitutes thinking or intelligence all together. All at once he had given permission to the researchers in the decades to follow to be able to pursue the creation of intelligence in machines without needing to even try to define what intelligence really is.

Now my working definition of RI does differ from Turing's mocked "Gallup poll" in at least one important aspect. Like Turing I think it is very important that the person making the evaluation of intelligence should themselves somehow be an expert judge. Say Geoff Hinton, or Gary Marcus would be examples that come to mind. Someone who doesn't really study cognition or who has no real understanding of what might be going on under the hood of an AI agent is going to be easier to fool, and since we have made the task of fooling ourselves into thinking that an AI is actually a human a central challenge of AI for the past 70 years it is even more important now than ever that the person making any assessment of intelligence is in some sense an expert tester. I don't think that we need to make any sort of specific criterion for what constitutes such an expert however, anyone who considers themselves an AI researcher I think should qualify.

Why We Need RI as a Term¶

Why do I think this is important? Well, as I've already mentioned I am tired of using phrases like "truly intelligent" and then second guessing myself. I think that there are just too many flavors of intelligence to really nail them all down. Sort of similar to how I don't think it really makes sense to talk about "general" intelligence as being any one well defined thing I don't think there is any one thing that is true intelligence. Likewise I think that researchers have used the goal of achieving human intelligence as a target as a bit too much of a crutch.

Because, I think that the Turing test has over time morphed into a sort of Turing mandate. First achieve human capabilities in some task and then you have strengthened the argument that however you achieved that capability is somehow causally connected to whatever real intelligence is. But I think this is stifling the conversation somewhat. In my opinion we don't necessarily need to be able to mimic humans perfectly to understand what intelligence really is. Moreover I think we have finally hit a sort of threshold where we will start to see AI that become incredibly good at seeming human without really having anything like human cognition running under the hood.

Turing argued that if human behavior could be achieved then of course intelligence must also have been achieved. That argument was a necessary defense of the then young and vulnerable field of AI. The scientists of that day could not afford to waste time rehashing the previous centuries of philosophical arguments about the nature of minds. In that setting putting on the cloak of unassailable objectivity by rigorously defining tasks and then one by one creating machines that could match human performance in those tasks was the right approach to take back then, and for many decades thereafter. But I think we have arrived in a different era where we need to begin really taking a hard look at what we think intelligence is. In order to facilitate that conversation I think it may actually be worth while to embrace terms for which we admit we do not have precise objective rigorous definitions while we are still figuring things out. Maybe "recognizable intelligence" isn't quite the right abstraction but it seems like a useful one to help with my own thinking and writing at least.

Over the past few years ideas have been piling up in my notebooks and as half finished blog post drafts and paper drafts. More than once during the past few years I have been actively working on an idea in my free time only to see a fleshed out version of that same idea (or one very much like it) get published by someone working at DeepMind or Facebook AI a few months later. Sometimes this was demoralizing since it meant that I could no longer be the first to publish some novel idea. But more often than not it felt like an invitation, evidence that my ideas were worth pursuing more agressively. Even when the published papers were in very close alignment with my own unpublished musings there always felt like something I could add, a direction of investigation that seemed important or obvious to me but which wasn't being addressed. For example I was recently working on a series of related ideas in which the weights in a neural network are themselves the outputs of another network. A few months later I saw this paper and a few months after that another paper in which the authors train a network to generate the weights for other networks. But, although the idea was very much the same, the approaches are very different than what I had in mind and I think that my approach may even work better. But I was never going to find out unless I could find the time and energy to spend more than a couple of hours a week working on it, I want in on the fun!

Also, I have been thinking more and more about how much I was learning over time and how much creative work I was producing and comparing it to other periods of my life. By far the year of my adult life in which I learned most rapidly and did the most creative work is the year of transition between grad school and taking an ML job in industry. The first two years of grad school and the first year as a professional ML scientist might be competitive if you consider only the raw rate of learning. The first couple years of grad school made me revisit all the physics that I wasn't quite ready for on first exposure as an undergrad (I'm looking at you Hamiltonian/Lagrangian mechanics) and I found on second exposure what had been quite impossible to grasp now regularly just seemed to click into place. Likewise my first year as a professional ML scientist I had to quickly become very proficient in a whole host of skills and technologies that I previously had little exposure to (git, docker, CI/CD, SQL, API design, monitoring/alerting, airflow, pulsar, ... ) not to mention the absolute torrent of business jargon and hyper specific company information. But although I learned a ton in both of those periods of time but my creative output was relatively low. It is hard to tackle open ended questions when you are flooded with an endless series of very specific seemingly urgent questions like "What is the value of this integral?" or "How do I use a docker volume?".

When I compare the level of creativity of ideas I see in my notebooks from the year in between grad school and work the difference is night and day. Even compared to the later years of grad school (where in principle producing creative and original thought was my overarching goal) the difference is stark. In the year after grad school I gave myself permission to explore more freely. Instead of feeling constant intense pressure to pursue only those ideas which were expedient I suddenly felt free to pursue whatever ideas I found compelling. The resulting increase in terms of raw rate of learning, creativity, and my personal happiness was dramatic.

If I look back on the past three years working on ML in industry it isn't the production ML systems which I value most (though there are some aspects of those systems of which I am proud). It is the creative and seemingly useless things that I have done of which I am by far the most proud. The perfect example is the correspondence between binary trees and hyper-spherical polar coordinate systems that I wrote up on the train headed to/from work. The correspondence seems so straightforward that I would actually be quite surprised if I was the first person to ever notice it, but, I have certainly never seen it used before by anyone other than myself. At first glance this might look like a useless mathematical curio. After all why would any one want a lot of different high dimensional spherical coordinate systems? For that matter why would anyone want a single high dimensional spherical coordinate system in the first place? I think the answer is clear; no one really does, or more to the point no one yet knows that they do want such a thing. Because to me a flexible family of ways to reparameterize the unit sphere in any number of dimensions sounds like something I absolutely want in my toolbox. I may not yet have found a great application for it (and maybe I never will), but it seems so compelling and beautiful that I don't care if I never do get much use out of it.

Looking at things from this perspective it seems that I've gotten the mixture of how to spend my budget brain power budget all wrong. I have been spending the overwhelming majority of my brain power on the most seemingly urgent (and frankly sometimes inane) problems and questions of the moment. But I deeply want to be able to spend more of my time on the things which I find most compelling (like pursuing "real" AGI), even when those things are seemingly useless (like turning binary trees into coordinate systems) or perhaps impossible (like achieving "real" AGI).

Ideally I would love to land a job that affords me the freedom to explore compelling novel ideas, something like a research scientist position at a place like DeepMind. But, without a strong collection of publications in prestigious ML publications landing such a position seems very unlikely. In principle I could have continued trying to write up ideas as paper drafts in my spare time but that hasn't been working out so well for me recently. Even if I do manage to squeeze out a paper draft once every other year by giving up nights, weekends, and vacations one paper isn't likely to be enough to successfully re-aim my current trajectory. So I decided it was time to take a little leap of faith. I quit my job so that I can focus on the things that I find most compelling and turn some of the things in the ever growing pile of interesting ideas into prototypes, papers and blog posts.

March 14 marked the first day of another year of transition, a year of time to focus and think. I'm perhaps a little late in my announcement of my intent to the world. But, I couldn't help but immediately dig into some ideas that I've been saving up and seeing if they really work out (turns out some of them do!). Now two weeks in and with some paper drafts under way I've relaxed enough that I feel ok to slow down and officially acknowledge this moment.

The end of the year is just around the corner once again and like the last two years I'm continuing the tradition of putting out some end of year posts. The blogging blitzes of the past two years have each generated only a couple of posts each and calling them "blitzes" is really being quite generous. To make matters even worse this year I'm not even actually planning to take any off any time off to devote specifically to blogging.

But I really like the tradition of getting some year end blogging in and if broadcasting my intent to the world in these announcement posts helps give me the kick in the butt I need to squeeze out even one more post before the year end then I think it is worth it.

Lets get blogging!

Deep Learning 101¶

SLC Python Meetup: June 2, 2021¶

Read more…

If you could see into the high dimensional abstract space of all possible sudoku boards what would it look like?

Read more…

Several years ago I was waiting for Great Fountain Geyser in Yellowstone to erupt. We ended up needing to wait several hours for the eruption (but boy was it worth it, earning Great Fountain a status as my favorite geyser in Yellowstone).

Around 45 minutes in to the wait a group of people came to sit behind us and soon after I overheard one of them tell a riddle that kept my mind happily occupied for both the next several hours until the eruption. The riddle as I originally overheard it went something like this,

100 prisoners are given the following deal: Each day one of them will be selected at random and taken to a room with a single light bulb. That prisoner will be given the option to turn the light on or off and will then be asked if they are certain that all the other 100 prisoners have been in the room. If they answer yes and are correct then all the prisoners will be set free, If they are incorrect then all the prisoners will be executed. The prisoners are allowed to discuss their strategy prior to the beginning of this process but once one of them is taken into the room all communication between the prisoners will be cut off.

What strategy should they agree upon?

Read more…

This is the first of a (hopefully long) series of very short posts whose purpose is to communicate a simple trick I often find useful.

Tip: The argsort of a permutation is the inverse of that permutation¶

Isn't that obvious?¶

You may think that this little nugget of information is completely obvious. You may be right. After all argsort returns the indexes into the array that will put it in order, which means that the argsort of the permutation gives the indexes into the permutation array which would undo that permutation, which is the inverse permutation by definition.

But I think this is only obvious in retrospect. A google search for "calculating the inverse of a permutation" yields things which are more likely to be useful to you if you want to know about the theory of permutation groups. Things like this and this. Even if you add in "in Python" to the end of that search you end up with things like this where the top answer is a python for loop which will be incredibly slow compared to just using argsort. To be fair lower down in the answers to that same question people recommend using argsort as a faster alternative and if you append "in numpy" instead of "in python" to the same search the top result uses argsort.

Some years back when I was trying to figure out how to calculate the inverse of a permutation I ran into only the first sort of search results which gave me the impression that coding up something to calculate an inverse permutation would be somewhat complicated and I just avoided it. But eventually it occured to me that argsort, a function I use all the time, was actually exactly what I had wanted all along. So for all you people out there that have gotten stuck in the theory of permutations (which by the way can be absolutely fascinating), you don't need to know anything about permutation theory or cycle notation or any of that, just use argsort.

Permute Compute Revert¶

If you didn't happen to land on this post via a google search for "how to calculate inverse permutations" then you might be thinking that this information has only very niche applications. But if you do data analysis in python you might be surprised just how useful this trick can be. I frequently will want to know a piece of information which is dependent on a rank ordering of various aspects of my data and more often than not I find that first permuting the ordering of the relevant information doing a (usually now simple) calculation and then applying the inverse permutation to the results can sometimes save me hundreds of lines of complicated buggy multiply indexed code with lots of python for loops and replace it with a couple of lines of simple numpy vectorized operations.

Although I may not use this paradigm as much as the "split apply combine" style of data processing embodied in the pandas group by operation. This "permute compute revert" style of transformation is just about as useful for dealing with relative rank order information as groupby is useful for dealing with group derived information.