I486/I586/H400 Artificial Life as an approach to Artificial Intelligence

Spring Semester 2011

 

Meeting Times:  2:30pm – 3:45pm MW

Location: Informatics West, room 107

 

Professor:  Larry Yaeger

Office: Informatics East, room 305

Office Hours:  By appointment, any afternoon or early evening I'm not in a class or meeting

Phone:  (812) 856-1845

Email:  larryy (at) indiana (dot) edu

 

Textbook (required): Braitenberg, V. Vehicles: Experiments in Synthetic Psychology

All other reading materials available online via links on this page.

 

For distinction between I486, I586, and H400 expectations, see Requirements section below.

 

Introduction

 

What is life?  What is intelligence?  How are the two linked, how can we quantify them, and how can we leverage our knowledge of natural intelligence to create artificial intelligence?  Since every example we have of natural intelligence is the product of the evolution of nervous systems subject to natural selection under ecological pressures, this course explores the idea that our best hope of creating artificial intelligence is through the evolution of artificial nervous systems subject to natural selection in an artificial ecology—i.e., Artificial Life.  We will study seminal papers and fundamental technologies that enable such an endeavor, including neural networks, genetic algorithms, emergent phenomena, information theory, and measures of complexity.

 

Expectations

 

Some of the course is conceptual in nature, some requires the ability to think algorithmically (as in computer programming), and some requires a degree of comfort with math that includes probabilities, summations, and logarithms, at least.  A basic introduction to probability theory and information theory are a key part of the class, and some of the readings are based on information theory and even some differential equations (though a knowledge of differential equations is not required to learn the necessary material).  A substantial amount of reading is required for the course, with undergrads expected to read at least a couple of journal articles each week, graduate students twice that.  There is also a term project, that can be a software project, a report on an experiment using existing software, or a review paper on a topic relevant to the class.

 

Schedule and Reading List

 

Links under the ÒTopicsÓ heading are to PowerPoint lecture notes.  You can download these in advance if you want something to take notes on, but be warned, they are subject to change.

 

In the topics, S# means Speaker #.  (Speaker topics can be inferred from the schedule, but are listed explicitly at the bottom of this page.)

In the reading assignments, B# means chapter # of the Braitenberg book.

L# is Lecture #.

 

Class

Date

Topics

Reading Assignment (after the corresponding weekÕs class)

Additional Graduate & Honors Reading Assignments

Extras (not required)

 1a

MO 10 Jan

Class intro, L1-Intro to Artificial Life

Langton1

Dyson

 

 1b

WE 12 Jan

Intro to Braitenberg, L2-Is it alive?

Farmer & Belin, B1

 

 

  

MO 17 Jan

No class - MLK Holiday

 

 

 

 2b

WE 19 Jan

L3-Intro to GAs

Goldberg, B2

Holland, Fraser

Charbonneau

 3a

MO 24 Jan

S1, S1, S2, B1, B2 discussion

 

 

 

 3b

WE 26 Jan

L4-Simulated Evolution (Sims movie)

Ray, Sims, B3

Sims1, Sims2

 

 4a

MO 31 Jan

S3, B3, discussion, test prep

Exam 1, take-home  

 

 

 4b

WE  2 Feb

Exam 1 due, L5-Neural Networks Pt. 1 - Terms & Defs

Anderson, B4

Rumelhart & McClelland

 

 5a

MO  7 Feb

S4, B4, software demos, discussion

 

 

 

 5b

WE  9 Feb

L6-Neural Nets Pt. 2 - Association & Hebb

James, Hebb, B5

Plasticity

 

 6a

MO 14 Feb

S5, B5, ALife project ideas, discussion

 

 

 

 6b

WE 16 Feb

L7-Intro to Information Theory

Shannon (Intro & Part I), n-grams, B6

Schneider, Jaynes

 

 7a

MO 21 Feb

John Beggs guest lecture?

 

 

 

 7b

WE 23 Feb

L8-Neural Nets Pt 3 – Hebbian learning via Information Theory

Linsker1, Linsker2, B7

 

Swindale

 8a

MO 28 Feb

S6,  S7, B6, B7, test prep

 

 

 

 8b

WE  2 Mar

In-class Midterm (Exam 2)

B8

 

 

 9a

MO  7 Mar

Return and discuss exams, S8, B8, discussion

 

 

 

 9b

WE  9 Mar

L9-Neural Nets Pt 4 – Spiking Neuron Models

Izhikevich1, Izhikevich2, Izhikevich3

Herz, O'Reilly, BlueBrain

