Hiding Complexity

post by Rafael Harth (sil-ver) · 2020-11-20T16:35:25.498Z · LW · GW · 14 comments

Contents

  1. The Principle
  2. The Software Analogy
  3. Human Learning
  4. Factored Cognition
None
14 comments

1. The Principle

Suppose you have some difficult cognitive problem you want to solve. What is the difference between (1) making progress on the problem by thinking about it for an hour and (2) solving a well-defined subproblem whose solution is useful for the entire problem?

(Finding a good characterization of the 'subproblem' category is important for Factored Cognition, but for [this post minus the last chapter], you can think of it purely as a problem of epistemic rationality and human thinking.)

I expect most to share the intuition that there is a difference. However, the question appears ill-defined on second glance. 'Making progress' has to cash out as learning things you didn't know before, and it's unclear how that isn't 'solving subproblems'. Whatever you learned could probably be considered the solution to some problem.

If we accept this, then both (1) and (2) technically involve solving subproblems. Nonetheless, we would intuitively talk about subproblems in (2) and not in (1). Can we characterize this difference formally? Is there a well-defined, low-level quantity such that our intuition as to whether we would call a bundle of cognitive work a 'subproblem' corresponds to the size of this quantity? I think there is. If you want, take a minute to think about it yourself; I've put my proposed solution into spoilers.

I think the quantity is the length of the subproblem's solution, where by "solution", I mean "the information about the subproblem relevant for solving the entire problem".

As an example, suppose the entire problem is "figure out the best next move in a chess game". Let's contrast (1) and (2):

2. The Software Analogy

Before we get to why I think the principle matters, let's try to understand it better. I think the analogy to software design is helpful here.

Suppose a company wants to design some big project that will take about 900k (i.e., 900000) lines of code. How difficult is this? Here is a naive calculation:

An amateur programmer with Python can write a 50 line procedure without bugs in an hour, which suggests a total time requirement of 18k hours. Thus, a hundred amateur programmers working 30 hours a week can write the project in six weeks.

I'm not sure how far this calculation is off, but I think it's at least a factor of 20. This suggests that linear extrapolation doesn't work, and the reason for this is simple: as the size of the project goes up, not only is there more code to implement, but every piece of code becomes harder because the entire project is more complex. There are mode dependencies, more sources of error, and so forth.

This is where decompositions come in. Suppose the entire project can be visualized like this, where black boxes denote components (corresponding to pieces of code) and edges dependencies between components.

This naturally factors into three parts. Imagine you're head of the team tasked with implementing the bottom-left part. You can look at your job like this:

(An 'interface' is purely a specification of the relationship, so the ellipses are each less than one black box.)

Your team still has to implement 300k lines of code, but regardless of how difficult this is, it's only marginally harder than implementing a project that consists entirely of 300k lines. In the step from 300k to 900k, the cost actually does scale almost linearly.[2]


As said at the outset, I'm talking about this not to make a point about software design but as an analogy to the topic of better and worse decompositions. In the analogy, the entire problem is coding the 900k line system, the subproblems are coding the three parts, and the solutions to the second and third part are the interfaces.

I think this illustrates both why the mechanism is important and how exactly it works.

For the 'why', imagine the decomposition were a lot worse. In this case, there's a higher overhead for each team, ergo higher overall cost. This has a direct analog in the case where a person is thinking about a problem on her own: the more complex the solutions to subproblems are, the harder it becomes for her to apply them to the entire problem. We are heavily bottlenecked by our ability to think about several things at once, so this can make a massive difference.

For the 'how', notice that, while the complexity of the entire system trivially grows with its size, the task of programming it can ideally be kept simple (as in the case above), and this is done by hiding complexity. From the perspective of your team (previous picture), almost the entire complexity of the remaining project is hidden: it's been reduced to two simple, well-defined interfaces

This mechanism is the same in the case where someone is working on a problem by herself: if she can carve out subproblems, and if those subproblems have short solutions, it dramatically reduces the perceived complexity of the entire problem. In both cases, we can think of the quality of a decomposition as the total amount of complexity it hides.[3]

3. Human Learning

I've come to view human learning primarily under the lens of hiding complexity. The world is extremely complicated; the only way to navigate it is to view it on many different layers of abstraction, such that each layer describes reality in a way that hides 99%+ of what's really going on. Something as complex as going grocery shopping is commonly reduced to an interface that only models time requirement and results.

