Computer system simulation
From InterSciWiki
Contents |
[edit] Problem Statement
From the statement of purpose I wrote as part of my grad school application:
"Max Weber suggested that the success of bureaucratic organization is due to its technical superiority over other forms of organization. Superiority refers to the precision, speed and reduced costs with which the organization carries out its objectives. These factors support the “calculability of results”, which is a fundamental advantage both for the organization itself and for its social environment. Weber also suggested that bureaucratic organization increases its advantage over other forms of organization with the growth in both size and complexity of the social environment in which it operates.
These views seem antiquated in current popular culture. Bureaucratic organizations are often characterized as being slow and inefficient in comparison to smaller, less hierarchical organizations. The first question that interests me is how to reconcile these opposing characterizations.
My suggestion is that these views can be reconciled in part by reference to the complexity of the various activities undertaken by the organization. Activities that involve the repetition over and over of well-defined tasks conform to Weber's description. Examples include providing health care for well-understood clinical conditions, or the roll-out of a newly constructed computer system to a user community. Results in these cases are generally predictable, and if the scale of the activity increases, e.g., from one hospital to ten hospitals, a proportionate increase in resources will continue to generate calculable results. Economies of scale may make it possible to achieve the desired results for less than a proportionate increase in resources.
On the other hand, activities whose tasks are not well-defined do not conform to Weber's description. My intuition is that these involve passing beyond a “threshold of complexity”, at which point, results turn abruptly negative. An example is the construction of a new computer system. My observation is that this kind of activity crosses the complexity threshold of bureaucratic organizations once the scope of the system grows beyond a certain size. As the scope of the system grows, the organization allocates proportionately more resources, but these resources are not proportionately effective. Not only do the expected economies of scale not materialize, the results are often negative -- a team that is ten times larger may produce less useful code than a team a tenth its size, and will frequently fail to deliver any working code at all.
I have observed this pattern first-hand a number of times, and there is a long public history of spectacular failures in building large computer systems. I suggest that this type of poor performance is a major source of the negative public image of many bureaucratic organizations. In my experience, bureaucracies do not distinguish effectively between tasks for which bureaucratic mechanisms are well-suited and those for which they are not well-suited. There remains an unquestioned assumption within bureaucracies that bureaucratic mechanisms are the most effective way to accomplish all the tasks that an organization faces. Experienced managers will recognize and attempt to manage the risk associated with projects of large scope and poor definition, but their actions will be bureaucratic – some combination of attempts to limit scope, and addition of resources. Once again, building computer systems is an example of an area where bureaucratic mechanisms are sub-optimal. The empirical evidence strongly suggests that bureaucracies do not produce the best systems, and are less cost-effective for the results they do produce. The largest computer system ever built, the Internet, was not built bureaucratically. Much of the best software currently available was built through open source efforts, which are not organized bureaucratically."
I've been trying to figure out how to simulate this problem.
[edit] A starting point
Brian Arthur defines a technology as "a means to fulfill a human purpose" (Arthur, 2007). This covers a very broad range of human artifacts, including computer systems. We speak of such things as having been "designed", i.e., put together deliberately to serve a purpose. In the biological world we see complex structures that serve a clear function. For example, an eye has the function of gathering light and converting it to signals a nervous system can interpret. Although there is a lot of debate in non-scientific circles about whether such structures could be said to be "designed", biology has no need to invoke a designer. Evolution is sufficient, given sufficient time, to generate very complex structures. We characterize evolution as "blind", by which we mean that there is no forward-looking mechanism at work to define how a structure should ultimately work. Instead, genetic variation is introduced, resulting in incremental changes, each of which must prove its survival value. After many incremental changes we might recognize something as having resulted in a new structure of which we might speak "it's just as if someone had designed it".
Although at some level invented technologies and evolved structures appear similar, Arthur argues that the genetic algorithm of evolution is an unlikely mechanism to drive the process of technological invention. Instead, he argues that "Technologies are put together or combined from component parts or assemblies." In collaboration with Wolfgang Polak (2004), he simulates the evolution of new technologies, in the form of logic circuits. "New elements are formed by combination from simpler existing elements (circuits), and if a novel combination satisfies one of a set of needs it is retained as a building block for further combination. We study the properties of the resulting buildout. We find that our artificial system can create complicated technologies (circuits), but only by first creating simpler ones as building blocks." This process of building simple components (e.g., an Exclusive Or) and then using them to build more complicated components results in getting to a relatively complicated artifact, e.g., an 8-Bit Adder, in much less time than would be required to evolve it without intermediate components, using a genetic algorithm.
The simulation is very carefully structured -- the algorithm is driven by a set of goals, which are the truth tables that define the behavior of all the components. When these truth tables match those of components proven through experience to be useful (e.g., 1-bit-adder), the algorithm works quickly. If some of the truth tables are random sets of inputs and outputs, progress is slower. This suggests that although the algorithm does not "design" new technologies, design has some place in the simulation -- the intermediate and final goals are "designed". So, although Arthur's simulation captures an important attribute of the process of developing new technologies, that it consists in essence of combinations of other technologies, it does not yet incorporate the notion that technologies are "designed". This is an essential part of the distinction between biological structures that evolve blindly, and technologies that are developed by humans. In this sense, a genetic algorithm and Arthur's algorithm for the combination of simpler components are both evolutionary, in that they proceed blindly to try many combinations, retaining only those that perform relatively better. Neither incorporates the process of design into the algorithm.
[edit] Design
What does it mean to design a technology? Design is "the process of originating and developing a plan for a product, structure, system, or component" wikipedia.
"Designing normally requires a designer considering aesthetic, functional, and many other aspects of an object or process, which usually requires considerable research, thought, modeling, interactive adjustment, and re-design." (ibid)
That sounds hard to simulate, so why bother? After all, if we squint hard enough, and wait a sufficiently long period of time, technologies that are consciously designed might not be distinguishable from structures that evolve blindly. My suggestion is that the process of "designing", of "planning", goes on all the time in human activity, and produces particular kinds of results, that differ in important ways from the results of blind evolution.
[edit] A beginning
A simple definition of the elements of the design process for a new technology might be:
Abstraction:
- An abstraction is developed of the situation pertinent to the purpose of the technology to be developed
Induction:
- Observation of events in the world results in forming a pattern, a generalization about the behavior that has been observed
Association:
- The pattern may be found to match one or more other patterns from past experince, based on the similarity of some attributes of the patterns
Deduction:
- The logic of the original pattern or an associated pattern is then applied to the target abstraction, generating propositions that could be tested.
The set of propositions so generated is the design. The design is then implemented -- actions are taken on the basis of the design, resulting in some changes in the world -- a new technology. The performance of the technology is observed, and compared to the original design. The successful performance of the new technology will in general follow the degree to which the design mapped well to the structure of the original situation. The power of design is that it enables us to bring to bear previously successful patterns on new situations, and thereby focus our efforts on those actions that the patterns predict are likely to have good results. The success of mathematics and the various physical sciences derives from their long track record of accurately predicting the performance of new technologies. Over and over, this has enabled humans to avoid spending the efforts necessary to try all paths blindly.
I don't think any of these processes -- abstraction, induction, association, and deduction -- is uniquely human, but I would suggest that the ability to use these processes to design new technologies is a fundamental key to the success of the human species.
[edit] The Problem Domain
To begin with, we need a problem domain -- a situation with behavior for which a system is to be developed. Perhaps anything that generates non-trivial behavior would do. Wolfram (2002) discusses the behavior of one-dimensional cellular automata. Although the rules that govern their behavior are very simple, they generate a range of behavior, from trivial to very complex (examples). Briefly, the cellular automaton outputs a row of cells on a grid, with values "on" or "off", following a pattern of this form: to find the value for each cell, look at the value of the cell immediately above it, and that cell's two neighbors. For example, one pattern might be "if the cell above is off, and its left neighbor is on and its right neighbor is off, then the new cell is on". It takes 8 patterns of this type to cover all the combinations possible for three cells with two values. As the output of any one of the eight patterns is independent from the output of the others, there are 256 combinations of patterns and outputs. Wolfram calls each such combination a rule, and numbers them from 0 to 255. At right is the output from Wolfram's rule 30, after 36 steps of execution.
[edit] Building the System
The simulation will start with one or more of these rules -- these are the "problems" to be solved. At each step in the simulation, each problem will generate another row of output cells. The simulation also includes agents, whose goal is to build a system to capture as much of this "behavior" as possible. The agents will spend "energy" in their attempts to capture the problem behavior. They will gain energy when they successfully capture the behavior, and will lose energy when they fail to capture the problem behavior. After a certain number of steps, the overall success of the simulation is evaluated. Although agents act individually, they are evaluated as a group. This matches our notion that systems are built by teams of individuals, who succeed or fail collectively.
[edit] Agent Characteristics
Agents have some characteristics that are intended to reflect the capabilities and limitations of humans. Agents will be said to have some built-in understanding of the world; in particular, agents "know" that behavior is produced by a cellular automaton rule. This matches our current understanding that aspects of the way that the world works are built in to the mental processing of animals, including humans. For example, our visual systems treat differences in light along a continuous line as delineating the edges of solid shapes in the world (Pinker, 1997).
Agents differ as to how well they can "reason" about a situation. Agents also differ as to how much effort they spend in communicating with other agents. This matches our experience that different people are good at different things.
Agents are limited as to the time and amount of processing that they can perform on information in any given step of the simulation. In their working memory, agents can manipulate seven "chunks" of information at one time, plus or minus two. Agents can "think" for a finite period of time in each step, but must then make a decision, and act.
Agents have a memory of what they have observed and done. Different memories are linked to one another through associations between similar qualities. Memories also have a negative or positive quality, depending on the outcome of the problem(s) with which they are associated.
Agents communicate with each other about the problems they are working on or their memories of past projects. Communications may be descriptions of states of the world, or prescriptions for actions to be taken.
[edit] Agent Processing
The agents' efforts to capture problem behavior can be through either manual processing or automated processing, or a combination.
- Manual processing: an agent moves to the cell "in front of" the cell that is to be generated in a given step. Manual processing is indifferent to the value of the cell -- cells may be either on or off. This matches our notion that manual processing is flexible -- "we can do anything we want, as long as we're willing to do it manually." But manual processing is also expensive -- it requires one agent to be dedicated to each column of cells.
 |
 |