Destexhe

  

MO 14 Mar

No Class - Spring Break

 

 

 

  

WE 16 Mar

No Class - Spring Break

 

 

 

10a

MO 21 Mar

Informal presentation of project ideas

 

 

 

10b

WE 23 Mar

L10-Evolution & Learning

Hinton&Nowlan, Parisi, Chalmers, B9

Belew

 

11a

MO 28 Mar

S9, S10, S10, B9, B10, discussion

 

 

 

11b

WE 30 Mar

L11-Organisms simulated and real (Koko, Dolphins, Betty, Alex)

Walter, NewSci, Salience, Giurfa, B10

Swinderen, Foote, Clayton

NatGeo

12a

MO  4 Apr

S11, S12, B11, B12, discussion, test prep

 

 

 

12b

WE  6 Apr

L12-Intelligence as an Emergent Phenomenon

Hillis, B11, B12

Dennett

 

13a

MO 11 Apr

Olaf Sporns guest lecture

Exam 3, take-home

Tononi1, Buzs‡ki

 

13b

WE 13 Apr

Exam 3 due, L13-Evolution of Intelligence (movies)

Yaeger, B13, B14

Gould, McShea, Carroll

 

14a

MO 18 Apr

Return exams, S13, S13 B13, B14, discussion

 

 

 

14b

WE 20 Apr

L14-Is it alive? Pt. 2, Measuring Complexity

Langton2

Seth, Tononi2

Crutchfield, Feldman

15a

MO 25 Apr

Project Demos

 

 

 

15b

WE 27 Apr

Project Demos (Projects due Friday Apr 29)

 

 

 

  

WE  4 May

Final Exam 12:30pm - 2:30pm (Exam 4) Info West 109

 

 

 


Requirements

 

Students will be expected to attend class, do weekly readings, and participate in discussions.  Each student will present and lead a discussion on the material in one topic area (see list at bottom of page).

 

In addition there is a semester project, for which each student must do one of the following.  Note that there are different requirements for graduate and undergraduate students, and grades will be assessed accordingly.

 

á      Write a final paper demonstrating insight into one of the topic areas (undergrads 15-20 pages; grads 20-25 pages and should be of publishable caliber as a review paper).

á      Develop a functioning ALife simulator of at least modest complexity (student should consult with teacher before writing; for graduate students this must be more than a simple CA or Conway Game of Life and the work should be of publishable caliber) and provide a succinct write up describing the software and sample results.

á      Turn in a technical paper describing the results of an ALife experiment, carried out with Breve, NetLogo, Tierra, Avida, Swarm, Second Life, Polyworld, or other ALife software (student should consult with teacher in selection of software and topic; for graduate students the experimental design and write up should be of publishable caliber).

 

Students will present / demo their projects the last week of class.

 

There will be four exams—two take-home exams, an in-class midterm, and an in-class final exam.  The lowest test grade will be dropped, thus the final is optional, if a student is satisfied with the first three test results.  The midterm may include cumulative questions, but will primarily focus on the material since the previous test.  The final exam is cumulative.  Dates are indicated in the schedule above.

 

Graduate students have additional reading assignments, and will be responsible for the material covered in those readings.

 

Course Structure

 

Generally, each weekÕs theme will bridge weekends, being introduced by me in the WE lecture class, and then followed up with readings before the next class on MO, in order to allow students maximum time to read and prepare for discussion.  On the following MO, student presentations of a topic related to the reading materials will take place, followed by a discussion of one of the chapters from the Braitenberg book, followed by any additional material I need to communicate, and class discussion of that weekÕs topic.  (There will be exceptions to this pattern, as indicated in the above schedule, at the start of the semester, around Spring Break or Thanksgiving, or when there are guest speakers.)

 

Each student will prepare one presentation during the semester on a topic related to the reading materials.  We will agree on and set dates in the first class.  If there are more than 13 students in the class, we will fit extra presentations in as needed.  These presentations are to be 15 to 20 minutes only.  In general, I hope students will select one of the papers referenced by the primary reading material and use that as the basis for their presentation.  But if there is a topic of particular interest to a student in the reading material itself and I have not covered that topic in the lecture class, that will be acceptable.  Related papers not taken from the reference list may also be acceptable, but require my approval.

 

Each student will also work on one final project, with higher expectations for graduate students.  As indicated above, this project may take the form of writing your own ALife simulator, performing experiments with an existing ALife simulator, or researching and writing on a topic in the field, in order to accommodate all computer skill levels.  Students are expected to give brief presentations describing their semester project during the last week of class, and projects are officially due at the end of the last week of class.

 

