This site serves as the blog for the "collaborative" seminar on Biosurveillance being taught at the Department for Biomedical Informatics at the University of Pittsburgh. If you would like to participate in the seminar, please contact denver.h.dash@intel.com.
Summary for E. Carlstein: Nonparametric change-point estimation.
We have a sequence of $n$ independent random variables $X_i$. Somewhere in that sequence, a change occurs in the distribution, so that the first $\theta$n follow a distribution F(x) and the remaining variables follow G(x). The paper proposes a method to estimate $\theta$ - when the change occurs.
The idea is to choose the estimate $t$ so as to make the empirical distributions before $t$ and after it as different as possible. The different-ness is measured by taking the differences in _cdf_ of $X$ under the pre-t and post-t distributions -- we obtain $n$ absolute difference values. Then the difference values are taken through a mean-dominant norming function to obtain a summary statistic. The norming function can be e.g. the mean or supremum of the differences.
One drawback of the method is that it does not permit the sequence to be an actual sequence: the assumption is that $X_i$ and $X_{i+1}$ are independent. This is an especially dubious assumption in the case of epidemic diseases.
The proposed method is nonparametric (good because no assumption need be made about the parametric form of F(x) and G(x)) and capable of detecting (eventually) the changepoint on any difference between F(x) and G(x) to speak of. "To speak of" means that F and G differ on a set of non-zero probability under either one. This favorable property is in contrast to many previous methods that fail when F and G have the same mean or median.
The section on how to achieve invariance under strictly monotone transformations is a technicality to get around duplicate data values ($X_i = X_j$ for $i\neq j$).
Two theorems are proven: 1. the estimate assymptotically trends towards the true changepoint (almost surely), the expected difference decreases as (just infinitesimally less than) sqrt(n) 2. Probability that the estimate deviates more that $\epsilon$ from the true changepoint decreases exponentially with n.
Experiments on two real-world datasets are conducted to find that the results are intuitively reasonable and in agreement with previous parametric detection methods. The resolution power is also verified in a simulated study, but the two distributions chosen in the study are rather extremely opposed, so it is not clear how well this result transfers to the real world.
Things that took pen, paper and time to figure out: - $\delta^{\theta}_{ni}$ is actually $F(X_i^n) - G(X_i^n)$
Things that remain unclear to me: - How exactly does the last equation on page 189 follow? - Clearly, invariance under strict monotone transformations of the data is a good thing. Why is it especially important for a nonparametric estimator (page 191, first paragraph)? - Why is mean-dominance essential, except for technical convenience?
link to paper http://www.stat.rutgers.edu/~madigan/PAPERS/surveillance.pdf
Summary of Madigan (2005). Bayesian data mining for health surveillance.
Paper explores different Bayesian extension of HMM used by Le Strat and Carrat for anomaly detection. Method discussed in the paper can be used for multivariate analysis but this paper is focused mainly on exploring the performance of different versions of HMM for univariate time series.
Paper extending work of Le Strat and Carrat(1990) who used HMM for biosurveillance from non-Bayesian perspective. $z^'_t$ with $t = 1, \ldots ,n$ form a first order Markov chain. Each pair of vertices $\left( {z_t ,y_t } \right)$ represents mixture model.$y_t$ can be multivariate. Conditional distribution y|z~Gaussian(mean,precision) is assumed. Serfling's cyclic regression method for mean $\mu _j$ with state specific trend and delta and epsilon state specific parameters associated with r-periods seasonality was used Madigan extended the model by assigning distributions to the parameters in the Serfling's model for mean. He tested model with influenza-like disease time series.
Another modification he tried to use Poison distribution for monthly poliomyelitis time-series.
He also compared model using mixture of various distributions: lognormal, gamma, exponential, Gaussian. Paper also discuss different measure used to compare different models: BIC with penalty term for number of parameters, deviance information criterion (DIC), complete DIC,and $DIC^V _C$. Comparison suggested that lognormal distribution provides better fit then other three distributions.
Paper also explored what number of states of hidden variable is optimal. Model when hidden variable has 3 states seemes to perform best.
He also discussed random observation time HMMs (case when data do not arrive in equally-spaced timepoints).
Summary of Early statistical detection of anthrax outbreaks by tracking over-the-counter medication sales. (http://www.pnas.org/cgi/reprint/99/8/5237)
Some highlights of this paper are: 1. Monitor grocery and over-the-counter (OTC) medication sales data, a new type of surveillance data, which may be more timely than traditional medical and public health data. 2. Describes a statistical framework for monitoring grocery data by using time series analysis. Use wavelets approach to smooth time series data. 3. Propose an evaluation method that is suitable in the absence of data on large-scale disease outbreaks.
Overview of these highlights: 1. Over-the-counter medication sales data is a newer type of surveillance data that is used for monitoring disease outbreaks. These data have significant potential as early indicators of disease outbreaks. Sick people treat themselves with nonprescription cough syrups, flu remedies. In addition to medications, they also purchase thermometers and other items for their illness, such as tissues, orange juice, and chicken soup. They frequently make purchases before seeking medical care or even instead of seeking medical care. Therefore, the use of nontraditional data sources, such as grocery and pharmacy data, school attendance records, uses of web sources, could improve the chances of detection. Furthermore, these datasets are typically large and rich. They are available on a more frequent scale, such as daily and even hourly basis. Third, although these data do not measure illness directly, we might infer specific symptoms experienced by purchasers at a relatively early stage of the onset of the disease.
2. Although there are some advantages for monitoring grocery and OTC medication sales data, these data contain much noise. There are many non-disease factors that influence the level of sales of a given OTC product. Sources of variability include day of week, season, holidays and severe weather. They designed a modular detection system, composed of several layers, where each layer applies a statistical tool to an OTC sales series. In the first and the second layer, they preprocess and denoise these data before applying some time-series analysis on the data. This paper uses some wavelets techniques to smooth the time series data. In order to denoise the data, a discrete cosine transform is applied to decompose the series into cosine waves and retain the cosine waves that have a large magnitude to capture the main features of the time series. In the third layer, because of the non-stationarity of the time series, the series have to be decomposed into several resolutions. Then autoregressive model can be applied for predicting each resolution separately. Each resolution describes a different frequency of the series and it retains information on the time that each frequency is present. Then, the predictions for each resolution are added for forecasting the next day sales. Finally, the detection system has to give a threshold in order to raise an alarm when the actual next day sales exceed the threshold. The threshold is based on the forecast made in the previous step, plus a margin of error. (There are many formulas involving in the above techniques and I really do not have time to type them here. I will briefly talk about Function Spaces and Wavelets in class.)
3. This paper proposes a statistical simulation approach to evaluate the detection system. In order to simulate a large-scale release of inhalational anthrax, the paper introduced a method on how to use data from the Sverdlovsk anthrax outbreak to construct a footprint of anthrax in grocery data. By analyzing the survival plot, which shows the probability of surviving for the number of days since onset, for the 66 (of the 68) people who died and the 11 people who survived in this outbreak, an assumption that the medication sales for specific anthrax symptoms will increase steadily over the first three days. Then they added the simulated footprint to the daily sales series and measured the spike detection ratio (SDR) that is the number of footprints detected, normalized by the number of footprints added to the datasets.
By traditional definition, a gold standard is a composite of two notions. In the first sense, a gold standard is an expression of practice carried out perfectly: the optimal therapy for a given biomedical problem or the best differential diagnosis at a particular point in the evolution of a case. In the second sense, a gold standard implies complete acceptance or consensus (7). For example, for a probabilistic expert system, a gold standard could be the physician’s final diagnostic report for patients who survived and an autopsy report for those who did not. As to buying a pair of shoes, our feet often serve as a gold standard. After all, shoes must first fit our feet before we concern ourselves with their other features.
Performance standards are the standards to which our system is compared. The measurement of accuracy against a gold standard is not sufficient to show the quality of system performance. Is 96% accuracy good enough? We will not know until we compare it to performance standards such as the accuracy of a human expert. For example, in evaluating a medical expert system, we often use (if feasible) three types of performance standards: human expert diagnosticians, other existing expert systems, and user feedback. In the situation of buying a pair of shoes, the shoes we have already owned often serve as performance standards.
In an evaluation process, we often need both a gold standard and one or more performance standards. We need a gold standard to determine how often the system makes correct judgments. On the other hand, we need performance standards to learn where our system stands among existing systems, and thereby determine the relative worth of our system. It is analogous to the situation in which we use our feet to try shoes, but we often compare a new pair of shoes to the shoes we already own to determine whether they are worth buying.
However, people often confuse a gold standard with a performance standard. The most often seen problem is that some people use a gold standard to play both roles. We should remember that a gold standard alone usually does not provide sufficient measurement concerning the relative performance of a system. We usually do not buy a pair of shoes simply because it seems to fit. The fact is, if we had never owned a previous pair of shoes, it is unlikely that we could judge that the first pair we try fits best, even though we have with us the gold standard, our feet. On the other hand, we should remember that no system can beat a gold standard performance-wise. As a matter of fact, “gold” means that it does not lose. When we call something a gold standard, we accept that what it says is 100% true. Obviously, no one would claim that a pair of shoes fits 20% better than our feet. Similarly, if we use autopsy report as our gold standard for evaluating a medical diagnostic support system, we would not claim that our system is 10% more accurate that the autopsy report. When it comes to the evaluation of an outbreak detection system, the claim that a system detects an outbreak “10 days earlier than the gold standard” certainly does not sound too thoughtful. After all, no matter how much we value the earliness of a detection system, we will not worship a system that detects an outbreak earlier than when the outbreak starts.
You might ask then why we need to develop any other systems if no system can beat a gold standard in determining the truth. My answer is simple: even if an autopsy report is 100% trustworthy, it is still valuable to have an expert system that is correct only 95% of time while a patient is still alive. Again using the metaphor of the shoes, although we can walk on our feet if we choose to, we still buy shoes.
8 comments:
Summary for E. Carlstein: Nonparametric change-point estimation.
We have a sequence of $n$ independent random variables $X_i$. Somewhere in that
sequence, a change occurs in the distribution, so that the first $\theta$n follow
a distribution F(x) and the remaining variables follow G(x). The paper proposes
a method to estimate $\theta$ - when the change occurs.
The idea is to choose the estimate $t$ so as to make the empirical distributions
before $t$ and after it as different as possible.
The different-ness is measured by taking the differences in _cdf_ of $X$
under the pre-t and post-t distributions -- we obtain $n$ absolute difference values.
Then the difference values are taken through a mean-dominant norming function
to obtain a summary statistic. The norming function can be e.g. the mean or
supremum of the differences.
One drawback of the method is that it does not permit the sequence to be
an actual sequence: the assumption is that $X_i$ and $X_{i+1}$ are independent.
This is an especially dubious assumption in the case of epidemic diseases.
The proposed method is nonparametric (good because no assumption need be made
about the parametric form of F(x) and G(x)) and capable of detecting (eventually)
the changepoint on any difference between F(x) and G(x) to speak of.
"To speak of" means that F and G differ on a set of non-zero probability under either one.
This favorable property is in contrast to many previous methods that fail
when F and G have the same mean or median.
The section on how to achieve invariance under strictly monotone transformations
is a technicality to get around duplicate data values ($X_i = X_j$ for $i\neq j$).
Two theorems are proven:
1. the estimate assymptotically trends towards the true changepoint (almost surely),
the expected difference decreases as (just infinitesimally less than) sqrt(n)
2. Probability that the estimate deviates more that $\epsilon$ from the true
changepoint decreases exponentially with n.
Experiments on two real-world datasets are conducted to find that the results
are intuitively reasonable and in agreement with previous parametric detection methods.
The resolution power is also verified in a simulated study, but the two distributions
chosen in the study are rather extremely opposed, so it is not clear how well
this result transfers to the real world.
Things that took pen, paper and time to figure out:
- $\delta^{\theta}_{ni}$ is actually $F(X_i^n) - G(X_i^n)$
Things that remain unclear to me:
- How exactly does the last equation on page 189 follow?
- Clearly, invariance under strict monotone transformations of the data is a good thing.
Why is it especially important for a nonparametric estimator (page 191, first paragraph)?
- Why is mean-dominance essential, except for technical convenience?
link to paper http://www.stat.rutgers.edu/~madigan/PAPERS/surveillance.pdf
Summary of Madigan (2005). Bayesian data mining for health surveillance.
Paper explores different Bayesian extension of HMM used by Le Strat and Carrat for anomaly detection. Method discussed in the paper can be used for multivariate analysis but this paper is focused mainly on exploring the performance of different versions of HMM for univariate time series.
Paper extending work of Le Strat and Carrat(1990) who used HMM for biosurveillance from non-Bayesian perspective.
$z^'_t$ with $t = 1, \ldots ,n$ form a first order Markov chain. Each pair of vertices $\left( {z_t ,y_t } \right)$ represents mixture model.$y_t$ can be multivariate. Conditional distribution y|z~Gaussian(mean,precision) is assumed.
Serfling's cyclic regression method for mean $\mu _j$ with state specific trend and delta and epsilon state specific parameters associated with r-periods seasonality was used
Madigan extended the model by assigning distributions to the parameters in the Serfling's model for mean. He tested model with influenza-like disease time series.
Another modification he tried to use Poison distribution for monthly poliomyelitis time-series.
He also compared model using mixture of various distributions: lognormal, gamma, exponential, Gaussian.
Paper also discuss different measure used to compare different models: BIC with penalty term for number of parameters, deviance information criterion (DIC), complete DIC,and $DIC^V _C$.
Comparison suggested that lognormal distribution provides better fit then other three distributions.
Paper also explored what number of states of hidden variable is optimal. Model when hidden variable has 3 states seemes to perform best.
He also discussed random observation time HMMs (case when data do not arrive in equally-spaced timepoints).
Summary of Early statistical detection of anthrax outbreaks by tracking over-the-counter medication sales. (http://www.pnas.org/cgi/reprint/99/8/5237)
Some highlights of this paper are:
1. Monitor grocery and over-the-counter (OTC) medication sales data, a new type of surveillance data, which may be more timely than traditional medical and public health data.
2. Describes a statistical framework for monitoring grocery data by using time series analysis. Use wavelets approach to smooth time series data.
3. Propose an evaluation method that is suitable in the absence of data on large-scale disease outbreaks.
Overview of these highlights:
1. Over-the-counter medication sales data is a newer type of surveillance data that is used for monitoring disease outbreaks. These data have significant potential as early indicators of disease outbreaks. Sick people treat themselves with nonprescription cough syrups, flu remedies. In addition to medications, they also purchase thermometers and other items for their illness, such as tissues, orange juice, and chicken soup. They frequently make purchases before seeking medical care or even instead of seeking medical care. Therefore, the use of nontraditional data sources, such as grocery and pharmacy data, school attendance records, uses of web sources, could improve the chances of detection. Furthermore, these datasets are typically large and rich. They are available on a more frequent scale, such as daily and even hourly basis. Third, although these data do not measure illness directly, we might infer specific symptoms experienced by purchasers at a relatively early stage of the onset of the disease.
2. Although there are some advantages for monitoring grocery and OTC medication sales data, these data contain much noise. There are many non-disease factors that influence the level of sales of a given OTC product. Sources of variability include day of week, season, holidays and severe weather. They designed a modular detection system, composed of several layers, where each layer applies a statistical tool to an OTC sales series. In the first and the second layer, they preprocess and denoise these data before applying some time-series analysis on the data. This paper uses some wavelets techniques to smooth the time series data. In order to denoise the data, a discrete cosine transform is applied to decompose the series into cosine waves and retain the cosine waves that have a large magnitude to capture the main features of the time series. In the third layer, because of the non-stationarity of the time series, the series have to be decomposed into several resolutions. Then autoregressive model can be applied for predicting each resolution separately. Each resolution describes a different frequency of the series and it retains information on the time that each frequency is present. Then, the predictions for each resolution are added for forecasting the next day sales. Finally, the detection system has to give a threshold in order to raise an alarm when the actual next day sales exceed the threshold. The threshold is based on the forecast made in the previous step, plus a margin of error.
(There are many formulas involving in the above techniques and I really do not have time to type them here. I will briefly talk about Function Spaces and Wavelets in class.)
3. This paper proposes a statistical simulation approach to evaluate the detection system. In order to simulate a large-scale release of inhalational anthrax, the paper introduced a method on how to use data from the Sverdlovsk anthrax outbreak to construct a footprint of anthrax in grocery data. By analyzing the survival plot, which shows the probability of surviving for the number of days since onset, for the 66 (of the 68) people who died and the 11 people who survived in this outbreak, an assumption that the medication sales for specific anthrax symptoms will increase steadily over the first three days. Then they added the simulated footprint to the daily sales series and measured the spike detection ratio (SDR) that is the number of footprints detected, normalized by the number of footprints added to the datasets.
I uploaded Greg's review here:
http://groups-beta.google.com/group/biosurveillance_seminar/web/BCD+overview.doc
Denver.
Gold Standards and Feet
By traditional definition, a gold standard is a composite of two notions. In the first sense, a gold standard is an expression of practice carried out perfectly: the optimal therapy for a given biomedical problem or the best differential diagnosis at a particular point in the evolution of a case. In the second sense, a gold standard implies complete acceptance or consensus (7). For example, for a probabilistic expert system, a gold standard could be the physician’s final diagnostic report for patients who survived and an autopsy report for those who did not. As to buying a pair of shoes, our feet often serve as a gold standard. After all, shoes must first fit our feet before we concern ourselves with their other features.
Performance standards are the standards to which our system is compared. The measurement of accuracy against a gold standard is not sufficient to show the quality of system performance. Is 96% accuracy good enough? We will not know until we compare it to performance standards such as the accuracy of a human expert. For example, in evaluating a medical expert system, we often use (if feasible) three types of performance standards: human expert diagnosticians, other existing expert systems, and user feedback. In the situation of buying a pair of shoes, the shoes we have already owned often serve as performance standards.
In an evaluation process, we often need both a gold standard and one or more performance standards. We need a gold standard to determine how often the system makes correct judgments. On the other hand, we need performance standards to learn where our system stands among existing systems, and thereby determine the relative worth of our system. It is analogous to the situation in which we use our feet to try shoes, but we often compare a new pair of shoes to the shoes we already own to determine whether they are worth buying.
However, people often confuse a gold standard with a performance standard. The most often seen problem is that some people use a gold standard to play both roles. We should remember that a gold standard alone usually does not provide sufficient measurement concerning the relative performance of a system. We usually do not buy a pair of shoes simply because it seems to fit. The fact is, if we had never owned a previous pair of shoes, it is unlikely that we could judge that the first pair we try fits best, even though we have with us the gold standard, our feet. On the other hand, we should remember that no system can beat a gold standard performance-wise. As a matter of fact, “gold” means that it does not lose. When we call something a gold standard, we accept that what it says is 100% true. Obviously, no one would claim that a pair of shoes fits 20% better than our feet. Similarly, if we use autopsy report as our gold standard for evaluating a medical diagnostic support system, we would not claim that our system is 10% more accurate that the autopsy report. When it comes to the evaluation of an outbreak detection system, the claim that a system detects an outbreak “10 days earlier than the gold standard” certainly does not sound too thoughtful. After all, no matter how much we value the earliness of a detection system, we will not worship a system that detects an outbreak earlier than when the outbreak starts.
You might ask then why we need to develop any other systems if no system can beat a gold standard in determining the truth. My answer is simple: even if an autopsy report is 100% trustworthy, it is still valuable to have an expert system that is correct only 95% of time while a patient is still alive. Again using the metaphor of the shoes, although we can walk on our feet if we choose to, we still buy shoes.
http://biosurveillance_seminar.googlegroups.com/web/Tutorial%20on%20HMMs%20and%20Selected%20Applications%20in%20Speech%20Recognition.doc?gda=1zaRDXUAAAB5THpO-Losai017pLRT8IZUgik6xx4OOgAA2YBLSxeHmG1qiJ7UbTIup-M2XPURDRyzUJRzksmfguTzGPnx8inwM3y4xKN73EW1my7ONAkQvXRB5hKcA2F_hqTFzy66lDoefGv_n0-3QkuyzJyOatQePrcwpKsnAut0e_luTXAPw&hl=en
This is a link to my paper :)
Hi. Jon's link is taking me to a screwy place :) If you have trouble accessing his paper, you can find it in the "files" section :
http://groups.google.com/group/biosurveillance_seminar.
Hi all. Sorry it's so late! You should be able to download my paper on ARMA, etc. processes here:
http://groups.google.com/group/biosurveillance_seminar/web/ARMA%2CARIMA%2CSARIMA.doc.
If that link doesn't work, just go to the google group and you should be able to get it there (see the above comment).
Post a Comment