BACKGROUND
bio-diversity researchers study how the abundance and geographic distribution of organisms change in response to varying environmental conditions.
these studies rely heavily on observations of species acquired in the field and spanning many different geographical regions.
observations include data such as species presence/absence, counts of individuals, gender, life history stages , behaviour , time and location where observations were made, photographs, audio recordings and environmental conditions where the observations occurred.
species richness  and abundance  data are crucial for understanding processes that govern the distribution of species across space.
quantifying beta-diversity  and endemism  is critical for conservation biology  <cit> .
this discipline includes developing conservation schemes  <cit> , such as identifying biological 'hotspots', which are areas with high levels of species richness.
monitoring abundance is critical for assessing species health, because population losses threaten species diversity  <cit> , and for understanding sensitivity of population size to environmental factors  <cit> , including climate change  <cit> .
all these issues are currently hotly debated in the ecology literature.
see for example ostling  <dig> describing controversy around the neutral theory, hubbell  <dig> vs. mcgill hadly and maurer  <dig>  and graves and rahbek  <dig>  more temporal and spatially explicit data on species and population sizes will inform these debates.
traditionally, bio-diversity researchers have relied on their own collections of observation data to carry out their analyses, and such collections are at inherently limited temporal and spatial resolution.
better informed analysis can be performed on larger quantities of data gathered across many different geographical regions.
one way to achieve larger datasets for scientific analyses is to enlist the help of the public, amateurs and volunteers, in gathering species observation data.
the possible numbers of participants covering a wide geographic area in a short period of time is exemplified by the christmas bird count , which in its 105th event of  <dig> –  <dig> had  <dig>  participants conduct  <dig>  counts, recording almost  <dig> million birds over a period of a few weeks in canada, the united states, latin america and the caribbean  <cit> .
volunteers defray otherwise prohibitive costs of surveys  <cit>  and generously donate travel expenses  <cit> .
researchers, however, are wary of using amateur observations as the basis of their studies, in part because of concerns over accuracy of species identifications  <cit> .
one way to increase accuracy is to provide tools that are intuitive to use, which limit the number of mistakes an amateur can make, allow a user to enter evidence for a reviewer to later verify the observation, and provide an overall pleasant user experience  <cit> .
potential improvements to the process
traditional paper-based field guides and dichotomous taxonomic trees typically arrange species according to morphological commonalities, reflecting their phylogenetic relationships, rather than their geographic distribution or abundance.
in practical use, species found in the same location may be morphologically different and only distantly related.
consequently, morphologically organized guides require readers to access many parts of the book.
also, the number of species found in any one area is small relative to the number of species in a typical regional field guide.
the number of species and size of an area are in fact related in a log/log fashion  <cit> .
local field guides are taxonomic keys limited to only the species found in one area.
unfortunately, local guides are expensive and time consuming to create.
and they may not contain newly arrived or rare species.
the impact of abundance on species identification was examined in  <cit> .
building on the existing idea of interactive keys, we constructed a tool, ecopod  <cit> , that attempts to combine the completeness of general field guides with advantages of their local counterparts.
ideally such a tool would reduce the number of questions the user needs to answer for identifying common or previously observed species, while not penalizing identification of rare species by increasing the number of questions required to id them.
ecopod
ecopod has an intuitive user interface and includes features such as an audit trail that allows users to document all decisions with supporting materials, like audio recordings, notes, or photographs.
users can also indicate whether they are certain about their decision on the state of each character.
experts can use this auxiliary information later while reviewing identifications.
such quality checks can then improve confidence in an evolving dataset of observations.
ecopod presents the operator with a list of characters.
as the user specifies the respective states, the remaining taxa are narrowed down and listed.
the most discriminating characters are displayed at the top of the list at all times , similar to algorithms introduced by  <cit>  and also found in desktop species identification programs delta  <cit>  and  <cit> .
we have previously described ecopod's user interface in detail  <cit> .
an exploration of the character ordering is the focus of the work we present here.
the current system  conceptually begins with a matrix view of the taxonomy.
from this matrix the system uses information gain theory to derive a decision tree that controls the user interface and is equivalent to a dichotomous key.
for illustration, table  <dig> shows a highly simplified matrix of four birds, a murres, egret, gray jay, and turkey.
from this matrix we can construct multiple decision trees that could guide the computing device's interface.
figure  <dig> shows two possible trees.
using the left tree, the device would first ask the user whether the specimen being observed had a long bill.
if the bird in question indeed exhibited a long bill, the identification would be accomplished with a single question.
the specimen would be an egret.
however, if we assume that all species of birds are equally likely to occur in the observer's locale, then on average more questions would be required.
for example, both gray jay and turkey would need answers to three questions before an identification could be produced.
the average number of questions in the left tree is / <dig> =  <dig> .
the right hand tree in contrast, produces an average of  <dig> questions for identifications.
under the assumption of uniform species distribution, the right side tree is therefore optimal.
osborne  <cit>  additionally showed that if the operator of a key has some non-zero probability of answering questions incorrectly, then short keys tend to minimize erroneous identifications.
currently, ecopod always uses that uniform distribution decision tree on the right of figure  <dig>  while for this example ecopod would never do as well as requiring just a single question to produce an identification, it would perform well on average across the species.
the work we present in the remainder of this writing removes the assumption that all species of a census are equally likely to be observed.
if, for the above example, the egret population were overwhelmingly larger than that of the other three species in the geographic area where the tool is to support identifications, ecopod would be well advised to choose the left-side decision tree of figure  <dig>  how would the device 'know' about such supporting information?
our vision is for ecopod to be carried into a field station that makes statistics of prior local species observations available through a wireless network.
the portable identification device would absorb these statistics and calibrate its operation such that it would ask users as few questions as possible while they are identifying organisms in the surrounding area.
short of such a vision, historic observation data might be downloaded from the web prior to commencing field work.
to this end we developed an algorithm that produces decision trees from a taxonomic matrix based on frequency of prior observations.
to test this algorithm we acquired observations of  <dig> bird species from stanford university's  <dig> acre jasper ridge biological preserve .
the observations were point counts across the preserve.
the counts were repeated multiple times per year between  <dig> and  <dig>  the data included a total of  <dig> observations with  <dig>  birds counted.
intuitively, the use of historical information should speed up identification of previously observed organisms.
but a number of factors need to be explored to ensure success.
first, observations are costly.
beyond their original collection, the data must be curated over many years.
associated computers must be maintained.
a realization of the idea thus does not come free of charge, and we must be sure of its value.
second, observations of rare species are valuable and should not be adversely impacted by the new technology.
summary of contributions
we answer the following questions:
• efficacy of species abundance data: how much faster are identifications of common species vs. rare species when using historical abundance data?
does the inherent bias towards common species increase the number of questions to identify rare species over a paper-based dichotomous taxonomic key?
• required amount of historical data: how many years  of observations are necessary to gain a significant benefit?
does performance depend on a particular year of the observation?
• unobserved species: computationally, what probability weight should be assigned to a species that has never been observed at the location before ?
known smoothing algorithms redistribute probability mass, but their efficacy depends on the corpus of data.
does the choice of two smoothing algorithms, laplace and good-turing, influence the number of questions to detect previously observed as well as  <dig> never before observed species?
• taxonomic key properties: how strongly does the matrix density, or the identification key author's choice of character states impact algorithm performance?
how does the difference in the minimum number of questions to identify various species influence algorithm performance?
we answer these questions via a computer simulation that exhaustively 'identified' all of the actual jasper ridge bird observations using our algorithm with a variety of parameter settings.
the measure of performance for each setting of the algorithm is the number of questions required to identify a species being examined.
methods
we begin with a description of the experimental setup, after which we introduce the algorithm that computes the optimal decision tree from the historical data.
we then present two alternatives for processing previously unobserved species.
these algorithms are well known in the literature, but they have been applied primarily in sub-disciplines of computer science.
their application to species identification is new.
in the results section we present the statistical analyses that answer the above research questions.
apparatus
each run of the simulation identified one focal species.
one block of runs identified  <dig> birds that were previously observed in jasper ridge.
some blocks additionally identified  <dig> random birds that have not been seen at the preserve.
one of two simulation parameters was varied across blocks of runs:  the amount and age of historical observations, and  a choice of smoothing algorithm for modelling previously unobserved birds.
for each block of runs the chosen amount of historic bird count observation data was fed to the observation probability distribution computation .
this computation produced a probability for each of the observed birds, plus a single probability that was used for any previously unobserved species.
experimental manipulations controlled how much historic data was provided to the computation.
we varied this information across  <dig> blocks of runs.
six blocks each provided one year's worth of observations  to the algorithm.
other blocks of runs utilized two years of data per run , three years , four years of data , five years ; and one block finally provided six years of observations to the computation .
that is, each of  <dig> species observed at jasper ridge preserve at least once between  <dig> and  <dig> were identified  <dig> times, each run being driven by a different set of historical observations.
in a separate computation we created a nearly perfectly balanced question tree.
this process did not consider any historic data, and we call this configuration the static condition.
this condition was our base line against which we compared the biased conditions that did use historical data when constructing the decision tree.
the right-most circle in figure  <dig> processed all the runs within a block.
this module used the probabilities and the character matrix database at the top of the figure to decide which sequence of characters to ask about.
acting as an oracle, the module at the bottom of the figure provided the proper state for any requested character.
this module – one could think of it as a second computer – thus took the role of what in real deployment would be the human operator.
an important difference between this module and a human being is that the oracle module never erred when providing the state of a character.
note that in ecopod's user interface we included a number of mechanisms that soften this assumption of correctness for human users.
the system alerts the human operator of intra-species variance, and users can rate their confidence in the character states they provide  <cit> .
once the focal species of a run was identified, the required number of character questions was noted and the next focal species was processed.
note that this procedure does not simply measure the length of the shortest path from root to correct species.
the experiment also measures how many questions the machine asks to find that shortest path.
observation data consisted of six years of an ongoing repeated bird point count study at jbrp.
birds were observed approximately  <dig> times a month by several expert birders following a strict observation protocol.
observations were conducted at  <dig> sites within jrbp, and data from all of these sites were pooled so that historical observations reflect species abundances for the whole preserve.
we make the implicit assumption that the count of a species reflects its actual abundance, and we use the terms interchangeably.
the bird species identification matrix was for >  <dig> western north american birds all of which were digitized by hand from the guide's paper format  <cit> .
creating the dichotomous tree
as sketched in the background section, two considerations enter the construction of the dichotomous tree from the matrix.
the first is whether we assume uniform distribution of observations over all species, or whether we figure local history of actual observations into the construction of the tree.
the second consideration is how to account for species that have not been observed in the geographic area before, but might be sighted in future field trips to the same region.
we discuss both aspects here.
underlying the solutions to both issues is the probability of observing a given species in the future.
computing probabilities
given the total of  <dig> observations of this example, the maximum likelihood estimate for murres would be 4/ <dig> = .
<dig>  that of gray jay would be 3/ <dig> = .
<dig>  and so on.
the next section describes how these probabilities are used to construct dichotomous trees used in the identification process.
information gain maximization
the computation of dichotomous trees is a well-studied problem in artificial intelligence, where the construct is known as decision trees  <cit> .
these constructs are a generalization of biology's dichotomous trees.
the calculation of decision trees involves the notion of information gain.
at each level of the tree, the algorithm chooses the character that maximizes the information gained .
maximizing information gain under a uniform distribution assumption in practice results in balancing the tree, minimizing its average depth.
intuitively, the dichotomous tree is constructed top down from its root, which is the node at the top.
that node has no parent nodes.
the root node is created and is associated with one character.
this character is chosen based on species probability.
under a uniform distribution assumption the character that eliminates close to 1/ <dig> of the remaining rows is chosen.
in table  <dig> we see that 1/ <dig> of the birds are white, while the other half are gray.
knowing the color therefore eliminates 1/ <dig> of the rows.
asking about bill length would instead partition the space at a ratio of  <dig> to  <dig>  color would therefore be used as the root node.
using mle instead of uniform distribution, egrets are about three times more likely than the other entries in the matrix.
for this case bill length would move higher in the list of good characters to ask early.
information gain theory formalizes this use of probabilities for the construction of optimal dichotomous trees.
please see additional file  <dig> for further information.
in additional file  <dig>  we work through the mathematical details of character selection in terms of this running example.
once the root node has been associated with the 'best' character, a child  node is created for each state that the character can take on.
for each of these child nodes the process of associating a character is repeated as per the initial root node.
the process is repeated until all terminal  nodes are species.
expressed as an algorithm this procedure runs as follows:
<dig>  begin at the root node.
<dig>  for each node, determine the character with the highest information gain that is not used in an ancestor node.
<dig>  add a child node for each possible state of that character.
<dig>  for each of these new nodes, attach a list of species that follow down the tree to that node.
<dig>  mark any of the species that are now uniquely identified as leaf nodes.
<dig>  go back to step two if not all terminal nodes are individual species.
note that the use of information gain for constructing the question tree is elegant in that it only relies on the probabilities that are derived from observations.
these probabilities in turn reflect very complex underlying influences, like local weather patterns, the prevalence of predators, and availability of food sources.
it would be very difficult to model all these factors explicitly.
on the other hand, whether using a uniform distribution assumption or not, this algorithm takes into account only the species that have been observed in an area.
of course, there is also a chance that a previously unseen species invades or just was not observed before by chance.
the next section introduces two alternatives from computer science practice that could be applied to address this shortcoming.
we will later examine which of these two is the better choice.
probability of unseen species
using maximum likelihood estimates would result in a probability of zero for previously unseen species .
the system would thus never enable successful identification of a species that is invading a new habitat, or was too rare to have been previously observed.
the process of modelling the probability of unseen species is an example of 'smoothing,' because the probability mass needs to be 'smoothed,' or spread among seen and unseen events.
probability mass is the discrete-variable equivalent to the integral of the probability density function for continuous random variables.
literature addressing this issue is found, for example, in the area of natural language processing  <cit> , where computer programs attempt to predict the co-occurrence of words in speech or written text from previous observations.
the reason for the existence of many smoothing algorithms is that their efficiency depends on the corpus that is being manipulated.
the question is therefore whether the distribution of species observations is similar enough to the occurrence of words in natural language that the same smoothing algorithms can be applied in both areas.
the two techniques are known as laplace, and good-turing smoothing.
laplace  smoothing
laplace smoothing increases each observed frequency by  <dig>  therefore, species that have never been seen before are now assumed to have been observed exactly once.
species that have been observed r times in the past are now assumed to have been seen r+ <dig> times.
therefore, probabilities are computed as follows:
p=+1number of observations+number of species found
or concisely:
p=r+1∑r+∑rnr
where r is the historically observed abundance of species x, and nr is the number of species with abundance r.
the laplace method has the advantage of being straightforward to describe and implement.
however, in natural language processing, laplace smoothing has been found to overestimate the probability of unseen events.
this overestimation problem of laplace smoothing has led to the development of alternatives.
one family of algorithms from the literature is known as good-turing smoothing.
in the following paragraphs we very briefly summarize the underlying concept in terms of species identification.
for details please see additional file  <dig> and  <cit> , where the procedures are discussed in the context of natural language processing.
good-turing smoothing
like laplace, good-turing smoothing modifies observed abundances r, discounting them by some amount.
however, the method takes a more subtle approach.
intuitively, the technique notes how abundance observations change across species.
a linear regression then fits a function through these variations of abundance.
using this function instead of the actual abundances to compute probabilities results in very abundant species contributing a bit less to the probability than they normally would.
this discounted probability mass is effectively assigned to the never-seen species.
this approach is a more controlled redistribution of probability than the crude add-1-everywhere laplace approach.
however, the algorithm is also more complex.
the steps are as follows:
<dig>  rank the frequency of observations: count how many species were observed exactly once and note this quantity as n <dig>  count how many species were observed twice and note that quantity as n <dig>  and so on.
<dig>  once ranking is complete, use local averaging to create non-zero values for any nr that are zero .
<dig>  fit linear regression to the resulting ranked list.
<dig>  compute the probability of seeing an unobserved species as n1n, with n being the total number of observations.
we describe the details of this process in additional file  <dig>
summary of probability considerations
use of historical observations of species abundance to calibrate the identification process requires consideration of unseen species.
we described assigning probability mass to previously unobserved species using two existing smoothing techniques that are popular in natural language processing.
the question is whether the good-turing algorithm needs to be used for a dataset like the jasper ridge bird counts when computing probabilities for the dichotomous key, or whether the simpler laplace method suffices.
we applied both algorithms to our experimental setup and measured the resulting number of questions for both seen and unseen species.
RESULTS
we now present the data analyses of our experiment separately for each of the research questions we introduced earlier.
for use in some of the analyses we computed the mean of all bird abundances over the six years of observations.
we call the result meanabundance.
we use the notation yyyy_n to indicate an observation year yyyy with n previous years' of data included.
for example, 2005_ <dig> means three years' of observations, the most recent being 2005:  <dig>   <dig>  and  <dig>  all historical computations used laplace smoothing.
the table inset of figure  <dig> shows the quartile ranges for abundances during each year.
for example, during  <dig> the rarest 25% of jasper ridge birds were not seen.
during  <dig> the rarest 25% were seen either not at all, or once.
the lowest row shows the sum of all counts during the respective year.
the 'mean' column shows quartile cut-offs for the mean abundance across all six years.
we call these cut-offs the meanquartiles.
the first research question we address is whether historical abundance observations provide any benefit at all for minimizing the average number of questions asked to identify a species.
the inclusion of such information in the probability computations is contrasted with the base case of the uniform distribution assumption .
does observation history add significant benefit?
the nature of the biased algorithm would have us expect a strong impact of bird observation abundance on performance.
this built-in dependency is illustrated in figure  <dig> where abundance is plotted against the number of questions the biased algorithm settings required when provided with observation data from  <dig>  we see that low abundance birds sometimes require very few, but also up to  <dig> questions to identify.
high abundance birds consistently require lower numbers of questions to id.
for formal verification we used the mean abundance over six years to partition the birds into quartiles, from rare  to common .
a repeated measure anova comparing the number of questions required when the algorithm was run with observations from  <dig>   <dig>  and 2005_ <dig> was conducted, with meanquartile as a between-subject factor.
the result verified the expected interaction between runs and quartiles .
in addition, the highly significant regression equation predicting the number of questions from log abundance is included as further verification at the bottom of figure  <dig>  given this predictable sensitivity of the algorithm to abundance we conducted all subsequent tests separately by quartiles.
each line shows the mean number of questions required to identify one meanquartile of the birds when the algorithm was provided with observations from different years as indicated along the abscissa.
the left most set of four  measurements corresponds to the static condition when no observations are used for the decision tree construction.
the five vertical sets of data points on the right show results when the algorithm was given access to several years' worth of observations .
the answers to several of the research questions reduce to examining significance of differences between portions of figure 6:
• does abundance information help?
↔ is the difference between the four static data points and the other data points significant?
• does it matter which year is used for observations?
↔ are the differences between vertical sets  <dig> through  <dig> significant?
• does it matter how many years of observations are used?
↔ are the differences between sets  <dig> and  <dig> significant?
• are rare birds unduly disadvantaged?
↔ for quartile  <dig> only, are any of the differences between static and the remaining measurements significant?
we performed repeated measure anovas separately for each meanquartile set of species.
the independent factor was the amount of information provided to the algorithm; its levels correspond to the abscissa labels of figure  <dig>  the dependent variable was the mean number of questions required for identification.
in each case we performed contrasts that compared each result for biased algorithm settings against static.
for meanquartiles 1– <dig> no differences were significant.
for meanquartile  <dig> the overall anova measured f <dig> , <dig>  =  <dig> ; p < .
<dig> .
table  <dig> shows results of the contrasts, and means with standard deviations.
the top portion of table  <dig> contrasts the single-year runs against static.
the lower portion shows the comparisons between static and the multi-year observations results .
additionally, repeated contrasts were performed to compare all horizontally neighbouring results in figure  <dig> .
very few differences were significant.
these were:
• meanquartile 1-two years vs. three years: f <dig>  =  <dig> , p < .
<dig>
• meanquartile 2-
◦  <dig> vs. 2005: f <dig>  =  <dig> ; p < .
<dig>
◦ two years vs. three years: f <dig>  =  <dig> ; p < .
<dig>
note that the differences in the mean number of questions for these measurements are very small: the difference in mean for the significant meanquartile  <dig> contrast was .
<dig> questions.
the differences between the meanquartile  <dig> results were  <dig>  and  <dig> , respectively.
while anova works well for the above analyses, its disadvantage in this situation is that a single quartile partitioning, namely meanquartile, must be used across all analyses.
recall that the meanquartile cut-offs are based on the counts averaged across six years.
in truth, the quartile cut-offs are different each year.
we concluded above that only the 4th quartile, most abundant species afford an advantage over static under the biased settings.
in order to verify that this conclusion is valid for each of the years' quartile cut-offs, we repeated the anova six times, each time using the cut-offs from a different year.
in each case the 4th quartile was clearly where the biased settings outperformed static.
in several cases the biased advantage extended into the 2nd and 3rd quartiles as well.
we conclude that the algorithm indeed reduces the number of questions required for identification, that this advantage only accrues for common species, and that neither the number of observation years used, nor the choice of years between  <dig> and  <dig> impacts this result for the jasper ridge preserve bird counts of that time period.
penalty for rare species
the lack of significant differences between static and the biased runs for 1st quartile species answers the question about whether the biased methods unduly handicap identification of rare species: the algorithm does no worse for rare species than the standard approach.
figure  <dig> adds a visual for details under three scenarios.
the figure shows how many more, or fewer questions the seven biased settings 2000– <dig>  2005_ <dig> require compared to static.
since only one bar can feasibly be displayed for each species , we show three scenarios.
the worst case scenario selects for each species the worst performing of the seven biased settings for the comparison against static.
the best case scenario  instead chooses the best performer for each species, and the bottom panel shows results when static is each time compared to the mean of the questions required by the seven biased settings.
each bar provides the comparison information for one of the  <dig> jasper ridge bird species.
a positive bar indicates that the biased settings required the indicated number of questions beyond static for the respective species.
a negative bar indicates that the biased settings performed better by the indicated number of questions.
that is, negative bars are 'good.'
for example, in the best case only very few species would require more questions than static as there are few positive bars.
note that in the bottom panel many bars are negative for common species, consistent with anova results of previous sections.
intrinsic ease of identification
we examined two aspects of the data to gain partial insight into how intrinsic ease of identification impacts the number of questions that need to be asked towards identification of a species.
the first data aspect we examined is the matrix density, the per species number of non-empty entries in the bird identification matrix.
the second is the minimal number of questions the algorithm could possibly ask to identify each bird.
sensitivity to matrix density
species identification matrices will differ across both species and matrix authors.
one such difference is the number of characters that are specified for each taxon .
in our north american birds matrix the average number of non-empty cells per row was  <dig>  with a range of  <dig> to  <dig> cells.
in order to obtain a rising measure of simplicity for each bird we divided this count into  <dig>  for example, a bird for which our matrix specified states for  <dig> characters received a simplicity score of 100/ <dig> =  <dig> .
to test whether the simplicity measure impacts the biased algorithm runs we computed a repeated measure anova for the eleven biased settings 2000– <dig>  2005_2– <dig>  with simplicity as covariant.
no interaction was detected between the covariant and the number of questions required for the bias settings.
we conclude that at least for this north-american bird matrix the algorithms are not sensitive to the row densities.
sensitivity to ease of identification
in order to extract the minimal, best case number of questions that the biased algorithm settings could elicit for any given bird we computed a minnumqs value for each species.
this value was obtained by in turn artificially setting the probability of each bird high, even if its abundance was low.
we then noted the number of questions that the algorithm generated in turn for each such artificially high-biased species.
for meanquartiles  <dig> and  <dig> strong correlations were in evidence between minnumqs and each of the eleven biased settings.
the pearson coefficient for all these correlations was close to .
<dig>  p < .
<dig>  for meanquartiles  <dig> and  <dig> no significant correlations were found.
however, the same correlation pattern was found to hold between minnumqs and static.
the relative performance of static and the biased settings was thus unaffected by minnumqs.
we verified this conclusion by normalizing all our measured results to neutralize the impact of minnumqs.
for each species we divided the number of questions generated under static and each of the biased settings by that species' minnumqs.
we then repeated all the previously described analyses for these normalized results.
all the conclusions remained unaltered.
we conclude that the intrinsic differences of how difficult various species are to identify does not in practice influence how much better or worse the biased methods perform relative to static.
does the smoothing algorithm impact performance?
our implementations of both laplace and simple good-turing  smoothing allowed us to compare performance under both algorithms.
we computed abundance probabilities for each of the matrix species, both seen and previously unobserved at jasper ridge.
for all of the  <dig> previously observed bird species, and  <dig> randomly selected never locally spotted birds we computed the number of questions required for identification.
we performed a repeated measures anova over the number of questions required for both laplace and sgt, for both one year's and five year's worth of observations.
table  <dig> shows results for each abundance quartile separately.
each cell is subdivided into four quadrants, each one holding a result for one quartile.
italicized values are significant at p < .
<dig>  other values are significant at p < .
<dig>  the left portion of table  <dig> shows the per-quartile mean of the number of required questions for each of the smoothing algorithms and amount of observation data.
the f values are results of planned contrasts.
non-significant comparisons are marked with 'ns.'
f values: p < .
<dig> ,
note that during  <dig>   <dig> of the  <dig> species that are sometimes seen at jasper ridge were not observed.
throughout the 2001– <dig> period against which we compare, only one species was not seen.
that is, the 2005_ <dig> settings contain more rare birds than the 2005_ <dig> settings.
from table  <dig> it is evident that whenever simple good-turing smoothing is applied to the identification of unseen species the results are worse than when laplace smoothing is used.
for example, comparing the one-year laplace with one-year sgt, first quartile birds required  <dig>  questions using laplace, but  <dig>  questions using sgt .
when abundant species are being identified, the difference between laplace and sgt tends to disappear.
the laplace one-year/sgt-six-year differences are not significant for any quartile.
we explored the impact on rare species further by having the algorithm identify  <dig> birds that were never seen in jasper ridge, using the probabilities from the above experiment as biased settings: laplace 2005_ <dig>  laplace 2005_ <dig>  sgt 2005_ <dig>  and sgt 2005_ <dig>  that is, the probabilities that guided the decision tree construction were computed from the abundances of observed birds, but the  <dig> identifications always had to rely on the probability that the smoothing algorithms set aside for never seen species.
the resulting number of required questions  were, respectively,  <dig>  ±  <dig> ,  <dig>  ±  <dig> ,  <dig>  ±  <dig> , and  <dig>  ±  <dig> .
the  <dig> species identified for all four runs were each time randomly selected from among the roughly  <dig> species that were available in our key but had not been seen at jasper ridge.
a oneway anova was significant .
posthoc tests showed the only significant difference to be the additional  <dig>  questions required by six-year sgt when compared to the one-year laplace.
we conclude that for rare species the laplace approach is more reliable than simple good-turing.
discussion
above we reported results from three directions of exploration.
first, we investigated whether the number of observation years and the age of observations impacted the performance of the identification algorithm.
second, we examined how some characteristics of our identification key influenced the number of required questions.
and third, we compared two smoothing algorithms that impact how well the identifications work for previously unobserved species.
in the following sections we add some thoughts to these results.
for all our results we stress that they are based on one particular data set from the relatively protected confines of a biological preserve.
further studies will be required to evaluate the impact of high instability in the ecosystem on the algorithm's performance.
number and choice of observation years
results showed clearly that the inclusion of historical observations can significantly accelerate an identification tool.
however, this benefit only accrues once a sufficient amount of observation data is available.
that amount corresponds to the top 25% most abundant species.
in our data set this means that birds seen at least  <dig> times during a one-year period  benefit significantly from the biased approach.
those species are, of course, precisely the ones that are the most important to identify quickly, because they make up the bulk of census activities.
surprisingly, the number of years of accumulated data was not found to significantly impact the algorithm's performance.
a single year's observations performed at the same level as six year's worth of data.
also, no difference was found for which year's observations were used to run the algorithm.
this robustness is good news because observations are expensive to gather and maintain.
within limits, fluctuations in species populations do not greatly impact results.
looking at the modest magnitude of differences between static and the biased results one might wonder whether an advantage of one question saved per identification is worth the trouble.
notice, however, that this savings is multiplied across many sightings and all observers that participate in a census.
impact of the key's characteristics
fortunately, the broad mixture of bird matrix row densities in our digitized key did not impact the algorithms.
this result suggests that matrices by different authors and for diverse species focus will be amenable to our question generation algorithms.
this assumption remains to be tested with other matrices and species, as well as with other observation datasets.
we were surprised that the minimum number of questions  did not interfere with our results.
we had expected that we would need to normalize results to control for this species-specific quantity.
it turned out, however, that the correlations between minnumqs and the algorithm outputs were very uniform across all experimental conditions, and most importantly affected the static condition equally.
this result again is good news because it limits the amount of work required when introducing a new key into the identification system.
no analysis of minimum question requirements is needed.
probability smoothing techniques
results of the smoothing technique analysis clearly imply that for this dataset at least laplace smoothing is the algorithm of choice precisely because of its reputation for overestimating unseen observations.
our analysis confirms this tendency for excessive apportioning of probability mass to unseens, in that laplace clearly improves the performance for never sighted species.
given that laplace does not in turn hurt performance for observed species, the complications of simple good-turing seem unnecessary and laplace is the smoothing method to use.
limitations and future work
two sets of limitations and consequent need for additional work apply to the material discussed here.
one set concerns the data set and experiment, the other concerns more broadly our ecopod tool.
our study was based on bird observations in a preserve.
one might argue that populations could change more rapidly in less protected environments, or for organisms other than birds.
it would therefore be useful to repeat our experiment with historic data from other ecosystems.
more than one year's worth of observations might be required for those cases, even though we found that a single year sufficed.
similarly, it would be useful to repeat our experiments for a different identification key, preferably for species other than birds.
even though we did test for dependencies of the algorithm's efficiency on the key matrix's distribution of sparsity and on the ease of identification for each species, these tests were by necessity limited to the matrix we used.
repeat experiments with other keys would solidify our findings.
regarding ecopod and its efficacy, neither of our ease of identification measures captures the practical difficulties of observing particular characters in the field.
the measures do not, for example, take into account the difficulty of measuring the length of a squirrel's hair at  <dig> ft, as compared to evaluating the animal's colour.
factors like those would need to be captured explicitly, or through the device observing which characters users choose to specify during a number of field excursions.
ecopod users are not forced to answer questions in order.
they may choose to specify characters further down the question list early.
in an improved tool their choice would then calibrate the characters that are preferentially solicited of the user in the future.
similarly, environmental cues could be worked into the device's question sequencing.
for example, geographic location and season might be used in the biasing of probabilities that guide the decision tree construction.
a field worker's skill and experience could further be used to influence ecopod's behaviour.
for example, the device could ask some questions that are not strictly required for identification, but would help avoid misidentification when two species are similar.
such a question could, for instance, inquire about a character that should not be of a particular state, given the user's answers so far.
we next discuss related work and then present concluding remarks.
related work
the cross-disciplinary nature of this work induces several strands of prior work.
we cover bio-diversity and computer science related work separately.
biodiversity
observations by volunteers have resulted in datasets which have been invaluable to scientific research and conservation efforts.
about  <dig> scientific papers have been written on the  <dig> years of christmas bird count observations   <cit> , informing topics such as the range of bird species, spread of invasive species, change in population sizes and species extinctions.
the fourth of july butterfly count   <cit>  has provided crucial data on abundance and population dynamics of common species e.g.
<cit> , as well as on monarch butterfly range and migration, and changes in population size with continued destruction of over-wintering habitat  <cit> .
such data have informed conservation needs, such as the recent identification of areas with stewardship responsibility for maintaining high levels of species abundance e.g.
<cit> .
the case for citizen participation is also made in  <cit> .
in addition to mass-participation census taking, continuous species observations can now be collected into online databases.
one example, the calflora project, has collected over  <dig>  observations of more than  <dig>  plant species in california.
websites supporting the cbc and fjc have also created databases for users to contribute observations, including ebirds  <cit>  and butterflies i've seen  <cit>  respectively.
observations collected by a single conscientious individual have been invaluable for determining the impacts of global warming on birds  <cit> .
computer science related work
decision tree theory is explained in  <cit> , where basics of information gain theory are also covered.
techniques for probability smoothing are discussed in  <cit> .
a number of computer based species identification tools exist.
many tools are direct carry-overs of paper-based field guides to electronic versions   <cit> , surflens,  <cit> , and profbuilder  <cit> .
these systems track user browsing habits, navigation histories or site usage information respectively to make recommendations to the user or as a basis for collaborative filtering.
CONCLUSIONS
we showed the algorithms that underlie our ecopod, an in-field species identification tool.
in particular, we focused on showing how the tool minimizes the number of questions it asks of the user during the course of an identification.
the main source of our optimization is the frequency of past observations in the field where the device is deployed.
the more often a species was observed in the past, the more the tool favours solicitation of characters for that species over characters that are discriminants for less frequently sighted species.
we employed computer science algorithms, particularly from the theory of decision tree learning, and smoothing techniques that are popular in the area of natural language processing.
we tested the question generating algorithm on point count bird observations that were conducted at stanford's jasper ridge biological preserve.
the data covered the years 2000– <dig>  the algorithm generated questions driven by an identification key of north american birds, which we transcribed from its original book form to an online matrix.
we showed that the question generating algorithm is not sensitive to how many of the six years' worth of observation data are supplied as input.
even one year's worth of data made all the difference.
we also showed that, at least for our bird observations at the jasper ridge preserve, the age of the data  did not impact the algorithm's efficiency.
observations from  <dig> were just as valuable as observations from  <dig>
the key matrix's varying density of characters for each bird species had no impact on the algorithm.
neither did differences in the minimum number of required questions among the species affect the algorithm differently than it affected the baseline alternative.
that is, some species do require more questions, no matter how the question sequence is constructed.
finally, we showed that the use of laplace smoothing during the calculation of probabilities for the future observation of each species works well.
this result contrasts with findings in other areas, like natural language processing, where variants of the good-turing algorithm are preferred.
the inclusion of the public in the collection of observation data is crucial if convincingly large and geographically diverse data sets are to be accumulated quickly.
a challenge in the way of such public participation is quality assurance.
ecopod is one tool that attempts to enable convenient and reliable collection of observations.
authors' contributions
yyy wrote the ecopod implementation.
am and ap worked on the simulations and algorithms.
js worked on design features and all the biological aspects.
throughout the project, though, the four authors operated as a team, contributing to all aspects of the work.
all authors read and approved the final manuscript.
supplementary material
additional file 1
appendix 1: information gain.
this appendix describes the information gain algorithm in detail with examples.
click here for file
additional file 2
appendix 2: good-turing smoothing.
this appendix describes the good-turing smoothing algorithm in detail with examples.
click here for file
acknowledgements
we thank the volunteers and staff at the stanford jasper ridge biological preserve for the invaluable collection of bird counts.
this data is clearly the foundation of this work, and its collection required years of care.
we particularly mention trevor hébert, richard jeffers, peter latourrette, and phil leighton, who were intimately involved with the bird count project.
in addition, richard jeffers invested many hours helping us digitize the bird field guide.
this work required a bird specialist, and without his effort we could not have proceeded with our simulation and analysis.
we thank the following funding sources for their generous support: am, yy and ap were supported by national science foundation grant # <dig>  'sei: computing support for acquisition, collaborative curation, and dissemination in biodiversity research'.
js was supported by the department of biological sciences at stanford university as well as the ford motor company through the center for evolutionary studies at stanford university.

 bio-diversity researchers study how the abundance and geographic distribution of organisms change in response to varying environmental conditions. these studies rely heavily on observations of species acquired in the field and spanning many different geographical regions. observations include data such as species presence/absence, counts of individuals, gender, life history stages, behaviour, time and location where observations were made, photographs, audio recordings and environmental conditions where the observations occurred. species richness and abundance data are crucial for understanding processes that govern the distribution of species across space. quantifying beta-diversity and endemism is critical for conservation biology. this discipline includes developing conservation schemes, such as identifying biological'hotspots', which are areas with high levels of species richness. monitoring abundance is critical for assessing species health, because population losses threaten species diversity, and for understanding sensitivity of population size to environmental factors, including climate change. all these issues are currently hotly debated in the ecology literature. see for example ostling describing controversy around the neutral theory, hubbell vs. mcgill hadly and maurer and graves and rahbek more temporal and spatially explicit data on species and population sizes will inform these debates. traditionally, bio-diversity researchers have relied on their own collections of observation data to carry out their analyses, and such collections are at inherently limited temporal and spatial resolution. better informed analysis can be performed on larger quantities of data gathered across many different geographical regions. one way to achieve larger datasets for scientific analyses is to enlist the help of the public, amateurs and volunteers, in gathering species observation data. the possible numbers of participants covering a wide geographic area in a short period of time is exemplified by the christmas bird count, which in its 105th event of – had participants conduct counts, recording almost million birds over a period of a few weeks in canada, the united states, latin america and the caribbean. volunteers defray otherwise prohibitive costs of surveys and generously donate travel expenses. researchers, however, are wary of using amateur observations as the basis of their studies, in part because of concerns over accuracy of species identifications. one way to increase accuracy is to provide tools that are intuitive to use, which limit the number of mistakes an amateur can make, allow a user to enter evidence for a reviewer to later verify the observation, and provide an overall pleasant user experience. potential improvements to the process traditional paper-based field guides and dichotomous taxonomic trees typically arrange species according to morphological commonalities, reflecting their phylogenetic relationships, rather than their geographic distribution or abundance. in practical use, species found in the same location may be morphologically different and only distantly related. consequently, morphologically organized guides require readers to access many parts of the book. also, the number of species found in any one area is small relative to the number of species in a typical regional field guide. the number of species and size of an area are in fact related in a log/log fashion. local field guides are taxonomic keys limited to only the species found in one area. unfortunately, local guides are expensive and time consuming to create. and they may not contain newly arrived or rare species. the impact of abundance on species identification was examined in. building on the existing idea of interactive keys, we constructed a tool, ecopod, that attempts to combine the completeness of general field guides with advantages of their local counterparts. ideally such a tool would reduce the number of questions the user needs to answer for identifying common or previously observed species, while not penalizing identification of rare species by increasing the number of questions required to id them. ecopod ecopod has an intuitive user interface and includes features such as an audit trail that allows users to document all decisions with supporting materials, like audio recordings, notes, or photographs. users can also indicate whether they are certain about their decision on the state of each character. experts can use this auxiliary information later while reviewing identifications. such quality checks can then improve confidence in an evolving dataset of observations. ecopod presents the operator with a list of characters. as the user specifies the respective states, the remaining taxa are narrowed down and listed. the most discriminating characters are displayed at the top of the list at all times, similar to algorithms introduced by and also found in desktop species identification programs delta and. we have previously described ecopod's user interface in detail. an exploration of the character ordering is the focus of the work we present here. the current system conceptually begins with a matrix view of the taxonomy. from this matrix the system uses information gain theory to derive a decision tree that controls the user interface and is equivalent to a dichotomous key. for illustration, table shows a highly simplified matrix of four birds, a murres, egret, gray jay, and turkey. from this matrix we can construct multiple decision trees that could guide the computing device's interface. figure shows two possible trees. using the left tree, the device would first ask the user whether the specimen being observed had a long bill. if the bird in question indeed exhibited a long bill, the identification would be accomplished with a single question. the specimen would be an egret. however, if we assume that all species of birds are equally likely to occur in the observer's locale, then on average more questions would be required. for example, both gray jay and turkey would need answers to three questions before an identification could be produced. the average number of questions in the left tree is / =. the right hand tree in contrast, produces an average of questions for identifications. under the assumption of uniform species distribution, the right side tree is therefore optimal. osborne additionally showed that if the operator of a key has some non-zero probability of answering questions incorrectly, then short keys tend to minimize erroneous identifications. currently, ecopod always uses that uniform distribution decision tree on the right of figure while for this example ecopod would never do as well as requiring just a single question to produce an identification, it would perform well on average across the species. the work we present in the remainder of this writing removes the assumption that all species of a census are equally likely to be observed. if, for the above example, the egret population were overwhelmingly larger than that of the other three species in the geographic area where the tool is to support identifications, ecopod would be well advised to choose the left-side decision tree of figure how would the device'know' about such supporting information? our vision is for ecopod to be carried into a field station that makes statistics of prior local species observations available through a wireless network. the portable identification device would absorb these statistics and calibrate its operation such that it would ask users as few questions as possible while they are identifying organisms in the surrounding area. short of such a vision, historic observation data might be downloaded from the web prior to commencing field work. to this end we developed an algorithm that produces decision trees from a taxonomic matrix based on frequency of prior observations. to test this algorithm we acquired observations of bird species from stanford university's acre jasper ridge biological preserve. the observations were point counts across the preserve. the counts were repeated multiple times per year between and the data included a total of observations with birds counted. intuitively, the use of historical information should speed up identification of previously observed organisms. but a number of factors need to be explored to ensure success. first, observations are costly. beyond their original collection, the data must be curated over many years. associated computers must be maintained. a realization of the idea thus does not come free of charge, and we must be sure of its value. second, observations of rare species are valuable and should not be adversely impacted by the new technology. summary of contributions we answer the following questions: • efficacy of species abundance data: how much faster are identifications of common species vs. rare species when using historical abundance data? does the inherent bias towards common species increase the number of questions to identify rare species over a paper-based dichotomous taxonomic key? • required amount of historical data: how many years of observations are necessary to gain a significant benefit? does performance depend on a particular year of the observation? • unobserved species: computationally, what probability weight should be assigned to a species that has never been observed at the location before? known smoothing algorithms redistribute probability mass, but their efficacy depends on the corpus of data. does the choice of two smoothing algorithms, laplace and good-turing, influence the number of questions to detect previously observed as well as never before observed species? • taxonomic key properties: how strongly does the matrix density, or the identification key author's choice of character states impact algorithm performance? how does the difference in the minimum number of questions to identify various species influence algorithm performance? we answer these questions via a computer simulation that exhaustively'identified' all of the actual jasper ridge bird observations using our algorithm with a variety of parameter settings. the measure of performance for each setting of the algorithm is the number of questions required to identify a species being examined. methods we begin with a description of the experimental setup, after which we introduce the algorithm that computes the optimal decision tree from the historical data. we then present two alternatives for processing previously unobserved species. these algorithms are well known in the literature, but they have been applied primarily in sub-disciplines of computer science. their application to species identification is new. in the results section we present the statistical analyses that answer the above research questions. apparatus each run of the simulation identified one focal species. one block of runs identified birds that were previously observed in jasper ridge. some blocks additionally identified random birds that have not been seen at the preserve. one of two simulation parameters was varied across blocks of runs: the amount and age of historical observations, and a choice of smoothing algorithm for modelling previously unobserved birds. for each block of runs the chosen amount of historic bird count observation data was fed to the observation probability distribution computation. this computation produced a probability for each of the observed birds, plus a single probability that was used for any previously unobserved species. experimental manipulations controlled how much historic data was provided to the computation. we varied this information across blocks of runs. six blocks each provided one year's worth of observations to the algorithm. other blocks of runs utilized two years of data per run, three years, four years of data, five years; and one block finally provided six years of observations to the computation. that is, each of species observed at jasper ridge preserve at least once between and were identified times, each run being driven by a different set of historical observations. in a separate computation we created a nearly perfectly balanced question tree. this process did not consider any historic data, and we call this configuration the static condition. this condition was our base line against which we compared the biased conditions that did use historical data when constructing the decision tree. the right-most circle in figure processed all the runs within a block. this module used the probabilities and the character matrix database at the top of the figure to decide which sequence of characters to ask about. acting as an oracle, the module at the bottom of the figure provided the proper state for any requested character. this module – one could think of it as a second computer – thus took the role of what in real deployment would be the human operator. an important difference between this module and a human being is that the oracle module never erred when providing the state of a character. note that in ecopod's user interface we included a number of mechanisms that soften this assumption of correctness for human users. the system alerts the human operator of intra-species variance, and users can rate their confidence in the character states they provide. once the focal species of a run was identified, the required number of character questions was noted and the next focal species was processed. note that this procedure does not simply measure the length of the shortest path from root to correct species. the experiment also measures how many questions the machine asks to find that shortest path. observation data consisted of six years of an ongoing repeated bird point count study at jbrp. birds were observed approximately times a month by several expert birders following a strict observation protocol. observations were conducted at sites within jrbp, and data from all of these sites were pooled so that historical observations reflect species abundances for the whole preserve. we make the implicit assumption that the count of a species reflects its actual abundance, and we use the terms interchangeably. the bird species identification matrix was for > western north american birds all of which were digitized by hand from the guide's paper format. creating the dichotomous tree as sketched in the background section, two considerations enter the construction of the dichotomous tree from the matrix. the first is whether we assume uniform distribution of observations over all species, or whether we figure local history of actual observations into the construction of the tree. the second consideration is how to account for species that have not been observed in the geographic area before, but might be sighted in future field trips to the same region. we discuss both aspects here. underlying the solutions to both issues is the probability of observing a given species in the future. computing probabilities given the total of observations of this example, the maximum likelihood estimate for murres would be 4/ =. that of gray jay would be 3/ =. and so on. the next section describes how these probabilities are used to construct dichotomous trees used in the identification process. information gain maximization the computation of dichotomous trees is a well-studied problem in artificial intelligence, where the construct is known as decision trees. these constructs are a generalization of biology's dichotomous trees. the calculation of decision trees involves the notion of information gain. at each level of the tree, the algorithm chooses the character that maximizes the information gained. maximizing information gain under a uniform distribution assumption in practice results in balancing the tree, minimizing its average depth. intuitively, the dichotomous tree is constructed top down from its root, which is the node at the top. that node has no parent nodes. the root node is created and is associated with one character. this character is chosen based on species probability. under a uniform distribution assumption the character that eliminates close to 1/ of the remaining rows is chosen. in table we see that 1/ of the birds are white, while the other half are gray. knowing the color therefore eliminates 1/ of the rows. asking about bill length would instead partition the space at a ratio of to color would therefore be used as the root node. using mle instead of uniform distribution, egrets are about three times more likely than the other entries in the matrix. for this case bill length would move higher in the list of good characters to ask early. information gain theory formalizes this use of probabilities for the construction of optimal dichotomous trees. please see additional file for further information. in additional file we work through the mathematical details of character selection in terms of this running example. once the root node has been associated with the'best' character, a child node is created for each state that the character can take on. for each of these child nodes the process of associating a character is repeated as per the initial root node. the process is repeated until all terminal nodes are species. expressed as an algorithm this procedure runs as follows: begin at the root node. for each node, determine the character with the highest information gain that is not used in an ancestor node. add a child node for each possible state of that character. for each of these new nodes, attach a list of species that follow down the tree to that node. mark any of the species that are now uniquely identified as leaf nodes. go back to step two if not all terminal nodes are individual species. note that the use of information gain for constructing the question tree is elegant in that it only relies on the probabilities that are derived from observations. these probabilities in turn reflect very complex underlying influences, like local weather patterns, the prevalence of predators, and availability of food sources. it would be very difficult to model all these factors explicitly. on the other hand, whether using a uniform distribution assumption or not, this algorithm takes into account only the species that have been observed in an area. of course, there is also a chance that a previously unseen species invades or just was not observed before by chance. the next section introduces two alternatives from computer science practice that could be applied to address this shortcoming. we will later examine which of these two is the better choice. probability of unseen species using maximum likelihood estimates would result in a probability of zero for previously unseen species. the system would thus never enable successful identification of a species that is invading a new habitat, or was too rare to have been previously observed. the process of modelling the probability of unseen species is an example of'smoothing,' because the probability mass needs to be'smoothed,' or spread among seen and unseen events. probability mass is the discrete-variable equivalent to the integral of the probability density function for continuous random variables. literature addressing this issue is found, for example, in the area of natural language processing, where computer programs attempt to predict the co-occurrence of words in speech or written text from previous observations. the reason for the existence of many smoothing algorithms is that their efficiency depends on the corpus that is being manipulated. the question is therefore whether the distribution of species observations is similar enough to the occurrence of words in natural language that the same smoothing algorithms can be applied in both areas. the two techniques are known as laplace, and good-turing smoothing. laplace smoothing laplace smoothing increases each observed frequency by therefore, species that have never been seen before are now assumed to have been observed exactly once. species that have been observed r times in the past are now assumed to have been seen r+ times. therefore, probabilities are computed as follows: p=+1number of observations+number of species found or concisely: p=r+1∑r+∑rnr where r is the historically observed abundance of species x, and nr is the number of species with abundance r. the laplace method has the advantage of being straightforward to describe and implement. however, in natural language processing, laplace smoothing has been found to overestimate the probability of unseen events. this overestimation problem of laplace smoothing has led to the development of alternatives. one family of algorithms from the literature is known as good-turing smoothing. in the following paragraphs we very briefly summarize the underlying concept in terms of species identification. for details please see additional file and, where the procedures are discussed in the context of natural language processing. good-turing smoothing like laplace, good-turing smoothing modifies observed abundances r, discounting them by some amount. however, the method takes a more subtle approach. intuitively, the technique notes how abundance observations change across species. a linear regression then fits a function through these variations of abundance. using this function instead of the actual abundances to compute probabilities results in very abundant species contributing a bit less to the probability than they normally would. this discounted probability mass is effectively assigned to the never-seen species. this approach is a more controlled redistribution of probability than the crude add-1-everywhere laplace approach. however, the algorithm is also more complex. the steps are as follows: rank the frequency of observations: count how many species were observed exactly once and note this quantity as n count how many species were observed twice and note that quantity as n and so on. once ranking is complete, use local averaging to create non-zero values for any nr that are zero. fit linear regression to the resulting ranked list. compute the probability of seeing an unobserved species as n1n, with n being the total number of observations. we describe the details of this process in additional file summary of probability considerations use of historical observations of species abundance to calibrate the identification process requires consideration of unseen species. we described assigning probability mass to previously unobserved species using two existing smoothing techniques that are popular in natural language processing. the question is whether the good-turing algorithm needs to be used for a dataset like the jasper ridge bird counts when computing probabilities for the dichotomous key, or whether the simpler laplace method suffices. we applied both algorithms to our experimental setup and measured the resulting number of questions for both seen and unseen species.  we now present the data analyses of our experiment separately for each of the research questions we introduced earlier. for use in some of the analyses we computed the mean of all bird abundances over the six years of observations. we call the result meanabundance. we use the notation yyyy_n to indicate an observation year yyyy with n previous years' of data included. for example, 2005_ means three years' of observations, the most recent being 2005: and all historical computations used laplace smoothing. the table inset of figure shows the quartile ranges for abundances during each year. for example, during the rarest 25% of jasper ridge birds were not seen. during the rarest 25% were seen either not at all, or once. the lowest row shows the sum of all counts during the respective year. the'mean' column shows quartile cut-offs for the mean abundance across all six years. we call these cut-offs the meanquartiles. the first research question we address is whether historical abundance observations provide any benefit at all for minimizing the average number of questions asked to identify a species. the inclusion of such information in the probability computations is contrasted with the base case of the uniform distribution assumption. does observation history add significant benefit? the nature of the biased algorithm would have us expect a strong impact of bird observation abundance on performance. this built-in dependency is illustrated in figure where abundance is plotted against the number of questions the biased algorithm settings required when provided with observation data from we see that low abundance birds sometimes require very few, but also up to questions to identify. high abundance birds consistently require lower numbers of questions to id. for formal verification we used the mean abundance over six years to partition the birds into quartiles, from rare to common. a repeated measure anova comparing the number of questions required when the algorithm was run with observations from and 2005_ was conducted, with meanquartile as a between-subject factor. the result verified the expected interaction between runs and quartiles. in addition, the highly significant regression equation predicting the number of questions from log abundance is included as further verification at the bottom of figure given this predictable sensitivity of the algorithm to abundance we conducted all subsequent tests separately by quartiles. each line shows the mean number of questions required to identify one meanquartile of the birds when the algorithm was provided with observations from different years as indicated along the abscissa. the left most set of four measurements corresponds to the static condition when no observations are used for the decision tree construction. the five vertical sets of data points on the right show results when the algorithm was given access to several years' worth of observations. the answers to several of the research questions reduce to examining significance of differences between portions of figure 6: • does abundance information help? ↔ is the difference between the four static data points and the other data points significant? • does it matter which year is used for observations? ↔ are the differences between vertical sets through significant? • does it matter how many years of observations are used? ↔ are the differences between sets and significant? • are rare birds unduly disadvantaged? ↔ for quartile only, are any of the differences between static and the remaining measurements significant? we performed repeated measure anovas separately for each meanquartile set of species. the independent factor was the amount of information provided to the algorithm; its levels correspond to the abscissa labels of figure the dependent variable was the mean number of questions required for identification. in each case we performed contrasts that compared each result for biased algorithm settings against static. for meanquartiles 1– no differences were significant. for meanquartile the overall anova measured f, =; p <.. table shows results of the contrasts, and means with standard deviations. the top portion of table contrasts the single-year runs against static. the lower portion shows the comparisons between static and the multi-year observations results. additionally, repeated contrasts were performed to compare all horizontally neighbouring results in figure. very few differences were significant. these were: • meanquartile 1-two years vs. three years: f =, p <. • meanquartile 2- ◦ vs. 2005: f =; p <. ◦ two years vs. three years: f =; p <. note that the differences in the mean number of questions for these measurements are very small: the difference in mean for the significant meanquartile contrast was. questions. the differences between the meanquartile results were and, respectively. while anova works well for the above analyses, its disadvantage in this situation is that a single quartile partitioning, namely meanquartile, must be used across all analyses. recall that the meanquartile cut-offs are based on the counts averaged across six years. in truth, the quartile cut-offs are different each year. we concluded above that only the 4th quartile, most abundant species afford an advantage over static under the biased settings. in order to verify that this conclusion is valid for each of the years' quartile cut-offs, we repeated the anova six times, each time using the cut-offs from a different year. in each case the 4th quartile was clearly where the biased settings outperformed static. in several cases the biased advantage extended into the 2nd and 3rd quartiles as well. we conclude that the algorithm indeed reduces the number of questions required for identification, that this advantage only accrues for common species, and that neither the number of observation years used, nor the choice of years between and impacts this result for the jasper ridge preserve bird counts of that time period. penalty for rare species the lack of significant differences between static and the biased runs for 1st quartile species answers the question about whether the biased methods unduly handicap identification of rare species: the algorithm does no worse for rare species than the standard approach. figure adds a visual for details under three scenarios. the figure shows how many more, or fewer questions the seven biased settings 2000– 2005_ require compared to static. since only one bar can feasibly be displayed for each species, we show three scenarios. the worst case scenario selects for each species the worst performing of the seven biased settings for the comparison against static. the best case scenario instead chooses the best performer for each species, and the bottom panel shows results when static is each time compared to the mean of the questions required by the seven biased settings. each bar provides the comparison information for one of the jasper ridge bird species. a positive bar indicates that the biased settings required the indicated number of questions beyond static for the respective species. a negative bar indicates that the biased settings performed better by the indicated number of questions. that is, negative bars are'good.' for example, in the best case only very few species would require more questions than static as there are few positive bars. note that in the bottom panel many bars are negative for common species, consistent with anova results of previous sections. intrinsic ease of identification we examined two aspects of the data to gain partial insight into how intrinsic ease of identification impacts the number of questions that need to be asked towards identification of a species. the first data aspect we examined is the matrix density, the per species number of non-empty entries in the bird identification matrix. the second is the minimal number of questions the algorithm could possibly ask to identify each bird. sensitivity to matrix density species identification matrices will differ across both species and matrix authors. one such difference is the number of characters that are specified for each taxon. in our north american birds matrix the average number of non-empty cells per row was with a range of to cells. in order to obtain a rising measure of simplicity for each bird we divided this count into for example, a bird for which our matrix specified states for characters received a simplicity score of 100/ =. to test whether the simplicity measure impacts the biased algorithm runs we computed a repeated measure anova for the eleven biased settings 2000– 2005_2– with simplicity as covariant. no interaction was detected between the covariant and the number of questions required for the bias settings. we conclude that at least for this north-american bird matrix the algorithms are not sensitive to the row densities. sensitivity to ease of identification in order to extract the minimal, best case number of questions that the biased algorithm settings could elicit for any given bird we computed a minnumqs value for each species. this value was obtained by in turn artificially setting the probability of each bird high, even if its abundance was low. we then noted the number of questions that the algorithm generated in turn for each such artificially high-biased species. for meanquartiles and strong correlations were in evidence between minnumqs and each of the eleven biased settings. the pearson coefficient for all these correlations was close to. p <. for meanquartiles and no significant correlations were found. however, the same correlation pattern was found to hold between minnumqs and static. the relative performance of static and the biased settings was thus unaffected by minnumqs. we verified this conclusion by normalizing all our measured results to neutralize the impact of minnumqs. for each species we divided the number of questions generated under static and each of the biased settings by that species' minnumqs. we then repeated all the previously described analyses for these normalized results. all the conclusions remained unaltered. we conclude that the intrinsic differences of how difficult various species are to identify does not in practice influence how much better or worse the biased methods perform relative to static. does the smoothing algorithm impact performance? our implementations of both laplace and simple good-turing smoothing allowed us to compare performance under both algorithms. we computed abundance probabilities for each of the matrix species, both seen and previously unobserved at jasper ridge. for all of the previously observed bird species, and randomly selected never locally spotted birds we computed the number of questions required for identification. we performed a repeated measures anova over the number of questions required for both laplace and sgt, for both one year's and five year's worth of observations. table shows results for each abundance quartile separately. each cell is subdivided into four quadrants, each one holding a result for one quartile. italicized values are significant at p <. other values are significant at p <. the left portion of table shows the per-quartile mean of the number of required questions for each of the smoothing algorithms and amount of observation data. the f values are results of planned contrasts. non-significant comparisons are marked with'ns.' f values: p <., note that during of the species that are sometimes seen at jasper ridge were not observed. throughout the 2001– period against which we compare, only one species was not seen. that is, the 2005_ settings contain more rare birds than the 2005_ settings. from table it is evident that whenever simple good-turing smoothing is applied to the identification of unseen species the results are worse than when laplace smoothing is used. for example, comparing the one-year laplace with one-year sgt, first quartile birds required questions using laplace, but questions using sgt. when abundant species are being identified, the difference between laplace and sgt tends to disappear. the laplace one-year/sgt-six-year differences are not significant for any quartile. we explored the impact on rare species further by having the algorithm identify birds that were never seen in jasper ridge, using the probabilities from the above experiment as biased settings: laplace 2005_ laplace 2005_ sgt 2005_ and sgt 2005_ that is, the probabilities that guided the decision tree construction were computed from the abundances of observed birds, but the identifications always had to rely on the probability that the smoothing algorithms set aside for never seen species. the resulting number of required questions were, respectively, ±, ±, ±, and ±. the species identified for all four runs were each time randomly selected from among the roughly species that were available in our key but had not been seen at jasper ridge. a oneway anova was significant. posthoc tests showed the only significant difference to be the additional questions required by six-year sgt when compared to the one-year laplace. we conclude that for rare species the laplace approach is more reliable than simple good-turing. discussion above we reported results from three directions of exploration. first, we investigated whether the number of observation years and the age of observations impacted the performance of the identification algorithm. second, we examined how some characteristics of our identification key influenced the number of required questions. and third, we compared two smoothing algorithms that impact how well the identifications work for previously unobserved species. in the following sections we add some thoughts to these results. for all our results we stress that they are based on one particular data set from the relatively protected confines of a biological preserve. further studies will be required to evaluate the impact of high instability in the ecosystem on the algorithm's performance. number and choice of observation years results showed clearly that the inclusion of historical observations can significantly accelerate an identification tool. however, this benefit only accrues once a sufficient amount of observation data is available. that amount corresponds to the top 25% most abundant species. in our data set this means that birds seen at least times during a one-year period benefit significantly from the biased approach. those species are, of course, precisely the ones that are the most important to identify quickly, because they make up the bulk of census activities. surprisingly, the number of years of accumulated data was not found to significantly impact the algorithm's performance. a single year's observations performed at the same level as six year's worth of data. also, no difference was found for which year's observations were used to run the algorithm. this robustness is good news because observations are expensive to gather and maintain. within limits, fluctuations in species populations do not greatly impact results. looking at the modest magnitude of differences between static and the biased results one might wonder whether an advantage of one question saved per identification is worth the trouble. notice, however, that this savings is multiplied across many sightings and all observers that participate in a census. impact of the key's characteristics fortunately, the broad mixture of bird matrix row densities in our digitized key did not impact the algorithms. this result suggests that matrices by different authors and for diverse species focus will be amenable to our question generation algorithms. this assumption remains to be tested with other matrices and species, as well as with other observation datasets. we were surprised that the minimum number of questions did not interfere with our results. we had expected that we would need to normalize results to control for this species-specific quantity. it turned out, however, that the correlations between minnumqs and the algorithm outputs were very uniform across all experimental conditions, and most importantly affected the static condition equally. this result again is good news because it limits the amount of work required when introducing a new key into the identification system. no analysis of minimum question requirements is needed. probability smoothing techniques results of the smoothing technique analysis clearly imply that for this dataset at least laplace smoothing is the algorithm of choice precisely because of its reputation for overestimating unseen observations. our analysis confirms this tendency for excessive apportioning of probability mass to unseens, in that laplace clearly improves the performance for never sighted species. given that laplace does not in turn hurt performance for observed species, the complications of simple good-turing seem unnecessary and laplace is the smoothing method to use. limitations and future work two sets of limitations and consequent need for additional work apply to the material discussed here. one set concerns the data set and experiment, the other concerns more broadly our ecopod tool. our study was based on bird observations in a preserve. one might argue that populations could change more rapidly in less protected environments, or for organisms other than birds. it would therefore be useful to repeat our experiment with historic data from other ecosystems. more than one year's worth of observations might be required for those cases, even though we found that a single year sufficed. similarly, it would be useful to repeat our experiments for a different identification key, preferably for species other than birds. even though we did test for dependencies of the algorithm's efficiency on the key matrix's distribution of sparsity and on the ease of identification for each species, these tests were by necessity limited to the matrix we used. repeat experiments with other keys would solidify our findings. regarding ecopod and its efficacy, neither of our ease of identification measures captures the practical difficulties of observing particular characters in the field. the measures do not, for example, take into account the difficulty of measuring the length of a squirrel's hair at ft, as compared to evaluating the animal's colour. factors like those would need to be captured explicitly, or through the device observing which characters users choose to specify during a number of field excursions. ecopod users are not forced to answer questions in order. they may choose to specify characters further down the question list early. in an improved tool their choice would then calibrate the characters that are preferentially solicited of the user in the future. similarly, environmental cues could be worked into the device's question sequencing. for example, geographic location and season might be used in the biasing of probabilities that guide the decision tree construction. a field worker's skill and experience could further be used to influence ecopod's behaviour. for example, the device could ask some questions that are not strictly required for identification, but would help avoid misidentification when two species are similar. such a question could, for instance, inquire about a character that should not be of a particular state, given the user's answers so far. we next discuss related work and then present concluding remarks. related work the cross-disciplinary nature of this work induces several strands of prior work. we cover bio-diversity and computer science related work separately. biodiversity observations by volunteers have resulted in datasets which have been invaluable to scientific research and conservation efforts. about scientific papers have been written on the years of christmas bird count observations, informing topics such as the range of bird species, spread of invasive species, change in population sizes and species extinctions. the fourth of july butterfly count has provided crucial data on abundance and population dynamics of common species e.g., as well as on monarch butterfly range and migration, and changes in population size with continued destruction of over-wintering habitat. such data have informed conservation needs, such as the recent identification of areas with stewardship responsibility for maintaining high levels of species abundance e.g.. the case for citizen participation is also made in. in addition to mass-participation census taking, continuous species observations can now be collected into online databases. one example, the calflora project, has collected over observations of more than plant species in california. websites supporting the cbc and fjc have also created databases for users to contribute observations, including ebirds and butterflies i've seen respectively. observations collected by a single conscientious individual have been invaluable for determining the impacts of global warming on birds. computer science related work decision tree theory is explained in, where basics of information gain theory are also covered. techniques for probability smoothing are discussed in. a number of computer based species identification tools exist. many tools are direct carry-overs of paper-based field guides to electronic versions, surflens,, and profbuilder. these systems track user browsing habits, navigation histories or site usage information respectively to make recommendations to the user or as a basis for collaborative filtering.  we showed the algorithms that underlie our ecopod, an in-field species identification tool. in particular, we focused on showing how the tool minimizes the number of questions it asks of the user during the course of an identification. the main source of our optimization is the frequency of past observations in the field where the device is deployed. the more often a species was observed in the past, the more the tool favours solicitation of characters for that species over characters that are discriminants for less frequently sighted species. we employed computer science algorithms, particularly from the theory of decision tree learning, and smoothing techniques that are popular in the area of natural language processing. we tested the question generating algorithm on point count bird observations that were conducted at stanford's jasper ridge biological preserve. the data covered the years 2000– the algorithm generated questions driven by an identification key of north american birds, which we transcribed from its original book form to an online matrix. we showed that the question generating algorithm is not sensitive to how many of the six years' worth of observation data are supplied as input. even one year's worth of data made all the difference. we also showed that, at least for our bird observations at the jasper ridge preserve, the age of the data did not impact the algorithm's efficiency. observations from were just as valuable as observations from the key matrix's varying density of characters for each bird species had no impact on the algorithm. neither did differences in the minimum number of required questions among the species affect the algorithm differently than it affected the baseline alternative. that is, some species do require more questions, no matter how the question sequence is constructed. finally, we showed that the use of laplace smoothing during the calculation of probabilities for the future observation of each species works well. this result contrasts with findings in other areas, like natural language processing, where variants of the good-turing algorithm are preferred. the inclusion of the public in the collection of observation data is crucial if convincingly large and geographically diverse data sets are to be accumulated quickly. a challenge in the way of such public participation is quality assurance. ecopod is one tool that attempts to enable convenient and reliable collection of observations. authors' contributions yyy wrote the ecopod implementation. am and ap worked on the simulations and algorithms. js worked on design features and all the biological aspects. throughout the project, though, the four authors operated as a team, contributing to all aspects of the work. all authors read and approved the final manuscript. supplementary material additional file 1 appendix 1: information gain. this appendix describes the information gain algorithm in detail with examples. click here for file additional file 2 appendix 2: good-turing smoothing. this appendix describes the good-turing smoothing algorithm in detail with examples. click here for file acknowledgements we thank the volunteers and staff at the stanford jasper ridge biological preserve for the invaluable collection of bird counts. this data is clearly the foundation of this work, and its collection required years of care. we particularly mention trevor hébert, richard jeffers, peter latourrette, and phil leighton, who were intimately involved with the bird count project. in addition, richard jeffers invested many hours helping us digitize the bird field guide. this work required a bird specialist, and without his effort we could not have proceeded with our simulation and analysis. we thank the following funding sources for their generous support: am, yy and ap were supported by national science foundation grant #'sei: computing support for acquisition, collaborative curation, and dissemination in biodiversity research'. js was supported by the department of biological sciences at stanford university as well as the ford motor company through the center for evolutionary studies at stanford university.