Grading

 

Each of the four tests, class participation, the topic presentation, and the final project will contribute to the total grade as follows:

 

Participation

5 pts

(Yes, it really does count)

Gedanken experiment

5 pts

 

Presentation

10 pts

 

Project

20 pts

 

 

 

 

Test 1 (take-home)

20 pts

 

Test 2 - Midterm

20 pts

 

Test 3 (take-home)

20 pts

 

Test 4 - Final

20 pts

 

 

 

 

Total

120 pts

(100 pts after dropping the lowest test score)

 

The extended gedanken experiment will be defined in the first week.  This experiment will pose a challenge that, if answered correctly by anyone in the class, anytime before the end of the semester, will result in the credit being received by the entire class.

 

Grades will not be curved and will be assigned as follows (this is the same as used in I101 and I210, but differs from some other classes):

 

A+

98-100

4.0

A

93-97

4.0

A-

90-92

3.7

B+

85-89

3.3

B

80-84

3.0

B-

75-79

2.7

C+

70-74

2.3

C

65-69

2.0

C-

60-64

1.7

D+

55-59

1.3

D

50-54

1.0

D-

45-49

0.7

F

  0-44

0.0

 

Conduct

 

Cooperation on the extra credit problem is encouraged, as is discussion in general.  In fact, I intend to set up an email list to facilitate discussions outside of class.  However, tests must be taken individually, both take-home and in-class.  Cheating will be reported to the Dean of Students, according to university policies.

 

General Course Description

 

Artificial Life is a broad discipline encompassing the origins, modeling, and synthesis of natural and artificial living entities and systems.  Artificial Intelligence, as a discipline, tries to model and understand intelligent systems and behavior, typically at the human level.  This class will introduce core concepts and technologies employed in Artificial Life systems that can be used to approach the evolution of Artificial Intelligence in computers.  Key themes include:

 

- bottom-up design and synthesis principles,

- definitions and measurements of life and intelligence,

- genetic algorithms,

- neural networks,

- the evolution of learning,

- the emergence of intelligence,

- computational ecologies, and

- information theory-based measures of complexity.

 

Our path through these materials will lay the theoretical groundwork for an approach to Artificial Intelligence based on the tenets and practices of Artificial Life—an approach which utilizes evolution to start small and work our way up a spectrum of intelligence, from the simplest organisms to the most complex, rather than attempting to model human-level intelligence from the outset.

 

Lectures and readings will be based on seminal papers and introductory texts in these fields, drawing from the Artificial Life conference proceedings, and technical papers by Donald Hebb (from which we obtain Hebbian learning), Rumelhart and McClelland (editors of and authors in the original Parallel Distributed Processing books that launched the modern neural network field), Ralph Linsker ("Infomax" theoretical approach to neural network learning), Hinton and Nowland (the "Baldwin effect"), William James ("the greatest American psychologist"), W. Grey Walter, Tom Ray, Karl Sims, Danny Hillis, and others.  We will also read and discuss Braitenberg's seductive and influential Vehicles book.

 

References (Partial)

 

Anderson, J. A., General Introduction, p. xiii-xxi, Neurcomputing, Foundations of Research, ed. by J. A. Anderson and E. Rosenfeld, A Bradford Book, MIT Press, Cambridge, Massachusetts, 1988

           

Chalmers, D., "The Evolution of Learning: An Experiment in Genetic Connectionism" in Connectionist Models, Proceedings of the 1990 Summer School, edited by D. S. Touretzky, J. L. Elman, T. J. Sejnowski, G. E. Hinton, Morgan Kaufmann, San Mateo, CA, 1991

           

Douglas, F., ÒDo fruit flies dream of electric bananas?Ó, New Scientist, 14 February 2004

           

Farmer, J. D., and A. dÕA. Belin, "Artificial Life: The Coming Evolution"  In Artificial Life II, edited by C. Langton, C. Taylor, J. Farmer, and S. Rasmussen.  Proceedings of the Artificial Life II Conference (in 1990), Santa Fe Institute Studies in the Sciences of Complexity Proc. Vol. X.  Addison-Wesley, Redwood City, CA, 1992

           

Frye, M.A. & Dickinson, M.H. ÒA signature of salience in the Drosophila brainÓ, commentary on article by Swinderen & Greenspan, Nat. Neur. 6 (6) 544-546 June 2003

           

Giurfa, M., Zhang, S., Jenett, A., Menzel, R., Mandyam, V., ÒThe concepts of 'sameness' and 'difference' in an insectÓ, Nature 410(6831) 930-933, 19 Apr 2001

           

