Article 46 of bionet.mycology:
Path: samba.oit.unc.edu!concert!gatech!howland.reston.ans.net!agate!darkstar.UCSC.EDU!nathan
From: nathan@cse.ucsc.edu (Nathan J. Wilson)
Newsgroups: bionet.mycology
Subject: Using computers to study mushrooms (1 of 2)
Date: 3 Sep 1993 20:33:19 GMT
Organization: University of California, Santa Cruz (CE/CIS Boards)
Lines: 184
Distribution: world
Message-ID: <2689mgINNrsn@darkstar.UCSC.EDU>
NNTP-Posting-Host: arapaho.ucsc.edu

This is the first of two documents related to my efforts to create computer
programs that will be helpful for studying mycology.  The one below is a 
newsletter article aimed at knowledgable yet amature mycologists (i.e. 
mushroom enthusiasts) with minimal knowledge of computers.  The second 
article, posted separately, is aimed at computer scientists with little 
or no knowledge of fungi.

Although neither of these articles are aimed at people who are 
knowledgable about both computers and fungus taxonomy, I am especially 
interested in contacting such people at the moment to talk over the 
architecture and implementation of my next generation of software.  The 
software I have created to date include a synoptic key style identification 
system (the principle subject of the two articles) and small utilities 
for creating species lists and name labels.

-Nathan Wilson

--- Begin article ---

The Future of Mushroom Identification

Like many of you my favorite hobby is mycology. I've been studying 
mushrooms on and off for over 15 years.  Most of what I've learned comes 
from field guides, supplemented by what I can pick up from others at 
forays and meetings.  This learning process has been slow and at times 
frustrating and tedious.  For example, I believe I just found my 
first Leucocoprinus luteus, a beautiful brilliant yellow Lepiota-like species.
Most of the books I have give short descriptions of one or maybe two 
species in this genus and one gives a description of the genus, but I 
want to know more.  How many described species are there in this group?  
How often does it occur in my area?  What is its world wide distribution?

To find out more I would have to try to find someone who knows more 
about the genus or at least tell me a few references.  If that doesn't 
work I would have to arrange access to the library collection in San 
Francisco and then find the time to make the hour and a half drive to San 
Francisco and spend a day hunting down the answers to my questions.

It also bothers me that if I did go to the effort to track this information
down, that my only way to share it with others is by talking to them at 
forays or, if I where really ambitious, by someday including it in a book.
Professionally, I'm a computer scientist, and this part of me rebels at 
the inefficiency of these methods.  I should be able to sit down 
at my computer, and quickly find descriptions of all the relevent species.  
Furthermore, I should be able to use my computer to help me identify the 
species and to record my observations.  Finally, I should be able to make my 
observations  available to others who might be interested in the species in 
the future. Here is a short story demonstrating the use of some future 
version.

Stardate 22938.1.  Planet Earth.  Yosemite Valley.

Student 1: Great field trip!  What did you see?
Student 2: I'm not sure, but I collected a few samples for identification.
Student 1: Wow!  Those are neat.  Let's see what we can find out with your 
        tablet.
Student 2: OK, let's see...Yosemite Valley...Wildlife...Identification.  It's 
        requesting features of the organism.
Student 1: Well, they're sort of like a brown plant.
Student 2: Yes, and 5 to 9.4 cm high and 3.6 to 5.4 cm wide, dark brown, 
        made of a soft but slightly brittle substance.
Student 1: and sort of like a sponge or a pine cone.
Student 2: The tablet is asking if the surface is wrinkled or pitted.
Student 1: I'd say pitted.
Student 2: Hmm, now it wants to know which picture better describes the 
        cross section.
Student 1: Let me cut one in half.
Student 2: The more hollow one.  There it's come up with an identification:  
        Morchella elata (M).
Student 1: What does the "M" mean?
Student 2: Here it is.  "A species name followed by (M) indicates a `macro-
        species' or a group of species that are macroscopically 
        indistinguishable.  To more precisely identify your specimen it 
        would be necessary to examine either the microscopic or chemical 
        characteristics.  The nearest facility with such equiptment is the 
        Lower Yosemite Valley Ranger Station."