Abstractly, here is the principled argument as to why we know this is happening:

  1. Thinking about a lot of things at once feels hard.
  2. Any topic you understand well feels easy.
  3. Therefore, any topic you understand well doesn't depend on a lot of things in your internal representation (i.e., in whatever structure your brain uses to store information).
  4. However, many topics do, in fact, depend on a lot of things.
  5. This implies your internal representation is hiding complexity.

For a more elaborate concrete example, consider the task "create a presentation about ", where is something relatively simple:

In absolute terms, preparing a presentation is hard. It requires many different actions that must be carried out with a lot of precision for them to work. Nonetheless, the process of preparing it probably feels easy all the way because every level hides a ton of complexity. This works because you understand the process well: you know what levels of abstraction to use, and how and when to transition between them.

The extreme version of this view (which I'm not arguing for) is that learning is almost entirely about hiding complexity. When you first hear of some new concept, it sounds all complicated and like it has lots of moving parts. When you successfully learned it, the complexity is hidden, and when the complexity is hidden, you have learned it. Given that humans can only think about a few things at the same time, this process only bottoms out on exceedingly simple tasks. Thus, under the extreme view, it's not turtles all the way down, but pretty far down. For the most part, learning just is representing concepts such that complexity is hidden.


I once wrote a tiny post titled 'We tend to forget complicated things [LW · GW]'. The observation was that, if you stop studying a subject when it feels like you barely understand it, you will almost certainly forget about it in time (and my conclusion was that you should always study until you think it's easy). This agrees with the hiding complexity view: if something feels complicated, it's a sign that you haven't yet decomposed it such that complexity is hidden at every level, and hence haven't learned it properly. Under this view, 'learning complicated things' is almost an oxymoron: proper learning must involve making things feel not-complicated.

It's worth noting that this principle appears to apply even for memorizing random data [LW · GW], at least to some extent, even though you might expect pure memorization to be a counter-example.

There is also this lovely pie chart, which makes the same observation for mathematics:

That is, math is not inherently complicated; only the parts that you haven't yet represented in a nice, complexity-hiding manner feel complicated. Once you have mastered a field, it feels wonderfully simple.

4. Factored Cognition

As mentioned in the outset, characterizing subproblems is important for Factored Cognition. Very briefly, Factored Cognition is about decomposing a problem into smaller problems. In one setting, a human has access to a model that is similar to herself, except (1) slightly dumber and (2) much faster (i.e., it can answer questions almost instantly).

The hope is that this combined system (of the human who is allowed to use the model as often as she likes) is more capable than either the human or the model by themselves, and the idea is that the human can amplify performance by decomposing big problems into smaller problems, letting the model solve the small problems, and using its answers to solve the big problem.

There are a ton of details to this, but most of them don't matter for our purposes.[4] What does matter is that the model has no memory and can only give short answers. This means that the human can't just tell it 'make progress on the problem', 'make more progress on the problem' and so on, but instead has to choose subproblems whose solutions can be described in a short message.

An unexpected takeaway from thinking about this is that I now view Factored Cognition as intimately related with learning in general, the reason being that both share the goal of choosing subproblems whose solutions are as short as possible:

In other words, Factored Cognition primarily asks you to do something that you want to do anyway when learning about a subject. I've found that better understanding the relationship between the two has changed my thinking about both of them.


(This post has been the second of two [LW · GW] prologue posts for an upcoming sequence on Factored Cognition. I've posted them as stand-alone because they make points that go beyond that topic. This won't be true for the remaining sequence, which will be narrowly focused on Factored Cognition and its relevance for Iterated Amplification and Debate.)


  1. Be5 is "move the bishop to square E5". ↩︎

  2. One reason why this doesn't reflect reality is that real decompositions will seldom be as good; another is that coming up with the decomposition is part of the work (and in extension, part of the cost). Note that, even in this case, the three parts all need to be decomposed further, which may not work as well as the first decomposition did. ↩︎

  3. In Software design, the term 'modularity' describes something similar, but it is not a perfect match. Wikipedia defines it as "a logical partitioning of the 'software design' that allows complex software to be manageable for the purpose of implementation and maintenance". ↩︎

  4. After all, this is a post about hiding complexity! ↩︎

14 comments

Comments sorted by top scores.

comment by Steven Byrnes (steve2152) · 2020-11-20T19:29:01.310Z · LW(p) · GW(p)

I find it helpful to think about our brain's understanding as lots of subroutines running in parallel. They mostly just sit around doing nothing. But sometimes they recognize a scenario for which they have something to say, and then they jump in and say it. So in chess, there's a subroutine that says "If the board position has such-and-such characteristics, it's worthwhile to consider protecting the queen." There's a subroutine that says "If the board position has such-and-characteristics, it's worthwhile to consider moving the pawn." And of course, once you consider moving the pawn, that brings to mind a different board position, and then new subroutines will recognize them, jump in, and have their say.

So if you take an imperfect rule, like "Python code runs the same on Windows and Mac", the reason we can get by using this rule is because we have a whole ecosystem of subroutines on the lookout for exceptions to the rule. There's the main subroutine that says "Python code runs the same on Windows and Mac." But there's another subroutine that says "If you're sharing code between Windows and Mac, and there's a file path variable, then it's important to follow such-and-such best practices". And yet another subroutine is sitting around looking for UI code, ready to interject that that can also be a cross-platform incompatibility. And yet another subroutine is watching for you to call a system library, etc. etc.

So, imagine you're working on a team, and you go to a team meeting. You sit around for a while, not saying anything. But then someone suggests an idea that you happened to have tried last week, which turned out not to work. Of course, you would immediately jump in to share your knowledge with the rest of the meeting participants. Then you go back to sitting quietly and listening.

I think your whole understanding of the world and yourself and everything is a lot like that. There are countless millions of little subroutines, watching for certain cues, and ready to jump in and have their say when appropriate. (Kaj calls these things "subagents" [? · GW], I more typically call them "generative models" [LW · GW], Kurzweil calls them "patterns", Minsky calls this idea "society of mind", etc.)

Factored cognition doesn't work this way (and that's why I'm cautiously pessimistic about it). Factored cognition is like you show up at the meeting, present a report, and then leave. If you would have had something important to say later on, too bad, you've already left the room. I'm skeptical that you can get very far in figuring things out if you're operating under that constraint.

Replies from: sil-ver
comment by Rafael Harth (sil-ver) · 2020-11-20T20:26:22.597Z · LW(p) · GW(p)

I think your whole understanding of the world and yourself and everything is a lot like that. There are countless millions of little subroutines, watching for certain cues, and ready to jump in and have their say when appropriate. (Kaj calls these things "subagents", I more typically call them "generative models", Kurzweil calls them "patterns", Minsky calls this idea "society of mind", etc.).

Factored cognition doesn't work this way (and that's why I'm cautiously pessimistic about it).

I come to similar conclusions in what is right now post #4 of the sequence (this is #-1). I haven't read any of the posts you've linked, though, so I probably arrived at it through a very different process. I'm definitely going to read them now.

But don't be too quick to write off Factored Cognition entirely based on that. The fact that it's a problem doesn't mean it's unsolvable.

Replies from: steve2152
comment by Steven Byrnes (steve2152) · 2020-11-20T21:00:23.936Z · LW(p) · GW(p)

But don't be too quick to write off Factored Cognition entirely based on that. The fact that it's a problem doesn't mean it's unsolvable.

I agree. I'm always inclined to say something like "I'm a bit skeptical about factored cognition, but I guess maybe it could work, who knows, couldn't hurt to try", but then I remember that I don't need to say that because practically everyone else thinks that too, even its most enthusiastic advocates, , as far as I can tell from my very light and casual familiarity with it.

I haven't read any of the posts you've linked

Hmm, maybe if you were going to read just one of mine on this particular topic, it should be instead Can You Get AGI From A Transformer [LW · GW] instead of the one I linked above. Meh, either way.

Replies from: sil-ver
comment by Rafael Harth (sil-ver) · 2020-11-24T12:27:30.904Z · LW(p) · GW(p)

I've read them both, plus a bunch of your other posts. I think understanding the brain is pretty important for analyzing Factored Cognition -- my problem (and this is one I have in general) was that I find it almost impossibly difficult to just go and learn about a field I don't yet know anything about without guidance. That's why I had just accepted that I'm writing the sequence without engaging with the literature on neuroscience. Your posts have helped with that, though, so thanks.

Fortunately, insofar as I've understood things correctly, your framework (which I know is a selection of theories from the literature and not uncontroversial) appears to agree with everything I've written in the sequence. More generally, I find the generative model picture strongly aligns with introspection, which has been my guide so far. When I pay attention to how I think about a difficult problem, and I've done that a lot while writing the sequence, it feels very much like waiting for the right hypothesis/explanation to appear, and not like reasoning backward. The mechanism that gives an illusion of control is precisely the fact that we decompose and can think about subquestions, so that part is a sort of reasoning backward on a high level -- but at bottom, I'm purely relying on my brain to just spit out explanations.

Anyway, now I can add some (albeit indirect) reference to the neuroscience literature into that part of the sequence, which is nice :-)

Replies from: steve2152
comment by Steven Byrnes (steve2152) · 2020-11-24T16:55:27.420Z · LW(p) · GW(p)

Thanks! Haha, nothing wrong with introspection! It's valid data, albeit sometimes misinterpreted or overgeneralized. Anyway, looking forward to your future posts!

comment by William_S · 2020-12-17T20:57:36.615Z · LW(p) · GW(p)

I think there are situations where you can still have subproblems where the output of the subproblem is long. A contrived example: suppose you have a problem where you want to calculate XOR(f(a), f(b)), where f(a) and f(b) are long strings. It seems reasonable to decompose into x=f(a), y=f(b), z=XOR(x, y), despite x and y being long, because there's a simple way to combine them.

If we had an AI system that could work on "making progress on a problem for an hour", then write down a complete description of everything it had figured out and pass that to another AI system, I'd count that as dividing the problem into subproblems, just in a way that's probably inefficient.

I'd evaluate decompositions into subproblems by something like the total cost of solving a problem by dividing it into subproblems. Some decompositions would be efficent and others would be inefficient, sometimes this would be because the output is large but in other cases it could be because it takes a long time to write the input, or because there's a lot of work repeated between subproblems.

Replies from: sil-ver
comment by Rafael Harth (sil-ver) · 2020-12-17T22:41:54.028Z · LW(p) · GW(p)

This is really good comment. I'm not sure yet what I think about it, but it's possible that the post is not quite right. Which might be a big deal because the upcoming sequence relies on it pretty heavily. I take purely abstract examples seriously.

One thing to note, though, is that your counterexample is less of a counterexample than it looks on first glance because while the size of the solutions to [subproblems of your natural decomposition] can be made arbitrarily large, the size of the overall solution grows equally fast.

If we allow two subproblems, then the optimal decomposition (as defined by the post) would be , , where and denote the first and second half of a string. Here, the solutions to subproblems are half as long, which is optimal.

These subproblems sound like they're harder to solve, but that's not necessarily the case; depends on . And if they can be solved, it seems like the decomposition would still be preferable.

comment by Gurkenglas · 2020-12-01T10:33:19.110Z · LW(p) · GW(p)

Does this mean that humans can only keep a few things in mind in order to make us hide complexity? Under that view the stereotypical forgetful professor isn't brilliant because he has a lot of memory free to think with at any time, but because he has had a lot of practice doing the most with a small memory. These seem experimentally distinguishable.

I conjecture that describing the function of a neural network is the archetypal application of Factored Cognition, because we can cheat by training the neural network to have lots of information bottlenecks along which to decompose the task.

Replies from: sil-ver
comment by Rafael Harth (sil-ver) · 2020-12-01T11:01:33.742Z · LW(p) · GW(p)

Under that view the stereotypical forgetful professor isn't brilliant because he has a lot of memory free to think with at any time, but because he has had a lot of practice doing the most with a small memory. These seem experimentally distinguishable.

Not necessarily. This post only argues that the absolute ability of memory is highly limited, so in general, the ability of humans to solve complex tasks comes from being very clever with the small amount of memory we have. (Although, is 'memory' the right term for 'the ability to think about many things at once'?) I'm very confident this is true.

Comparative ability (i.e., differences between different humans) could still be due to memory, and I'm not confident either way. Although my impression from talking to professors does suggest that it's better internal representations, I think.

comment by slicko · 2020-11-21T05:00:02.450Z · LW(p) · GW(p)

Intuitively, this feels accurate to me (at least for a certain category of problems - those that are solvable with divide and conquer strategies).

I've always viewed most software best-practices (e.g. modularity, loose-coupling, SOLID principles) as techniques for "managing complexity".

Programming is hard to begin with, and programming large systems is even harder. If the code you're looking at is thousands of lines of code in a single file with no apparent structure, then it's extremely hard to reason about. That's why we have "methods", a mechanism to mentally tuck away pieces of related functionality and abstract them into just a method name. Then, when that wasn't enough, we came up with classes, namespaces, projects, microservices ..etc.

Also, I agree that a good amount of learning works this way. I would even point to "teaching" as another example of this. Teaching someone a complex topic often involves deciding what "levels" of understanding are at play, and what subproblems can be abstracted away at each level until the learner masters the current level. This works both when you teach someone in a top-down fashion (you're doing the division of problems for them and helping them learn the subsolutions, recursively), or a bottom-up fashion (you teach them a particular low-level solution, then name the subproblem you've just solved, zoom out, and repeat).

comment by adamShimi · 2020-11-21T18:01:20.481Z · LW(p) · GW(p)

Cool post. I like the intuition of hiding complexity. Indeed, when I think of a low complexity description for what I got from my 1-hour of thinking very hard, the most natural answer is "a decomposition into subproblems and judgement about their solutions".

In other words, Factored Cognition primarily asks you to do something that you want to do anyway when learning about a subject. I've found that better understanding the relationship between the two has changed my thinking about both of them.

Would it be then representative of your view to say that a question can be solved through Factored Cognition iff the relevant topic can be learned by a human?

Replies from: sil-ver
comment by Rafael Harth (sil-ver) · 2020-11-21T18:49:45.671Z · LW(p) · GW(p)

Would it be then representative of your view to say that a question can be solved through Factored Cognition iff the relevant topic can be learned by a human?

Unfortunately, no. It's more like 'FC is inferior to one person learning insofar as decompositions lead to overhead'. And in practice, decompositions can have large overhead. You often don't know how to decompose a topic well until you already thought about it a lot.

comment by Kevin Lacker (kevin-lacker) · 2020-11-21T00:32:21.830Z · LW(p) · GW(p)

I don't think the metaphor about writing code works. You say, "Imagine a company has to solve a problem that takes about 900,000 lines of code." But in practice, a company never possesses that information. They know what problem they have to solve, but not how many lines of code it will take. Certainly not when it's on the order of a million lines.

For example, let's say you're working for a pizza chain that already does delivery, and you want to launch a mobile app to let people order your food. You can decompose that into parts pretty reasonably - you need an iOS app, you need an Android app, and you need an API into your existing order management system that the mobile apps can call. But how are you going to know how many lines of code those subproblems are? It probably isn't helpful to think about it in that way.

The factoring into subproblems also doesn't quite make sense in this example: "Your team still has to implement 300k lines of code, but regardless of how difficult this is, it's only marginally harder than implementing a project that consists entirely of 300k lines." In this case, if you entirely ignore the work done by other teams, the Android app will actually get harder, because you can't just copy over the design work that's already been done by the iOS team. I feel like all the pros and cons of breaking a problem into smaller parts are lost by this high-level way of looking at it.

My null hypothesis about this area of "factored cognition" would be that useful mechanisms of factoring a problem into multiple smaller problems are common, but they are entirely dependent on the specific nature of the problem you are solving.

Replies from: sil-ver
comment by Rafael Harth (sil-ver) · 2020-11-21T11:37:41.872Z · LW(p) · GW(p)

I agree that the analogy doesn't work in every way; my judgment was that the aspects that are non-analogous don't significantly distract from the point. I think the primary difference is that software development has an external (as in, outside-the-human) component: in the software case, understanding the precise input/output behavior of a component isn't synonymous with having 'solved' that part of the problem; you also have to implement the code. But the way in which the existence of the remaining problem leads to increased complexity from the perspective of the team working on the bottom-left part -- and that's the key point -- seems perfectly analogous.

I've updated downward on how domain-specific I think FC is throughout writing the sequence, but I don't have strong evidence on that point. I initially began by thinking and writing about exactly this, but the results were not super impressive and I eventually decided to exclude them entirely. Everything in the current version of the sequence is domain-general.