Goldberg, D. E., A Gentle Introduction to Genetic Algorithms, p. 1-23, Chapter 1 of Genetic Algorithms in Search, Optimization, and Machine Learning, by D. E. Goldberg, Addison-Wesley 1989

           

Hebb, D. O., Introduction (p. xi-xix) and Chapter 4, "The first stage of perception: growth of the assembly" (p. 60-78), The Organization of Behavior, Wiley, New York, 1949 (with introduction, p. 43-56 from Neurocomputing, Foundations of Research, ed. by J. A. Anderson and E. Rosenfeld, A Bradford Book, MIT Press, Cambridge, Massachusetts, 1988)

           

Hillis, D. W., Intelligence as an Emergent Behavior, p. 175-189, Daedalus, Journal of the American Academy of Arts and Sciences, special issue on Artificial Intelligence, Winter 1988

           

Hinton, G. E. and Nowlan, S. J., How learning can guide evolution. Complex Systems, 1:495--502, 1987

           

Izhikevich, Eugene M., Simple Model of Spiking Neurons, IEEE Transactions on Neural Networks (2003) 14:1569-1572

http://www.nsi.edu/users/izhikevich/publications/spikes.htm

           

Izhikevich, Eugene M., Which Model to Use for Cortical Spiking Neurons? IEEE Transactions on Neural Networks (2004) 15:1063-1070

http://www.nsi.edu/users/izhikevich/publications/whichmod.htm

           

Izhikevich, Eugene M., Polychronization: Computation With Spikes, Neural Computation (2006) 18:245-28

http://www.nsi.edu/users/izhikevich/publications/spnet.htm                                         

           

James, W., Association, Chapter XVI of Psychology (Briefer Course), p. 253-279, Holt, New York, 1890 (with introduction, p. 1-14 from Neurocomputing, Foundations of Research, ed. by J. A. Anderson and E. Rosenfeld, A Bradford Book, MIT Press, Cambridge, Massachusetts, 1988)

           

Langton, C. G., Artificial Life, preface to Artificial Life, The Proceedings of an Interdisciplinary Workshop on the Synthesis and Simulation of Living Systems held September, 1987 in Los Alamos, New Mexico, Santa Fe Institute Studies in the Sciences of Complexity Proc. Vol. VI., edited by C. Langton, Addison Wesley, Redwood City, CA, 1989

           

Langton, C. G., Computation at the Edge of Chaos: Phase Transitions and Emergent Computation, p. 12-37, Emergent Computation, Proceedings of the Ninth Annual International Conference of the Center for Nonlinear Studies on Self-organizing, Collective, and Cooperative Phenomena in Natural and Artificial Computing Networks, Los Alamos, NM, 1989, ed. Stephanie Forrest, North Holland, 1990

           

Linsker, R., "Towards an Organizing Principle for a Layered Perceptual Network" in Neural Information Processing Systems, ed. by D. Z. Anderson. American Institute of Physics, New York, 1988

           

Linsker, R., "Self-Organization in a Perceptual Network", Computer 21(3), 105-117, March 1988

           