Student 1: Does it say any more about what we found?
Student 2: Yes.  It is a fungus or mushroom common this time of year in this 
        part of the planet.  It is also known as the Black Morel  There are 
        124 recognized micro-races forming 25 reproductively isolated 
        species.  It is one of a number of macro-species known as Morels all 
        of which are in the genus Morchella.  Several of these species are 
        cultivated as a delicacy.
Student 1: Mmmm, delicacy.
Student 2: In addition, they are still collected in the 
        wild for recreation and consumption.  However, it warns that the 
        species is poisonous unless properly prepared and that 
        inexperienced collectors should be sure to precisely identify the 
        species before trying them.  Further information includes a list of 
        the species and their descriptions, as well as references dating 
        back almost 300 years.
Student 1: Well that's enough for me.  I want to go on that hike up the falls 
        this afternoon.
Student 2: I'll be at the ranger station.  I want to find out more.
Student 1: Well if you decide to eat them, let me know.  I'd like to try them!
Student 2: OK.

I am currently working on creating a computer based system that would be capable
of performing the role of the 'tablet' in this fable.  I would like it to 
include a way to perform taxinomic identification, to record field 
observations, and to easily extend the underlying database of species.
I am working on a masters degree in computer science and hope to 
make this project my thesis.  I already have a simple prototype up and running
that principally addresses the identification problem.  I am currently
searching for 
other people who are interested in these ideas and would like to help make 
them a reality.

My ultimate goal is to create a system that can carry all the current 
knowledge of fungi and which can be extended and updated as new things 
are learned.  I believe that it is critically important for the results 
of this project to be freely available to anyone to encourage use, 
interchange, and development.  The current idea is that all data in the 
system would indicate both who developed it and who entered it into the 
system.  Data that becomes `obsolete' would remain accessible in a 
historical record.

There are several other important issues pointed out by this fable that I 
hope my project will handle.  One is another take on the latin versus 
common name issue.  I see names as the way we connect something to 
previous knowledge.  As we extend our knowledge names necessarily 
change.  At the same time the old knowledge and old names remain 
important and often capture important connections.  For example, in the 
fable the concept of a macro-species remains important since it describes 
a set of species which are related simply because they cannot be 
differentiated by the human eye.  Obviously both common names and latin 
names carry important information.  By including all of this information 
in the computer system, it would be easy for two people to make sure that
the names they are using refer to the same thing.

A second point of the fable is to acknowledge an important tension 
between so called 'lumpers' and 'splitters'.  The issue as I see it is
between what we know and what we don't know.  Lumpers are trying to organize the
information that we know into a coherent order that is reliable, easily learned,
and accessible.  Splitters are trying to extend our knowledge of fungi and
understand more precisely the relationships between species and their roles in
the natural world.  Both of these endeavours are important, but they should be
done together in an organized way.  I see my proposed project connecting
these two endeavours, by providing a complete, though easily used, 
reference which gives the user as much information as they want.

In general, I try very hard not to use what I have gathered to be the most 
accurate scientific name for the species I identify.  However, given the 
current accessibility of accurate information, the names I end up using 
are often inaccurate.  Often the closest description I have to a species 
I collect is from a guide that is several years old and I have no way of 
knowing if it is still correct information.  This is because at best a 
book is a snapshot of the knowledge of at most a few people at a 
particular point in time.  A computer system, on the other hand, could be 
dynamically updated through the various computer networks that are 
currently available throughout the world.

This points out another important issue which we must not lose sight of. 
A species name is a pigeon-hole that we humans have created to help us 
categorize the world around us.  These pigeon-holes will never be a 
completely correct description of the relationships between the individual
organisms.  Mushrooms will always be evolving and changing.  New strains 
will arise, and new species will develop.  Our task as enthusiastic 
fungophiles is to develop the knowledge and share it with others so we 
can better understand and appreciate these fascinating creations.

As for helping with the project, anyone can help.  The only requirements for
helping are willingness, and a computer.  Tasks include data entry, program
testing, discussion of design issues, programming new features, and 
making it work on different types of computers.  You do not have to feel 
you are an expert to help.  Simply getting the knowledge that can be 
learned from the most common guide books into the system is a daunting 
task, and it can be a wonderful way to learn new things about the species 
you work on.

I look forward to hearing from you,

Nathan Wilson
Co-Science Advisor and Minister of Local Forays
Fungus Federation of Santa Cruz
1620 Bay St.
Santa Cruz, Ca 95060
(408)423-3773
Internet: nathan@cse.ucsc.edu
-- 
 ---------------------        _________
     Nathan Wilson           <_________>
nathan@taurus.apple.com          |_|         It is no dream!
   velosa@apple.com             /___\     Matsutake are growing


Article 47 of bionet.mycology:
Path: samba.oit.unc.edu!concert!gatech!howland.reston.ans.net!agate!darkstar.UCSC.EDU!nathan
From: nathan@cse.ucsc.edu (Nathan J. Wilson)
Newsgroups: bionet.mycology
Subject: Using computers to study mushrooms (2 of 2)
Date: 3 Sep 1993 20:35:41 GMT
Organization: University of California, Santa Cruz (CE/CIS Boards)
Lines: 315
Distribution: world
Message-ID: <2689qtINNs10@darkstar.UCSC.EDU>
NNTP-Posting-Host: arapaho.ucsc.edu

This is the second of two documents related to my efforts to create 
computer programs that will be helpful for studying mycology.  The one
below is a report written for an independent study I did last year in
graduate school.  It is aimed at knowledgable computer scientists with 
little or no knowledge of mushrooms.

-- Begin report --

Final Project Report
Independent Study - Winter 1993
Developing a Computer System for Taxonomic Identification

Nathan Wilson
March 25, 1993


* Goals *

The purpose of this project is to develop a general purpose taxinomic
database using fungi as a case study.  The general concept behind
the system is for the user to be able to specify values for a set of
features and have the system search through a database of species
descriptions for matches to the specified set.  The effort for the
project had four principle components: developing the database
engine, designing and creating the user interface, creating a small
trial database, and an attempt to find an efficient search method.
In addition, the system includes an advisory facility for helping the 
user to decide which feature to enter values for next.


* The System *

The system as it currently stands includes a database and a program.
The program, in turn, is conceptually divided into two parts: the
database engine which is responsible for executing any requested
transactions on the database, and the user interface which gets input
from the user, passes these requests on to the database
engine, and displays result returned by the database.  The database
engine communicates with the user interface through a small command
language.  The goal of creating this distinction is to aid in future
attempts to port the system to other platforms.  At the moment, the
system runs only on Apple Macintoshes, though I expect to create a
command line interface for it in the near future.

 + Database Engine +

The database consists of a set of 'descriptions', one for each
species.  A description consists of a set of 'features'.
The features each have a unique 'field' name by which they can be
accessed, and a set of 'values'.  Currently the values are a
subset of a set of names associated with each feature.  There are two
special fields `Genus' and `species'.  Each of these fields have a
specially marked value, known as the 'canonical' value.  The
combination of the canonical value for the `Genus' and `species'
fields uniquely identify a particular description.

