Sociology 242G Lecture Outlines

Agent-based modeling: Agent learning and adaptation (week 5)

This page contains materials supporting sociology 242G. During the terms when this course is being taught, it will also have a home page on the U.C.R. campus web-server, which gives access to email and web-board utilities. This course is developed by Robert Hanneman of the Department of Sociology at the University of California, Riverside. Feel free to use and redistribute any materials posted here (with citation, please). Your comments and suggestions are much appreciated.
Week 5: Agent-based modeling: Learning and adaptation

readings:
Bainbridge, William Sims. 1995. "Neural Network Models of Religious Belief."
Ladd, Scott Robert. 1996. Genetic Algorithms in C++
Holland, John H. 1992. "Genetic Algorithms" Scientific American, July.
Rao and Rao. 1995. Neural Networks and Fuzzy Logic. Chapter 1.

activities:
Bainbridge's "Mars," and "Evolve" simulations. Prisoner's Dilemma and Traveling Salesman genetic algorithm simulations.

lecture outline:
Introduction: The challenge of smart or adaptive agents

adaptation through evolution
cognitive learning machines: artificial intelligence, memory structures, neural networks
social learning machines: learning and remembering, conforming, innovating

Adapting through evolving

basic dynamics: mutation, cross-over, selection
embedding the dynamics in agents: sexual reproduction models
embedding the dynamics in agents: cultural reproduction models
genetic algorithm models (see also below)

Adapting through cognitive learning

trial-and-error, reward and punishment: strategy evolution in iterated games
perceiving the environment - local knowledge, "mass-media"
organizing and using knowledge: information averaging, discounting, Baysian inference
learning: memory registers, schema, knowlege networks, neural networks (see also below)

Adapting through social learning

interaction and diffusion, mobility, network structuring of influence and learning - local knowledge
deciding whether to interact - biased knowledge
learning by rumors, learning trusted rumors

Some reading notes:
Adaptation by selection: genetic algorithims
Adaptation by cognition/learning: neural networks
Adaptation by social learning

Adaptation by selection: genetic algorithims

One set of mechanism by which populations may change and adapt are the mutation-selection dynamics of evolutionary theory. This kind of adaption has been modeled by treating the list of traits that descibe actors as "DNA" that encode the genotype of the actor, and applying biological models. This kind of thinking has been applied to ascriptive traits of actors, as in sexual reproduction. It can also be applied to the dynamics of culture and information being transmitted from one agent to another. Much recent work in computer science (e.g. Ladd) has focused on how this way of thinking about "actors" and their modification can be used to solve problems of optimization, sorting, and other solution-seeking programming problems.

Holland's article from Scientific American (supplied by Kate Auerhahn) contains a lot of quite stimulating reports and suggestions. Pages 66-70 deal more generally with genetic algorithms, the pages after deal more with applications -- specifically of classifiers.

The general story is that some object (as in a social agent in a agent-based simulation) may be represented as a list of attributes, analogous to genes. In "mating" algorithms, two such strings are selected. They are given a probability of producing offspring proportional to the "fitness" of the two strings. If they do mate, they produce two offspring strings. The offspring strings are generated by selecting a (usually random) cross-over point in the string, and swapping code between the two strings at that point. In most algorithms, an additional probability of mutation is added, in which individual genes may be changed at random. The primary mechanism is "mating" is cross-over; mutation and random re-ordering of genes are the only mechanisms of change in non-mating algorithms. Some mating algorithims also allow for re-arrangement of whole code chunks. After "mating" the new strings are evaluated for fitness, and the process proceeds iteratively.

Holland shows a number of really neat and important results that demonstrate that these kinds of methods are extrememly computationally efficient for searching for solutions to very complex problems -- and points out a number of very important practical applications. We will look at one of these in the "genetic algorithms" simulation.

Our immediate concern, however, is whether genetic algorithms are a reasonable analog of some processes of social change. They have a good bit of intuitive appeal. Some arguements in favor of adapting them to agent models are:
1) the "genetic code" list approach is analogous to the "trait list" approach for representing agents
2) the notions of random mutation, chuck switching, and cross-over may all be reasonable analogs of processes that occur when individual humans generate offspring and train them as social beings; and, when macro-agents interact and recombine.

