[Date Prev][Date Next][Date Index]
CSLI Calendar, Wednesday, 9 October 2002, vol. 18:5
CSLI CALENDAR OF PUBLIC EVENTS
______________________________________________________________________
9 October 2002 Stanford Vol. 18, No. 5
______________________________________________________________________
A weekly publication of the
Center for the Study of Language and Information (CSLI)
Stanford University, Ventura Hall, Stanford, CA 94305-4115
http://www-csli.stanford.edu/
____________
ACTIVITIES FROM 9 OCTOBER 2002 TO 18 OCTOBER 2002
WEDNESDAY, 9 OCTOBER 2002
11:00am Stanford IT Open House
11:00am - 1:30pm
Meyer Library Lobby
Technology information for faculty, staff, & students
http://itopenhouse.stanford.edu/
12 noon Psychology Developmental Brownbags
Jordan Hall 420:100
Preschool Children's Conception of Individuals and Expressions
Referring to Individuals
Christina Sorrentino
Psychology, Stanford University
http://www-psych.stanford.edu/news.html#dev_brownbag
3:45pm Psychology Department Colloquium
Jordan Hall 420:041
Cognitive modeling of decision making in the Bechara-Damasio
gambling task with ventromedial frontal cortex lesioned individuals
Jerry Busemeyer
Indiana University
http://www-psych.stanford.edu/news.html
4:15pm EE380: Computer Systems Lab Colloquium
Gates B03 (NEC Auditorium)
Molecular electronics:
Defect Tolerance, Chemical Fabrication and Quantum-State
R. Stan Williams
Hewlett-Packard Molecular Electronics
http://ee380.stanford.edu/contents.html
THURSDAY, 10 OCTOBER 2002
12:15pm CSLI CogLunch
Cordura Hall, Room 100
Automating Human Performance Modeling at the Millisecond Level
Alonso Vera
NASA & CMU
http://www-csli.stanford.edu/events/Coglunch/
Abstract below
12:15pm Stanford Networking Seminar
Gates 104
Analysis of a Campus-wide Wireless Network
David Kotz
Dartmouth
http://netseminar.stanford.edu/
Abstract below
2:30pm Special University Oral Examination
Packard 101
Probabilistic Methods for Web Caching and Performance
Prediction of IP Networks and Web Farms
Konstantinos Psounis
http://www.stanford.edu/~kpsounis/
4:00pm PARC Forum
George Pake Auditorium at PARC
Rapid, Automated Bio-Detection and its Application to
Bio-Terrorism Defense
Kurt Petersen
Cepheid
http://www.parc.com/forum/
4:00pm UC Berkeley CIS Seminar
Soda Hall 310 (UC Berkeley)
The State of the Art in Language Modeling: Short Version
Joshua Goodman
Microsoft Research
http://www.cs.berkeley.edu/~eyal/cis-seminar
Abstract below
4:00pm SRI AI Seminar Series
EJ228, SRI International
An Object-Based Interaction for the Operation of Multiple
Field Robots
Hank Jones
Aerospace Robotics Laboratory (ARL), Stanford University
http://www.ai.sri.com/seminars/
Abstract below
4:15pm SSP10: Symbolic Systems Forum
Bldg. 380:380C (Math Corner)
Developmental Stability and Evolution: Possible Link Between
Micro- and Macro-Evolution
Aviv Bergman
Center for Computational Genetics and Biological Modeling
http://symsys.stanford.edu:8081/ssp-dynamic/servlet/ssp_events
Abstract below
4:15pm Fundamental Themes in Neuroscience
Munzer Auditorium, Beckman B060
The inner workings of a cortical motor system
Stephen Lisberger
UCSF
http://www-med.stanford.edu/sbrc/calendar/
4:30pm Personality Seminar
Jordan Hall 420:100
Towards the study of affective decay
Jon Rottenberg
Stanford University
http://www-psych.stanford.edu/news.html#person_lab
FRIDAY, 11 OCTOBER 2002
12 noon Logic Lunch
Bldg. 380:383N (math corner)
Goedel's Developing Platonism
Martin Davis
Visiting Scholar UC Berkeley
Professor Emeritus, NYU
http://www-logic.stanford.edu/seminars.html
Abstract below
12:30pm CS547: Human-Computer Interaction Seminar
Gates B01
Desire in Context
Rich Gold
The Red Shift
http://www-pcd.stanford.edu/cs547/
Abstract below
2:00pm NLP Reading Group
Margaret Jacks Hall, Room 460:301
Heuristic dependency-parsing based on local search
Matthias Kromann
Copenhagen Business School
http://www-nlp.stanford.edu/nlp/nlpgroup.html
Abstract below
2:00pm TGIF
Turing Auditorium
Wireless Technologies @ Stanford
Chudi Igboemeka and Mark Branom
ITSS, Stanford
http://tgif.stanford.edu/
Abstract below
5:00pm Stanford Phonology Workshop
Margaret Jacks Hall 460:126
Variable Vowel Epenthesis in Picard
Julie Auger
Indiana University
http://www-linguistics.stanford.edu/pinterest/
Abstract below
MONDAY, 14 OCTOBER 2002
3:30pm Social Lab
Jordan Hall 420:050
Brainstorming In Organizational Context: Why Past Research on
Brainstorming Effectiveness is Misguided and Nearly Useless
Robert Sutton
Management Science, Engineering, and Organizational Behavior, Stanford
http://www-psych.stanford.edu/news.html#social_lab
4:15pm Broad Area Colloquium in AI,
Geometry, Graphics, Robotics, and Vision
TCSeq 200
The Level Set Method - What's In It For You?
Stan Osher
UCLA
http://robotics.stanford.edu/ba-colloquium/
Abstract below
WEDNESDAY, 16 OCTOBER 2002
4:15pm EE380: Computer Systems Lab Colloquium
Gates B03 (NEC Auditorium)
Quantitative Go, And Some Other Combinatorial Games
Elwyn Berlekamp
UC Berkeley
http://ee380.stanford.edu/contents.html
Abstract below
6:00pm Syntax Workshop
for location email bzack (at) stanford.edu
How many grammars do we need?
Guido Seiler
University of Zurich
http://www-linguistics.stanford.edu/sssg/
Abstract below
THURSDAY, 17 OCTOBER 2002
12:15pm Stanford Networking Seminar
Gates 104
Zero Configuration Networking
Stuart Cheshire
Apple
http://netseminar.stanford.edu/
Abstract below
3:00pm SRI AI Seminar Series
EJ228, SRI International
Visual and Auditory Spatial Sensing
Stan Birchfield
Quindi Corporation
http://www.ai.sri.com/seminars/
Abstract below
3:30pm SSP10: Symbolic Systems Forum
Frances Arrillaga Alumni Center
First Symposium of Undergraduate Research in Progress
http://symsys.stanford.edu:8081/ssp-dynamic/servlet/ssp_events
4:00pm UC Berkeley CIS Seminar
Soda Hall 310 (UC Berkeley)
Title to be announced
David Andre
UC Berkeley
http://www.cs.berkeley.edu/~eyal/cis-seminar
4:15pm CSLI Seminar on Computational Learning and Adaptation
Cordura Hall, room 100
Lloyd Clustering of Gauss Mixtures
Robert M. Gray
Information Systems Lab, EE, Stanford
http://cll.stanford.edu/scla.html
Abstract below
4:15pm Fundamental Themes in Neuroscience Seminar
Munzer Auditorium, Beckman B060
Oscillatory Circuits for Breathing Control
Jeffrey C. Smith
NINDS
http://www-med.stanford.edu/sbrc/calendar/
4:15pm History of Science Colloquium
Bldg. 200:307 (History Corner)
Information is Good (and Bad) for Your Health: Utopias of
Surveillance in Modern American Public Health
Nicholas King
Anthropology, History, and Social Medicine, UC San Francisco
http://www.stanford.edu/dept/HPS/colloquia.html
4:30pm Personality Seminar
Jordan Hall 420:100
The role of self-conscious emotion in self-regulation:
Insights from orbitofrontal damage
Jenni Beer
UC Berkeley
http://www-psych.stanford.edu/news.html#person_lab
5:30pm Stanford Phonology Workshop
Margaret Jacks Hall 460:126
Model theory and the content of OT constraints
Christopher Potts & Geoffrey Pullum
Linguistics, UC Santa Cruz
http://www-linguistics.stanford.edu/pinterest/
Abstract below
FRIDAY, 18 OCTOBER 2002
12:30pm CS547: Human-Computer Interaction Seminar
Gates B01
Post-desktop User Interfaces
Jan Borchers
Stanford Computer Science
http://www-pcd.stanford.edu/cs547/
____________
Stanford Blood Bank status: Critical Shortage of O+, A+; Shortage of
O-, A-, B+, AB+, AB-. For an appointment:
http://bloodcenter.stanford.edu/ or call 650-723-7831. It only takes
an hour of your time.
____________
CSLI COGLUNCH
on Thursday, 10 October 2002, 12:15pm-1:30pm
Cordura Hall, Room 100
http://www-csli.stanford.edu/events/Coglunch/
Automating Human Performance Modeling at the Millisecond Level
Alonso Vera
Senior Research Scientist at NASA Ames Research Center
and Senior Systems Scientist at Carnegie Mellon University
CPM-GOMS is a modeling method that combines the task decomposition of
a GOMS analysis with a model of human resource usage at the level of
cognitive, perceptual, and motor operations. CPM-GOMS models have made
accurate predictions about skilled user behavior in routine tasks, but
developing such models has been tedious and error-prone. We describe
a process for automatically generating CPM-GOMS models from a
hierarchical task decomposition expressed in a computational modeling
tool called Apex, taking advantage of reusable behavior templates and
their efficacy for generating zero-parameter a priori predictions of
complex human behavior. To demonstrate the process, we present models
of automated teller machine interaction and use of a CAD tool. The
models show that it is possible to string together existing behavioral
templates that compose basic HCI tasks, (e.g., mousing to a button and
clicking on it) in order to generate powerful human performance
predictions. Because interleaving of templates is now automated, it
becomes possible to construct arbitrarily long sequences of
behavior. In addition, the manipulation and adaptation of complete
models becomes dramatically easier. CPM-GOMS is a powerful modeling
method that may have remained underused because of expertise and labor
required. Apex-CPM provides a computational engine for CPM-GOMS,
greatly facilitating the modeling of human performance and the
millisecond level.
____________
STANFORD NETWORKING SEMINAR
on Thursday, 10 October 2002, 12:45pm (lunch 12:15pm)
Gates 104
http://netseminar.stanford.edu/
Analysis of a Campus-wide Wireless Network
David Kotz
Dartmouth College
[Joint work with Kobby Essien]
Understanding usage patterns in wireless local-area networks (WLANs)
is critical for those who develop, deploy, and manage WLAN technology,
as well as those who develop systems and application software for
wireless networks. This paper presents results from the largest and
most comprehensive trace of network activity in a large, production
wireless LAN.
For eleven weeks we traced the activity of nearly two thousand users
drawn from a general campus population, using a campus-wide network of
476 access points spread over 161 buildings. Our study expands on
those done by Tang and Baker, with a significantly larger and broader
population. We found that residential traffic dominated all other
traffic, particularly in residences populated by newer students;
students are increasingly choosing a wireless laptop as their primary
computer. Although web protocols were the single largest component of
traffic volume, network backup and file sharing contributed an
unexpectedly large amount to the traffic. Although there was some
roaming within a network session, we were surprised by the number of
situations in which cards roamed excessively, unable to settle on one
access point. Cross-subnet roams were an especial problem, because
they broke IP connections, indicating the need for solutions that
avoid or accommodate such roams.
About the speaker: David Kotz is an Associate Professor of Computer
Science at Dartmouth College in Hanover NH. He received the M.S. and
Ph.D degrees in computer science from Duke University in 1989 and
1991, respectively. He received the A.B. degree in computer science
and physics from Dartmouth College, Hanover NH, in 1986. He rejoined
Dartmouth College in 1991 and was promoted with tenure to Associate
Professor in 1997. His research interests include context-aware
mobile computing, intrusion detection, multiprocessor file systems,
and mobile agents. He is chair of ACM SIGOPS, and a member of the
ACM, IEEE Computer Society, and USENIX associations, and of Computer
Professionals for Social Responsibility.
____________
UC BERKELEY CIS SEMINAR
on Thursday, 10 October 2002, 4:00pm
Soda Hall 310 (UC Berkeley)
http://www.cs.berkeley.edu/~eyal/cis-seminar
The State of the Art in Language Modeling: Short Version
Joshua Goodman
Microsoft Research
http://research.microsoft.com/~joshuago/
Language models predict the probability of word sequences. They are
useful for areas like speech and handwriting recognition, as well as
machine translation, soft keyboard entry, information
retrieval. Techniques from language modeling have even been achieving
state of the art performance for modeling patterns of web page
usage. In this talk, I will give a quick overview of some of the most
useful techniques in language modeling, including trigrams, smoothing,
caching, clustering, skipping, sentence mixture models, and
structure-based (parsing) techniques. I will show that by combining
all of these techniques (except parsing), we can reduce perplexity by
up to 50%. Most of these techniques are useful in other areas besides
language modeling. This talk is a highly condensed (3 to 1) version
of the tutorial I presented at NA-ACL and AAAI and will be presenting
at AMTA; people who have seen that tutorial will probably not want to
attend this talk.
____________
SRI AI SEMINAR SERIES
on Thursday, 10 October 2002, 4:00pm - 5:30pm
EJ228, SRI International
http://www.ai.sri.com/seminars/
An Object-Based Interaction for the Operation of Multiple Field Robots
Hank Jones
Aerospace Robotics Laboratory (ARL), Stanford University
Note: This talk discusses a project that utilizes the Open Agent
Architecture (OAA), developed at SRI. Today's field robots, such as
the Mars Sojourner rover or the Predator unmanned aerial vehicle, work
alone to accomplish dirty, dull, or dangerous missions. However, the
design specifications for future missions call for multiple robots to
work together to perform complex tasks. Although the success of this
cooperation certainly will require significant advances in artificial
intelligence and autonomy for the robots, the important role of the
human operator in such a system has been somewhat overlooked. A
user-centered approach to design the human-robot interaction is
desired. Unfortunately, there are no user settings to study because no
multiple-robot systems have been deployed. As an alternative, this
research sought a surrogate setting that could be studied to inform
the early interaction designs for multiple-robot systems. Police
Special Weapons and Tactics (SWAT) teams were chosen as this setting,
and an ethnographic study of SWAT commanders was conducted. For
tasking and localization of their units, SWAT commanders were observed
to utilize dialogues based on shared physical objects in their
environment. Concepts from the interdisciplinary field of Remote and
Distributed Work were applied for the first time to robotics. Using
the lessons learned through the surrogate setting, a human-robot
interaction was developed for the Micro Autonomous Rovers platform in
the Aerospace Robotics Laboratory at Stanford University. This
interaction is built around localization and tasking dialogues that
focus on the physical objects sensed by the robots. In this way, a
single operator can readily coordinate the actions of multiple robots.
The presentation will conclude with a video of the robots in operation
using a 3-D graphical user interface to the object-based interaction.
About the speaker: Hank Jones is a soon-to-graduate PhD candidate in
Aeronautics and Astronautics at Stanford University, working in the
Aerospace Robotics Laboratory (ARL). He was the co-leader of the ARL's
autonomous helicopter project, where his primary contribution was the
development of a point-and-click task-level interaction for the
operator interface. Hank has recently designed and developed operator
interfaces for three other PhD thesis projects in the ARL through the
course of his own research. His primary interest is the application of
user-centered design principles to robotics and embedded systems.
____________
SSP10: SYMBOLIC SYSTEMS FORUM
on Thursday, 10 October 2002, 4:15pm
Bldg. 380:380C (Math Corner)
http://symsys.stanford.edu:8081/ssp-dynamic/servlet/ssp_eventsxo
Developmental Stability and Evolution:
Possible Link Between Micro- and Macro-Evolution
Aviv Bergman
Center for Computational Genetics and Biological Modeling
Stanford University
(aviv at stanford dot edu)
Most species harbor abundant genetic variation and experience a range
of environmental conditions, yet phenotypic variation in key traits is
low. That is, development is robust to changes in genotype and
environment. It has been postulated that this robustness, termed
canalization, is a product of stabilizing selection. By this view,
natural selection yields a genetic system that not only produces the
optimal phenotype on average, but also reduces the phenotypic
variance. Support comes from demonstrations of increased phenotypic
variance under extreme genetic or environmental perturbation, and from
theoretical studies. However, there is concern that strong selection
may prevent evolution of canalization, that evolution of canalization
under stabilizing selection may be slow, and that canalization does
not explain why some traits have greater genetic variance than
others14. We show that the developmental process, here modeled as a
network of transcriptional regulators, constrains the genetic system
so as to produce canalization, even without selection toward an
optimum. We argue that canalization may be an inevitable consequence
of stable development, and therefore requires no explanation in terms
of evolution to suppress phenotypic variation.
____________
LOGIC LUNCH
on Friday, 11 October 2002, 12 noon
Math Corner 380:383N
http://www-logic.stanford.edu/seminars.html
G\"odel's Developing Platonism
Martin Davis
Visiting Scholar UC Berkeley
Professor Emeritus, NYU
G\"odel started out almost dismissive of a platonist philosophy of set
theory, and only over many years moved to the fully platonist point of
view with which he is usually identified. By suggesting that his final
position was the one he had always held, G\"odel has made it difficult
to trace his evolving views. In this talk I will point out various
markers on his intellectual odyssey. If time permits, I will say
something about my own views.
____________
CS547: HUMAN-COMPUTER INTERACTION SEMINAR
on Friday, 11 October 2002, 12:30-2:00pm
Gates B01
http://www-pcd.stanford.edu/cs547/
Desire in Context
Rich Gold
The Red Shift
Engineers often conceive of their work as solving problems usually by
reorganizing the physical world, or in the case of computer science,
by writing a program that alters a receptive machine. The literature
is replete with methods for finding such solutions along with metrics
for their efficiency, economy and completeness. But what exactly is
the definition of a problem the supposed target of all this activity?
Where do problems come from, what is their nature and is there a way
of understanding them that will positively impact, not only what we
consider a worthy solution, but what we consider good engineering? In
this talk I will propose the definition for a problem as a desire in a
context and look at the process of engineering through this useful, if
slightly flawed, lens. One difficulty in this definition lies here:
while most engineers are comfortable with the idea of context, desire
is usually relegated to the domain of the designer. This broader
definition, desire in context, conflates what are often treated as two
distinct cultures.
About the speaker: Rich Gold is an engineer, artist, designer, writer
and cartoonist who brings together ideas and methodologies from
different disciplines to create stuff for people to enjoy. He was a
co-founder of the League of Automatic Music Composers, the first
network computer music band (1975). He invented the award winning
Little Computer People program (Activision, 1984) which was the first
artificially intelligent human you could buy. At Mattel Toys he
managed the PowerGlove home VR project (1989) and designed many other
interactive toys. For ten years he was a researcher at Xerox PARC
(1991 2001) on the Ubiquitous Computing Project. He also set up and
managed the PARC Artist in Residence Program (PAIR) and the Research
in Experimental Documents (RED) Group which combined art, science,
design and engineering to create Evocative Knowledge Objects. He
currently is consultant working on the future of reading and knowledge
exchange.
____________
NLP READING GROUP
on Friday, 11 October 2002, 2:15pm
Margaret Jacks Hall, Room 460:301
http://www-nlp.stanford.edu/nlp/nlpgroup.html
Heuristic dependency-parsing based on local search
Matthias Kromann
Copenhagen Business School
We will briefly present a heuristic parser based on local search,
and explain its potential benefits and dangers in terms of
parsing efficiency, robustness, disambiguation, linguistic
coverage, precision, and psycholinguistic plausibility.
We will then explain how the success of our parsing algorithm
depends on the locality of the underlying syntax formalism,
and why this encourages the use of a syntax formalism based on
dependency structure rather than phrase structure.
Finally, if time permits, we will sketch some ideas for extending
our parser to solve various morphological and syntactic problems:
morphological parsing, the Danish possessive clitic "'s", spoken
language analysis (without clear word boundaries or punctuation),
robust handling of unknown words, and elliptic coordination.
Relevant readings:
* Matthias T. Kromann, "Optimality parsing and local cost functions in
Discontinuous Grammar", Formal Grammar and Mathematics of Language
Conference, Helsinki 2001, to appear in Electronic Notes of
Theoretical Computer Science, vol. 53, 2001.
http://www.id.cbs.dk/~mtk/files/011001-entcs.pdf
* Matthias T. Kromann, "Robustness and discontinuity in local
optimality parsing", handout for the 26th Penn Linguistics
Colloquium, March 2002.
http://www.id.cbs.dk/~mtk/files/020302-plc26-hnd.pdf
* Matthias T. Kromann and Line Mikkelsen, "Danish Dependency Treebank:
Annotation guide", incomplete work in progress, October 2002.
http://www.id.cbs.dk/~mtk/treebank
____________
STANFORD TGIF
on Friday, 11 October 2002, 2:00pm - 3:30pm
Turing Auditorium
http://tgif.stanford.edu/
Wireless Technologies @ Stanford
Chudi Igboemeka and Mark Branom
ITSS, Stanford
ITSS is offering wireless services to the Stanford community this
fall. Wireless networking allows laptop users to access network
resources from locations where wiring is not available, providing
increased flexibility and productivity. Currently, ITSS Wireless
Service is located at the Main Quad, Jordan Quad, Tresidder and the
Arrillaga Alumni Center Cafe. Wireless also exists in other areas on
campus such as the Law School, Med School, Engineering, and
libraries. ITSS is planning to extend the wireless network to other
locations across the campus. Join Chudi Igboemeka and Mark Branom as
they walk us through the growing world of wireless at Stanford.
TGIFs are informal, interactive sessions on computer-related topics of
interest to the Stanford community. Bring your questions! Sessions are
led by knowledgeable ITSS staff. These sessions are open to faculty,
staff, and students -- no registration is required.
____________
STANFORD PHONOLOGY WORKSHOP
on Friday, 11 October 2002, 5:00pm
Margaret Jacks Hall 460:126
http://www-linguistics.stanford.edu/pinterest/
Variable Vowel Epenthesis in Picard
Julie Auger
Indiana University
One striking feature of Picard (a language closely related to French)
concerns the regular insertion of epenthetic vowels in order to break
up consonant clusters and syllabify word-initial and word-final
consonants. This corpus-based study focuses on word-initial
epenthesis. It provides quantitative evidence that vowel epenthesis
applies categorically in some environments and variably in
others. Probabilistic analysis reveals that the variable pattern is
constrained by a complex interplay of linguistic factors. Following
Labov (1972) and Anttila & Cho (1998), I interpret this result as
evidence that this variation is a reflection of a grammatical
competence that generates variable outputs. An Optimality Theory
analysis that generates both categorical and variable aspects of vowel
epenthesis is proposed. Finally, an analysis of individual patterns of
epenthesis by members of the community reveals that, even though all
speakers share the same basic community grammar, their use of
epenthesis differs qualitatively as well as quantitatively. This paper
shows that individual grammars can be derived from the community
grammar and that OT thus allows us to formalize the idea that
individual grammars constitute more specific versions of community
grammars.
____________
BROAD AREA COLLOQUIUM FOR
AI-GEOMETRY-GRAPHICS-VISION-ROBOTICS
on Monday, 14 October 2002, 4:15pm
TCSeq 200
http://robotics.stanford.edu/ba-colloquium/
The Level Set Method - What's In It For You?
Stan Osher
Department of Mathematics, UCLA
The level set method for capturing moving fronts was introduced in
1987 by Osher and Sethian. It has proven to be phenomenally successful
as a numerical device. For example, typing in "Level Set Methods" on
Google's search engine gives roughly 3200 responses. Applications
range from capturing multiphase fluid dynamical flows to special
effects in Hollywood to visualization, image processing, control,
epitaxial growth, computer vision and many more. In this talk we shall
give an overview of the numerical technology and a few graphics
oriented applications.
About the Speaker: Stan Osher is Professor of Mathematics and Director
of Applied Mathematics at University of California, Los Angeles. He is
the coinventor and a principle developer of widely used
state-of-the-art high resolution schemes for approximating hyperbolic
conservation laws and Hamilton-Jacobi equations; level set methods for
computing moving fronts involving topological changes; total variation
and other partial differential equations based image processing
techniques. Dr. Osher has been a Fulbright Fellow, Alfred P. Sloan
Fellow, SERC (England) Fellow, U.S. - Israel Binational Fellow,
received NASA Public Service Groups Achievement Award, and was an
invited speaker at the International Congress of Mathematicians.
____________
EE380: COMPUTER SYSTEMS LAB COLLOQUIUM
on Wednesday, 16 October 2002, 4:15pm to 5:30pm
NEC Auditorium (B03), Gates Computer Science Building
http://ee380.stanford.edu/contents.html
Quantitative Go, and Some Other Combinatorial Games
Elwyn Berlekamp
University of California at Berkeley
Combinatorial game theory is concerned with two-person
perfect-information games, especially those classes of positions for
which winning strategies can be stated explicitly, or at least proved
to exist. The powerful mathematical methods (often requiring only
paper and pencil, no computers) are most successful when applied to
games whose positions often decompose into "sums". The many examples
of such games include Nim, Dots and Boxes, Hackenbush (best played
with colored chalk and erasures), Domineering (played with dominoes on
a checkerboard), Konane (popular in ancient Hawaii), Amazons (invented
less than fifteen years ago, but which has attracted a substantial
following on the Internet), and Go (a popular Asian board game dating
back several thousand years, and which supports nearly 2,000 active
professionals today). The theory also applies very well to the
fascinating new game called "Clobber", invented in Nova Scotia in the
summer of 2001.
In many of these games, a mathematically defined "temperature"
provides a numerical measure of the value of the next move. The
extension of this notion to loopy positions, such as kos in Go,
appeared in "Games of No Chance" in 1996. A subsequent extension,
called "Environmental Go", includes a stack of coupons in addition to
the Go board. This has led to fruitful collaborations between game
theoreticians and professional 9-dan Go players. For the past four
years, we have been developing methods and techniques which allow us
to get rigorous analyses of the last 50 to 100 moves of some
professional games, and we not infrequently discover fatal mistakes.
We will present a broad introductory overview of this subject,
including a fascinating problem in which Go, chess, checkers, and
domineering are all played concurrently.
The time may now be ripe for new efforts to combine modern
mathematical game theory with alpha-beta pruning and other traditional
AI minimax search techniques.
About the speaker: Elwyn Berlekamp has been Professor of Mathematics
and of Electrical Engineering/Computer Science at UC Berkeley since
1971. He was associate chairman of EECS for computer science at
Berkeley in 1975-77. In the late 1980s he also served four years on
the UC President's Science Advisory Committee for Los Alamos and
Livermore National Laboratories.
In the early 1980s, Berlekamp took industrial leaves and reduced his
faculty appointment to part-time to pursue off-campus ventures. He was
founder and president of Cyclotomics, which was acquired by Eastman
Kodak in 1985 and renamed "Kodak Berkeley Research", and a cofounder
of several other successful companies, including IC Designs and
Cylink. (NASDAQ: CYLK)
Berlekamp has 12 patented inventions (now all public domain), mostly
dealing with algorithms and devices for synchronization and
error-correction. He has nearly 100 publications, including 2 books on
algebraic coding theory and 4 books on the mathematical theory of
combinatorial games, the most recent of which is "The Dots and Boxes
Game", recently published by AK Peters. This book will be featured in
Scientific American's January 2001 issue. Berlekamp is a member of the
National Academy of Sciences, the National Academy of Engineering, and
of the American Academy of Arts and Sciences. From 1994-1998, he was
chairman of the board of trustees of the Mathematical Sciences
Research Institute (MSRI).
Since 1991, Berlekamp's primary research interest has been extensions
of the mathematical theory of games and applications to Go. He chaired
the organizing committee of a workshop at MSRI in July 2000, about
which more information can be found at http://www.msri.org/ .
____________
SYNTAX WORKSHOP
on Wednesday, 16 October 2002, 6:00pm
for location email bzack (at) stanford.edu
http://www-linguistics.stanford.edu/sssg/
How many grammars do we need?
Guido Seiler
University of Zurich
Variation and optionality within one grammar have been a notorious
challenge for syntactic theory. However, empirical evidence from
syntax geography suggests that in many cases variation cannot be
plausibly accounted for by the co-presence of two (or more) grammars
in a speaker's mind. In this talk I will try to distinguish (i) such
cases, where it is necessary to design (single) grammars that predict
optionality and preference directions between options, (ii) from cases
where it perhaps makes sense to trace back variation to two separate
grammars (despite the technical possibilities Stochastic Optimality
Theory gives us).
____________
STANFORD NETWORKING SEMINAR
on Thursday, 17 October 2002, 12:45pm (lunch 12:15pm)
Gates 104
http://netseminar.stanford.edu/
Zero Configuration Networking
Stuart Cheshire
Apple
Zeroconf promises to bring true plug-and-play to the Internet Protocol
(IP), by enabling users to automatically find and connect to IP
devices using Multicast DNS and service-based lookups. This talk will
cover the technical details of Zeroconf, and Rendezvous, Apple's
implementation of Zeroconf.
About the speaker: Stuart Cheshire is currently a senior engineer at
Apple and is the architect behind Rendezvous, Apple's revolutionary
home networking technology. He is also co-chairman of the IETF
Zeroconf Working Group. He previously worked on IBM Token Ring with
Madge Networks in the UK and has published research papers in the
areas of wireless networking and Mobile IP. Dr Cheshire received
B.A. and M.A. degrees from Sidney Sussex College, Cambridge, UK. He
holds M.S. and Ph.D. degrees from Stanford University, California.
____________
SRI AI SEMINAR SERIES
on Tuesday, 17 October 2002, 3:00pm
EJ228, SRI International
http://www.ai.sri.com/seminars/
Visual and Auditory Spatial Sensing
Stan Birchfield
Quindi Corporatio
Humans rely predominantly upon their eyes and ears to gather
information about the three-dimensional world, such as the shapes and
locations of objects. It is not surprising, then, that the two primary
types of data for automatic sensing in 3D are also video and audio. In
this talk I will discuss the two classic problems of stereo vision and
acoustic localization. We will see that both problems share much in
common, although they differ in many ways as well. For both problems,
I will describe some of the challenges involved, as well as the latest
research trends. Stereo vision experienced a significant breakthrough
a few years ago when algorithms based on graph cuts were shown to be
able to minimize functionals over the entire image. I will describe
these techniques and some extensions that have been added by myself
and others, as well as point out situations in which the graph-cut
algorithms fail. A similar breakthrough has occurred in acoustic
localization, where researchers have recently discovered that all the
signals can be taken into account in an efficient manner, thus
replacing the previous sub-optimal and time-consuming methods. I will
describe our latest work on this problem, including a unifying
framework that encompasses the recently discovered efficient method
along with the Bayesian formulation and the traditional beamforming
and time-delay-estimation methods. In addition, I will show how the
algorithms can be used to detect multiple simultaneous sound sources.
Together, this work on stereo vision and acoustic localization brings
us a little closer toward achieving the goal of robust spatial
sensing.
____________
CSLI SEMINAR ON COMPUTATIONAL LEARNING AND ADAPTATION
on Thursday, 17 October 2002, 4:15pm to 5:30pm
Cordura 100
http://cll.stanford.edu/scla.html
Lloyd Clustering of Gauss Mixtures
Robert M. Gray
Information Systems Lab, EE, Stanford
An early application of statistical clustering was Stuart Lloyd's 1959
algorithm for designing optimal quantizers, an algorithm commonly
known in communications and signal processing applications as the
"Lloyd-Max" algorithm. Quantization, or source coding with a fidelity
criterion as it is known in Shannon information theory, strongly
resembles a variety of problems that have arisen through the years in
communications, signal processing, statistics, and mathematics.
Included are several statistical clustering approaches such as
k-means, the problem of sums of moments, and the problem of
approximation of continuous probability distributions by discrete
ones. The goal of this talk will be to describe the general
quantization problem as it is typically formulated in information
theory and to survey the state of the theory and design
algorithms. Brief mention of similar problems in other fields will be
made, but the specific examples used to illustrate the ideas will be
the "worst case" role played by Gauss and Gauss mixture models and a
resulting approach to designing Gauss mixture models from learning
data via Lloyd clustering with a relative entropy distortion measure.
____________
STANFORD PHONOLOGY WORKSHOP
on Thursday, 17 October 2002, 5:30pm
Margaret Jacks Hall 460:126
http://www-linguistics.stanford.edu/pinterest/
Model theory and the content of OT constraints
Christopher Potts and Geoffrey K. Pullum
Linguistics, UC-Santa Cruz
We develop an extensible metalanguage for stating the content of
optimality-theoretic constraints in phonology, and specify a class of
structures for interpreting it. The aim is a transparent formalization
of OT constraints. Our proposal meshes well with recent work on
constraint ranking instigated by Karttunen and more fully developed by
Samek-Lodovici and Prince (SLP). We show how to state a wide range of
constraints, including markedness, input--output faithfulness,
base--reduplicant faithfulness, and paradigm uniformity. However,
output--output correspondence, sympathy, and targeted constraints are
revealed to be extremely problematic. It is unclear that any
reasonable class of structures can reconstruct their proponents'
intentions. They are also inconsistent with the developments of SLP.
For the most part, the problematic constraint types were developed to
deal with opacity, which therefore remains the most important
theoretical crux for current OT. We hope to shed new light on this
debate, by subjecting some common responses to it within OT to
critical investigation.
____________
END MATERIAL
The CSLI Calendar appears weekly on Wednesdays throughout the academic
year. Announcements, abstracts, and other information to appear in
the Calendar should be submitted to the editor, who reserves the right
to decide what does or does not go in the calendar
mailto:incalendar@csli.stanford.edu
Requests to be added to the mailing list should be sent to
majordomo@csli.stanford.edu. With the lines in the body of the text
of either
subscribe csli-calendar
for the long form or
subscribe csli-short-calendar
for the short form (i.e., no abstracts). Problems with subscribing or
unsubscribing should be sent to
owner-csli-calendar@csli.stanford.edu.
The full current issue is at
http://www-csli.stanford.edu/Archive/calendar/current.shtml
and the archives at
http://www-csli.stanford.edu/Archive/calendar/
People on most of the CSLI computers can type 'help csli-calendar' to
see the current issue.
The CSLI Calendar is also posted each week to
news://nntp-csli.stanford.edu/csli.bboard.
and
news://news.stanford.edu/su.events
Information about CSLI's research program is available at
http://www-csli.stanford.edu/
For maps to the Stanford University campus see
http://www.stanford.edu/home/visitors/maps.html
____________