The database engine includes facilities for reading, writing and merging
databases; adding new descriptions, features or values; and searching the
database.

 + The User Interface +

The user interface for the Macintosh includes two windows, the
'selection' window, and the 'feature' window.  The selection window
includes a scrolling list of the canonical genera.  One of these can
be selected from the list either with the mouse or by typing.  Name
completion and keyboard scrolling are supported.  After a genus has
been selected a list of the canonical species names which have that
genus as their canonical genus appears in another list.  Selecting a
species causes that description to be added to a special sub-database
called the 'selection'.  Most of the transactions the user
performs on the database are with respect to the selection.  For
example, the advisory system only looks at the members of the
selection when deciding which features to suggest.

The user typically interacts with the system by constructing their
own, typically incomplete, description known as the 'key' in the
feature window.  The process of constructing the key is similar to the
species selection process.  The key can be inserted directly into the
database as a new description, or it can be used to manipulate or extend
the selection.  The descriptions in the selection can be changed by
either adding or removing values for each feature in the key.  If
a description already has a value for a given feature, then a set
union or set difference operation is performed.

 + Searching +

The search facilities are also controlled with the key.  Descriptions
that match the key can be either added or removed from the selection.
In addition, all descriptions that do not match the key can be removed 
from the selection.  For completeness it might be good to add an option 
to add all descriptions from the database that do not match the key, but I
have yet to find a need for this option.

The user can choose between two matching policies.  The 'or' policy is
that a description and the key are considered to match if the intersection
of the values for each of the features in the key is non-empty.  The
'and' policy is that a match only occurs if for each feature the
values in the key are a subset of the values in the description.  In
my own use of the system I have used the 'or' policy almost
exclusively.

 + Most Specific Generalizers and Concepts +

