Subject: Using computers to study mushrooms (2 of 2)

From: [email-masked] (Nathan J. Wilson)
Date: 3 Sep 1993 20:35:41 GMT

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           <_________>
[email-masked]          |_|         It is no dream!
   [email-masked]             /___\     Matsutake are growing
  [email-masked]            | |         On the belly of the mountain.
   AppleLink: velosa             | |                        -Shigetaka
                                 \_/ *83--