Parisi, D., S. Nolfi, and F. Cecconi, "Learning, Behavior, and Evolution", Tech. Rep. PCIA-91-14, Dept. of Cognitive Processes and Artificial Intelligence, Institute of Psychology, C.N.R., Rome, June 1991. (Appeared in Proceedings of ECAL-91—First European Conference on Artificial Life, December 1991, Paris; also in Varela, F, Bourgine, P. Toward a pratice of autonomous systems. MIT Press. 1991

           

Ray, T. S. 1992. Evolution, ecology and optimization of digital organisms. Santa Fe Institute working paper 92-08-042

           

Rumelhart, D. E. and McClelland, J. L., PDP Models and General Issues of Cognitive Science, p. 110-146, Chapter 4 of Parallel Distributed Processing, Explorations in the Microstructure of Cognition, Volume 1: Foundations, ed. by D. E. Rumelhart, J. L. McClelland, and the PDP Research Group, A Bradford Book, MIT Press, Cambridge, Massachusetts, 1986

           

Schneider, T., ÒInformation Theory PrimerÓ, <http://www.lecb.ncifcrf.gov/~toms/paper/primer/>

           

Sims, K., Evolving Virtual Creatures, Computer Graphics, Annual Conference Series, (SIGGRAPH Ô94 Proceedings), July 1994, pp.15-22.

           

Walter, W. G. (1950), "An Imitation of Life", Scientific American, 182(5), 42-45, May 1950

           

Yaeger, L. S., Computational Genetics, Physiology, Metabolism, Neural Systems, Learning, Vision, and Behavior or PolyWorld: Life in a New Context, p. 263-298, Proceedings of the Artificial Life III Conference (in 1992), ed. Chris Langton, Addison-Wesley, 1994

 

Speaker Topics

 

S1 – Intro to Artificial Life or Is It Alive?

Origin of life; artificial intelligence; Charles Darwin; Alan Turing; John von Neumann; other attempts to formally define life; applications of artificial life; multi-agent modeling; evolutionary trends (in complexity, size, cell types, etc.); ALife software on the web (Breve, Sugarscape, Swarm, NetLogo, Avida, Framsticks, etc.)

S2 – Genetic Algorithms

Function optimization issues (Charbonneau "extras" reading); real world applications (there are many); specific application in depth; Genetic Programming methods and applications; John Holland; cross-over versus mutation (Holland, others);  differences between computational GAs and biological genetical evolution; evolutionary art / aesthetic selection; evolutionary robotics; GA software on the web

S3 – Simulated Evolution

Avida; recent reimplementations of Sims's blocky creatures; Sims's competing block creatures work; applications of simulated evolution (economy, language, number use, art, music etc.); evolutionary games (Spore, SimLife, Creatures, etc.); simulated Lamarckian evolution; evolutionary software on the web (Breve, Sugarscape, NetLogo, Avida, Framsticks, etc.)

S4 – Neural Networks, Intro

Neural network applications (there are many); distributed vs. symbolic AI and knowledge representation; evolving neural networks; enhancements to BackProp for training ANNs; levels of detail used to model neurons and neural nets; differences between artificial and biological neurons and neural nets; neural network software on the web (for biological modeling and/or engineering/classification work)

S5 – Neural Networks, Association & Hebb

Applications of Hebbian learning (vision, PCA/ICA, signal separation, robotics, etc.); anti-Hebbian learning; Hebbian-learning neural network software on the web (biological or artificial)

S6 – Information Theory

Information metrics as expected values; the Schneider paper; discussion of results from the "n-grams" extra exercises; applications of information theory (neural spike timings, feature selection for inputs to ANNs, medical imaging, genetic analysis—site conservation, encoding information about the environment, classifying protein sequences, etc.); Kullback-Liebler Divergence; information theory software on the web

S7 – Neural Networks, Information theoretic approach to neural network learning

Application of information theory to ANNs (neural spike timings, feature selection for inputs to ANNs, etc.);  Bayesian techniques and applications; analyzing neural networks with information theory (capacity, statistical mechanics, etc.); application of statistical mechanics to network analysis (percolation on graphs, ala John Beggs)

S8 – Any of the above!

Any of the above topics, and then some

S9 – Combining evolution and learning

Belew's analysis and extension of the Hinton & Nowlan work (see "extras"); other Parisi papers; David Ackley's experiments with Lamarckian evolution; other computational experiments combining learning and evolution (Miller & Todd, French & Messinger, others)

S10 – Animal intelligence, intelligence in simulated organisms

Any Clayton work with scrub jays (see "extras"); any animal cognition studies; more depth on Koko, Alex, Kanzi, others; other bee experiments (bilateral symmetry, human facial recognition, etc.)

S11 – Intelligence as an emergent phenomenon

Dennett's "Kinds of Minds" (see "extras"); Hillis's coevolution of sorting algorithms; other approaches to modeling intelligence (Cyc, Hofstadter's Copy-Cat, Seq-See, etc.); emergence; order out of chaos (Prigogene, others)

S12 – Evolution of intelligence

Other evolutionary software (Sugarscape, NetLogo, Avida, Framsticks, etc.); evolution of complexity (see "extras")

S13 – Complexity

Complexity metric from Tononi, Sporns, & Edelman (see "extras" next to Olaf Sporns's guest lecture); overview of different complexity measures (see Seth, Crutchfield, and Feldman "extras"); Tononi's "Phi" measure of complexity and consciousness (see Tononi2 in "extras"); Kolmogorov descriptive/algorithmic complexity

 

Links to previous student presentations may be found on the following class home pages from previous semesters.  Click on the student's name in parentheses to download the presentation.  If the "S#" indicator is also a link, then it will point to supporting materials for the presentation.  (Other links on these pages do not work.)

 

Spring 2005

Fall 2005

Spring 2007

Spring 2008

Spring 2010

 

Look here for examples of previous semester projects.