Another search related feature is that the key can be modified by 
selecting a particular species from the selection window and finding the 
most specific generalizer between that description and the key.  If the 
key is empty then the key becomes the entire description.  There is also a
facility that attempts to construct an entire partial order of the possible
generaliers for the entire set of descriptions.

 + The Advisory System +

The advisory system works by sorting the features on the basis of the
selection.  The user can choose between three different sorting methods.
The simplest is the 'Count' method.  For each feature the number
of values used in the selection is counted.  A feature is considered to
be better if it has more values.

The other two keys are based on not only the number of possible
values, but also the number of times each value occurs over the entire
selection.  In the 'MinMax' method, the feature whose most common
value occurs the least often in the selection is considered the best.  
Finally, the 'LogSum' method uses the sum of the logs of the value counts
to sort the feature, with the highest sum being the best.

 + The Database +

The database created this quarter contains descriptions for 50 species
of fungi.  All descriptions were based on published descriptions of
the species ([Arora, 1986], [Jenkins, 1986], and [Thiers et al.]).
Each species description has 58 features whose values are each a
subset of the values possible for that feature.  The choice of
features and values was based on [Largent, 1986].  There are between 2
and 50 values for each feature, and 333 values across all the
features.  Most features had less than 10 possible values.


* Searching for Efficient Search *

(illustration showing number of concepts as species are added)
        
The focus of this part of the effort was to try to use the partial
order of the most specific generalizers across all the subsets of the
species.  The hope was that this partial order would be
sparse due to the latent structure created by the biological
relatedness of species.  The figure shows that some
savings was in fact found over the worst case exponential growth that
would be expected with a randomly selected set of descriptions.
However, the savings is not sufficient to consider using this partial
order directly to help structure the search or retrieval tasks.
It may be that the structure that is there can be exploited
by restricting the partial order to only those subsets that have
a sizable membership.


* Evaluating Sorting Methods for the Advisory System *

The principle result of this aspect of the work is a comparison
between the sorting methods.  The MinMax sorting method is judged to
be better, though no standard measure was used to directly confirm
this judgement.

 Count                        MinMax                     LogSum
------------------------------------------------------------------------------
Habitat                    | Spore surface color      | Habitat
Stem surface texture       | Gill distance            | Months
Cap surface color          | Spore color              | Cap surface color
Stem surface texture below | Spore surface attachment | Spore surface color
Stem surface texture above | Cap surface color        | Cap shape
Spore surface color        | KOH reaction             | Cap cross section
Months                     | Cap shape                | Stem shape

        Top seven features selected by the different sorting methods
                  for the all 50 species in the database

The three different sorting methods in fact ordered the features
differently.  The above table gives the top seven features
selected by the three different methods.  The Count and LogSum methods
were the most similar with four common features.  The MaxMin and Count
methods were the most different sharing only two features.

Unfortunately, standard measures for comparing decision trees do not
easily apply in this domain due to the disjunctive nature of the database.
That is a given decision (e.g. are the gills pink) does not necessarily
partition the selection into two non-intersecting sets.  This means that
a given species can occur in more than one place in the tree.  In addition,
the user can actually enter more than one value for a given 
feature.  Thus branching factor for a given decision is potentially exponential
in the number of values a given feature has.  As a result, standard concepts
such as depth are not well defined.

Another way to compare these lists is to compare them to the set of
features standardly used by human expert mycologists or listed in
reference books ([Arora,1986], [Largent, 1986], and [Lincoff, 1981]).
Interestingly, probably the most important initial feature, the over
all structure of the mushroom, is not included in any of the lists.
Looking further down the lists this feature was 10th in the Count
list, 9th in the MinMax list, and 16th in the LogSum list.
Furthermore, another critical feature, spore color, only appears in
the MinMax top seven, and is 11th and 13th in Count and LogSum
respectively.  Finally, looking at the lists given in the first
table, the features chosen by the MinMax are all important
morphological features that standardly appear in dichotomous keys for
many different genera of fungi.  The Count and LogSum lists, on the
other hand, both include the features Habitat and Months which are not
typically used.

 Count                  MinMax              LogSum