for our dataset neither age of the historic data, nor the number of observation years impacted the algorithm. we also explore how characteristics of the matrix interact with the algorithm, and how best to predict the probability of observing a previously unseen species. point counts of birds taken at stanford university's jasper ridge biological preserve between and were used to examine the algorithm. historic observation data from the census geographic area helps minimize question volume. we sketch our species identification tool for palm sized computers that helps knowledgeable observers with census activities. for rare birds the history based algorithms did not impose a noticeable penalty in the number of questions required for identification. we explore how much historic data is required to boost performance, and whether the use of history negatively impacts identification of rare species. we found that laplace smoothing performed better for rare species than simple good-turing, and that, contrary to expectation, the technique did not then adversely affect identification performance for frequently observed birds. historic data improved identification speed, but only impacted the top 25% most frequently observed birds. intrinsic differences in identifying different birds did affect the algorithm, but the differences affected the baseline method of not using historic data to exactly the same degree.
 we sketch our species identification tool for palm sized computers that helps knowledgeable observers with census activities. an algorithm turns an identification matrix into a minimal length series of questions that guide the operator towards identification. historic observation data from the census geographic area helps minimize question volume. we explore how much historic data is required to boost performance, and whether the use of history negatively impacts identification of rare species. we also explore how characteristics of the matrix interact with the algorithm, and how best to predict the probability of observing a previously unseen species.  point counts of birds taken at stanford university's jasper ridge biological preserve between and were used to examine the algorithm. a computer identified species by correctly answering, and counting the algorithm's questions. we also explored how the character density of the key matrix and the theoretical minimum number of questions for each bird in the matrix influenced the algorithm. our investigation of the required probability smoothing determined whether laplace smoothing of observation probabilities was sufficient, or whether the more complex good-turing technique is required.  historic data improved identification speed, but only impacted the top 25% most frequently observed birds. for rare birds the history based algorithms did not impose a noticeable penalty in the number of questions required for identification. for our dataset neither age of the historic data, nor the number of observation years impacted the algorithm. density of characters for different taxa in the identification matrix did not impact the algorithms. intrinsic differences in identifying different birds did affect the algorithm, but the differences affected the baseline method of not using historic data to exactly the same degree. we found that laplace smoothing performed better for rare species than simple good-turing, and that, contrary to expectation, the technique did not then adversely affect identification performance for frequently observed birds. 