- Automated processing: one or more agents may build a rule which attempts to predict what the value of a cell will be at each step. If the prediction is correct, the behavior is captured, and there is a positive payoff; if the prediction is incorrect, there is an exception, and a negative payoff. Automated processing requires an initial investment of effort, but once a rule has been built, the cost of running it is much less than the cost for manual processing. This matches our intuition that automation is efficient when successful, but requires an initial investment, which only pays off over time. This also matches our notion that if the automation fails to match the target behavior a significant portion of the time, the system may never pay off its investment, and will be treated as having "failed".
 |
 |
 |
- Combination processing: a rule may be only partially successful in capturing behavior, but its failure may be predictable. In such cases, it may work to have occasional manual processing to supplement automated processing. This matches our intuition that all automated systems have exceptions, that require some manual processing. As long as the manual processing is not excessive, the combination will be less expensive that no automation at all.
[edit] Simulating Design
So how might we simulate the design processes of abstraction, induction, association, and deduction in this situation?
[edit] Simulating Abstraction
We can treat abstraction as the process of taking a subset of the attributes of problem behavior and giving them a label, a name. A name is a way of dealing with a set of attributes without having to explicitly detail each of them, each time they are invoked. This can either be for purposes of further processing by the agent, or for communication to other agents. The attributes of rule behavior might include:
- agent that observed the behavior, e.g., "Fred"
- location on the grid where the behavior was observed, e.g., "column 12"
- counts of observed cell triplet patterns resulting in an "on" cell, e.g., "3 of 7 on" (translation: "of seven patterns observed, three resulted in a cell being turned on")
- step when the behavior was named, e.g., "step 29"
An abstraction of this behavior might be "Fred column 12 step 29". Note that this name provides only some of the information observed; the remainder of the information can be requested or retrieved as needed, e.g., "tell me the details of 'Fred column 12 step 29'"".
A key function of abstraction is to combine multiple discrete pieces of information into a single "chunk". Because we hypothesize that agents and humans can only work with a relatively small number of pieces of information at once, this "chunking" enables an agent to "consider" a set of information as a single unit, and then combine it with other chunks to reach a broad conclusion in a finite period of time with finite working memory. If instead the agent had to consider each detailed piece of information each time, that would occupy multiple "chunks" of working memory, and limit the agent's ability to simultaneously deal with other information.
[edit] Simulating Induction
"[Inductive reasoning] is used to ascribe properties or relations to types based on tokens (i.e., on one or a small number of observations or experiences); or to formulate laws based on limited observations of recurring phenomenal patterns." (wikipedia) After observing a set of events, humans may discern some pattern, some regularity. From that pattern, we may make some generalization, and use that generalization as a premise for later deductive reasoning.
As we have assumed that an agent "knows" what a rule is, the agent can determine the behavior of a particular column of cells as follows:
- Observe the values of a cell and its two neighbors, and remember them
- Observe the value of the cell that is generated at the next step
- Infer from these observations the general rule that whenever the input values match what was observed in the first step, the cell that is generated will have the value in the second step.
If this process is repeated over time, and if the input values vary, the agent will gradually build up rules for each of the eight possible input combinations, and can then be said to have completely "understood" the behavior of that column of cells. The agent's understanding may be less than complete if all of the input combinations are not observed.
It is also possible to observe patterns at a higher level, by observing the values of multiple columns of cells at each of a number of steps. It was at this level that Wolfram did his analysis of the behavior of the automata to be used in this simulation, and divided the patterns of behavior into four classes:
- uniformity: all cells in an area are of the same color
- repetitive: cells alternate from one color to the other in a fixed sequence
- nested: cells create a fixed set of patterns, but at different scales
- complex: cells create random patterns, or patterns that do not ever repeat or repeat only at relatively long intervals
It should be straightforward to create agents that can "perceive" patterns of the first two types. I have no idea how hard it would be to program to "perceive" nested patterns or complex patterns.
Once such a pattern has been "perceived", a number of directions are possible to understand what generated it. A brute-force approach would be to run samples of each of the 256 possible rules, and compare the outputs to what has been observed. When a match is found, it could then be inferred that the observed pattern was generated by the matching rule. This approach has limitations: for a given pattern, there may be several rules that produce similar output for the particular inputs that were observed. Also, if the pattern was generated by one of the complex rules, it can be very challenging to find a matching pattern in any reasonable period of time.
Another approach would be to ignore the original problem that generated a pattern, and just come up with an ad hoc rule. A simple way to do this would be to count the number of occurrences of a particular color in a column; if the count favors one color (e.g., red) over the other, the rule that might be inferred could be just "the cells in this column are red", which would be correct most of the time.
Finally, patterns could be observed at a higher level -- in the behavior of the agents, not the cells. After working with multiple columns of cells for some time, each agent will accumulate a history of successes and failures at "understanding" the columns of cells. That could lead to observations like "Mary mostly succeeds in understanding cells in X location of the grid" or "Joe fails almost all the time, no matter where we put him." From this, rules could be inferred: "Mary will succeed more often than Joe".
There are many possible ways to build a pattern. Some examples:
- B follows A, from which we infer that A caused B
- Many cases of X are observed, from which we infer that X always occurs
- M & N are close to one another, from which we infer that they are driven by the same mechanism
These pattern-building mechanisms may not be logically defensible or may be examples of cognitive bias, but that is not our concern. We should just be concerned that they are frequently used by people, and are therefore plausible ways for our agents to use to come to an understanding of the behavior of phenomena.
[edit] Simulating Association
"That reminds me of..." may be the most common processing that people do of the patterns they see in the world. Associations can be made between any attribute of current experience with similar attributes of remembered experience. Association is also a common subject of personal contact -- conversations consist in significant part of associations one person makes and communicates in response to a communication from another person.
Agents will be maintain memories of previous automata and previous agent interactions, and will be able to associate current observations with those memories. As well, communication will occur between agents; this communication will consist in part of associating one agent's current observations with the memories of another. These associations might take the form of something like "that sequence of cells looks like something I remember from another problem", or "....looks like something Mary told me about from a problem she worked on."
Associations can take place between any combination of attributes of one problem and the current problem, including behavior of automata and of agents. The likelihood of a particular association will be some function of random choice and the agent's "feelings" about the memory. "Feelings" are positive or negative qualities attached to the memory by the success or failure of the problem effort for which the memory was saved.
[edit] Simulating Deduction
Deduction is the derivation of conclusions from premises through the application of logic mechanisms. The premises can be any propositions that may have come from the processes of abstraction, induction and association applied to the current problem. The derived propositions will make predictions about the results of possible actions taken to address the current problem. The actions that are evaluated as resulting in the best outcomes will then drive the behavior of the agent in future steps.
Deduction will be simulated as a programming problem. The propositions will be a series of tokens and logical operations. Logical functions will be applied to the tokens, and the resulting propositions given a probability of success. The domain of tokens to be evaluated will probably include:
- cell values
- cell locations
- cell relations (neighbors, at various distances)
- cell sequences (which cells followed which in a given column)
- counts of cell values
- time (step of the simulation)
- problem abstractions
- rules
- patterns
- agent names
- actions associated with cells (manual processing, automatic processing)
- events (successful & exception processing)
- histories of previous problem efforts
- agent populations
- payoff levels
[edit] Agent Roles
To this point, we have outlined a way we might simulate the process of designing an approach to solving a problem through some combination of manual and automated processing for a particular domain. To get to a plausible simulation of the process of building a non-trivial system, I propose perhaps four roles:
- manual processor: agents who intervene manually to keep cells under control
- rule builders: agents who build & maintain rules for one or more columns, and who may analyze the behavior of single columns
- analysts: agents who observe the behavior of multiple columns, and who recommend approaches to capture that behavior
- managers: agents who manage a population of other agents to build and run systems under a budget
[edit] Problem Simulations
The simulations themselves will have the structure of defining one or more problems to generate behavior across a portion of the grid. Left unchecked, this behavior will expand one step at a time, and eventually come to fill the entire grid. The simulation will also include one or more agents, whose goal is to "capture" the behavior of the problems, within the constraints of an energy budget. Success consists of keeping the automata from overrunning the grid, while maintaining a positive amount of energy. Relative success consists of succeeding more efficiently than some other effort. Success is defined at the level of the group of agents. Energy is re-distributed among the agents to keep them all "alive" until or unless the entire group exhausts its energy budget. (This corresponds to the corporate way in which systems are built -- the project is treated as a unit. The project budget is either sufficient to complete the entire system, or it is not. In the former case the project team is rewarded; in the latter case the project team is disbanded.)
Once some of the simpler scenarios have been understood, agents will accumulate "memories" of their previous experiences, and then will be assigned to more complex scenarios. This will enable an analysis of how a culture develops and sustains itself around particular approaches to building systems.
[edit] Simulation parameters
The parameter space for this simulation is very large. This is driven by the attempt to simulate the design process as not just one of behavior, but of internal processing by each agent, and of the interaction of agents with different histories. Examples of parameters will include:
External parameters
- size of the grid
- number of separate problems generating cell patterns
- number of agents
Internal parameters
- number of "chunks" of information an agent can process
- number of "thinking cycles" available to an agent at each step
Historical & cultural parameters
- number & ratio of agents with "successful" & "failed" histories
- number & ratio of agents with histories on small, medium & large projects
- language tokens (built-in & acquired) available to agents to process information
[edit] Analysis approach
The simulations will be run with various combinations of parameters, looking to answer these questions:
- Does the size of the project team have an impact on its likelihood of success?
- How does the likelihood of success of the project vary with the complexity of the behavior the team is attempting to capture?
- How do the networks that emerge among the agents affect the success of the team in building the target system?
The project will also evaluate the usefulness & plausibility of this simulation for addressing the questions above. The immediate objection is that it is very complex. Complex as it is, is the simulation still too simple to provide insights? How could it be simplified further?
(Comments welcome! -- please register and update freely) Steve 18:24, 27 November 2007 (PST)