-----------------------------------------------------------------
Habitat              | Odor              | Months
Months               | Annulus position  | Habitat
Cap surface color    | Annulus thickness | Grouping
Stem shape           | Cap staining      | Cap surface color
Spore surface color  | Stem staining     | Spore surface color
Cap staining         | Habitat           | Cap staining
Stem surface texture | KOH reaction      | Stem shape

   Top seven features selected by the different sorting methods
            for the species in the genus Agaricus

The second table gives another compelling example of this
distinction.  The table shows the same information but this time for
the subset of species that are members of the genus Agaricus.
In this group, the most important distinguishing features for field
identification are odor, and the staining reactions of the cap and
stem.  All of these are in the top seven for MinMax (1st, 4th and 5th
respectively).  Odor placed 9th and 10th for Count and LogSum
respectively, cap staining was 6th and stem staining was both 8th and
16th respectively.  To the trained eye, the inclusion of the Grouping
feature (e.g. solitary, caespitose, gregarious) by the LogSum sort is
very strange.

>From a theoretical standpoint, the apparent failure of the LogSum
method is somewhat disturbing.  In theory, such calculations should be
getting directly at the informational content of the database and
exploiting it.  There is, however, a critical difference between the
features chosen by the LogSum method and those the experts consider to
be useful.  In particular, the features the experts use have low
variance within a given species but high variance between species.

For example, in the case of the `good' features, such as over all
structure or spore color, a given species typically has between one
and three possible values, but the entire selection has many more
possible values.  For the features chosen by the LogSum method such as
the Habitat and Months features, it is not unusual for a species to
occur in many different habitats or to have a long fruiting season.

The MinMax sort is sensitive to this difference.  When a given feature
has multiple values within each species then the total counts for each
value will tend to be higher, pushing the maximum value higher, making
it less likely to be ranked highly.  The Count sort, on the other
hand, is entirely insensitive to the frequency with which a particular
value actually occurs.  Finially, the LogSum will actually increase in
this situation!

Insensitivity to this issue has another undesirable side effect.  In
particular, a given feature can reappear high on the list even after a
selection based on a value for this feature has been made.  The MinMax
sort avoids this since after the selection all the remaining species
would typically share at least one of the values for that feature,
placing that feature at the bottom of the list.


* Futures *

One of the biggest problems with the system as it currently stands is
the one sidedness of the user feedback to date.  As the principle user
I am, of course, happy with the system and find it intuitive to use.
Within the next month I hope to get the system into a form that I can
give it to some other people to try it out.

Currently values for features can only be sets of strings.  Other
representations for feature values need to be added.  Pursuant to that 
goal I think it would be a good idea to step back and go through a more 
careful design process from the ground up.  As part of this effort I 
would like to switch over from using C to C++.

While using the system, I have also been trying to develop a clear
model for a command line interface for the program.  The principle
goal for this interface would be to port the system to both the
UNIX and IBM PC platforms.  These ports are important if I hope
to get other people working with the database and hopefully
extending it.

Finally, I would like to do some more work with the decision system.
The insight I have gained in analyzing the difference between the
different sorting methods should help me to develop an even better
method.  I believe that there must be a way to improve the LogSum method,
in particular, since it is the method with the closest ties to
information theory.


* Bibliography *

Arora, David (1986) Mushrooms Demystified.  Ten Speed Press; Berkeley, Ca.

Jenkins, David T. (1986) Amanita of North America. Mad River Press; Eureka, Ca.

Lincoff, Gary (1981) The Audubon Society Field Guide to North American
  Mushrooms. New York: Alfred Knopf.

Largent, David L. (1986) How to Identify Mushrooms to Genus I: Macroscopic
  Features. Mad River Press; Eureka, Ca.

Thiers, H.D. (1982-) The Agaricales (Gilled Fungi) of California: Agaricaceae,
 Amanitaceae, Cantharellaceae, Gomphidiaceae, and Hygrophoraceae.  Mad River
 Press; Eureka, Ca.
 ---------------------        _________
     Nathan Wilson           <_________>
nathan@taurus.apple.com          |_|         It is no dream!
   velosa@apple.com             /___\     Matsutake are growing
  nathan@cse.ucsc.edu            | |         On the belly of the mountain.
   AppleLink: velosa             | |                        -Shigetaka
                                 \_/ *83--