Somewhat troublesome to me is the operation of natural selection in these algorithms. On the good side, codes of more than a few genes can generate very complex patterns of fitness landscapes -- analogous to there being multiple kinds of differentiated social structures adapted to local conditions; this view seems more sophisticated than earlier functionalist notions of social evolution. On the negative side, the models themselves are unsophisticated about how fitness selection actually occurs. In this sense, embedding them in spatial or social network environments is more promising -- this, in effect is what the Macy and the Bainbridge models do.

As a practical tool, genetic algorithms are really search and sort algorithims designed to solve complex problems by iterative -- but non-linear search. There is evidence that this is analogous to biological genetics in many ways -- and may account for "punctuated equilibrium" in revisionist evolution theory. Human adaptation of structures to environments may display the same kinds of non-linear and discontinuous response; are genetic algorithms a plausible analog to some social change processes?

If you think they might be, how do you decribe the "genetic structure" of a social object?

return to the index of this page
Adaptation by cognition/learning: neural networks

Learning and adaptation also occur (or at least it's a plausible hypothesis) in individuals, as well as in populations. There are many different theories of learning, and much of the field of artificial intelligence has been devoted to building machines that learn through perception, cognition, and experimentation with their environments. Of the many approaches and models, one of the most interesting current trends is to use "neural networks" to model learning processes. Neural networks are so named because they borrow some of their architecture from biological neruon networks, and are designed -- more or less loosely -- to try to learn "the same ways" that humans do.

Again, very loosely, neural network models consist of agents with simple properties, and network relations with other actors. In a sense, neural networks could be though of as actor networks embedded within individual actors -- who are themselves embedded in networks of other actors. Neural networks have a great deal in common, structually, with ideas that are widely used in social network analysis. Some of the analysts (e.g. Bainbridge) who become interested in applying neural networks in sociology have come out of this social networks tradition.

Neural networks can take many forms. Many consist of three layers: input, transformation, and output. Generally, external stimuli act on the input layer; when nodes in the input layer are "stimulated" they send signals of various strengths to some nodes in the processing layers. Neurons in the processing layers aggregate the signals they receive from the input layer (weighted sums), and pass on these signals (often "clipped" and transformed into binary outputs) to connected nodes in the output layer -- which present the results of the algorithm.

Neural networks are usually used as "learning" or "adaptive" programs. They may be "trained" by the programmer (either by interaction, or by writing a control program to interact with the network, and give it feedback). We might begin with a system in which all the weights connecting input to process to output layers have randomly assigned weights. An input stimulus is presented, and the output is observed. If the output is not acceptable, the parameters (weights) of the system are modified. Once the system has been trained to solve "reference" problems correctly, it can then be applied to novel problems.

This kind of approach is of considerable interest in engineering and computer science. But of what utility is it in building models of social dynamics? There are serveral answers. However, almost all the answers are very speculative, as there have been few serious attempts (contra, see article by Bainbridge) to use these algorithms in sociology.

One answer is: neural networks can be embedded in agent-based models to represent the ways that agents perceive their environments, formulate responses, and respond. Whether this kind of approach can represent persons well is an open question; they might be useful to explore how social structures (families, communities, organizations, etc.) process and respond to environmental stimuli.

Second: neural networks may be particularly useful as a model of how humans and their constructed agents identify and create simpler qualitative patterns from complex, and often continuous inputs. Humans have limited short-term cognitive capacity; but they achieve very fast and efficient processing by clumping data and manipulating flags and patterns -- neural networks may provide better models of how humans deal with very complex environments than do, say, rational choice optimization types of algorithms.

Third: the neural network may be an analogy for certain forms of human social organization in itself. Consider Bainbridge's "Invent" simulation. While not a formal neural network, the model has some structural similarities to neural networks. Might certain aspects of how human social structures process symbolic input and produce symbolic output be captured with neural nets?

return to the index of this page
Adaptation by social learning

This is really a brief reprise. Many of the agent models have more or less explicit theories of how actors change in response to stimuli arising from their interactions with other actors. Simple copying, information averaging, migration toward or away from individuals or groups on the basis of similarity, mimicing high status actors, etc. are all examples of how more "sociological" analysists have approached the question of how actors and systems "adapt" or change over time.

It should now be apparent that the "intelligence" of "artificial societies" is multi-layered and multifaceted, and may well involve many dynamics occurring simultaneously at different levels. There is a great deal of work still to be done on understanding how human systems are "intelligent."




return to the course home page