nips nips2003 nips2003-123 knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Nicholas P. Hughes, Lionel Tarassenko, Stephen J. Roberts
Abstract: We examine the use of hidden Markov and hidden semi-Markov models for automatically segmenting an electrocardiogram waveform into its constituent waveform features. An undecimated wavelet transform is used to generate an overcomplete representation of the signal that is more appropriate for subsequent modelling. We show that the state durations implicit in a standard hidden Markov model are ill-suited to those of real ECG features, and we investigate the use of hidden semi-Markov models for improved state duration modelling. 1
Reference: text
sentIndex sentText sentNum sentScore
1 uk Abstract We examine the use of hidden Markov and hidden semi-Markov models for automatically segmenting an electrocardiogram waveform into its constituent waveform features. [sent-6, score-0.563]
2 An undecimated wavelet transform is used to generate an overcomplete representation of the signal that is more appropriate for subsequent modelling. [sent-7, score-0.32]
3 We show that the state durations implicit in a standard hidden Markov model are ill-suited to those of real ECG features, and we investigate the use of hidden semi-Markov models for improved state duration modelling. [sent-8, score-0.568]
4 Of particular interest is the electrocardiogram (ECG1 ) of the patient, which provides detailed information about the state of the patient’s heart. [sent-12, score-0.155]
5 By examining the ECG signal in detail it is possible to derive a number of informative measurements from the characteristic ECG waveform. [sent-13, score-0.098]
6 In particular, drug-induced prolongation of the QT interval (so called Long QT Syndrome) can result in a very fast, abnormal heart rhythm known as torsade de pointes, which is often followed by sudden cardiac death 2 . [sent-16, score-0.219]
7 In practice, QT interval measurements are carried out manually by specially trained ECG analysts. [sent-17, score-0.171]
8 terfenadine, which had the side-effect of significantly prolonging the QT interval in a number of patients. [sent-29, score-0.105]
9 In this paper we consider the problem of automated ECG interval analysis from a machine learning perspective. [sent-31, score-0.161]
10 In particular, we examine the use of hidden Markov models for automatically segmenting an ECG signal into its constituent waveform features. [sent-32, score-0.336]
11 A redundant wavelet transform is used to provide an informative representation which is both robust to noise and tuned to the morphological characteristics of the waveform features. [sent-33, score-0.451]
12 Finally we investigate the use of hidden semi-Markov models for explicit state duration modelling. [sent-34, score-0.302]
13 Figure 1 shows a human ECG waveform and the associated features. [sent-38, score-0.162]
14 The standard features of the ECG waveform are the P wave, the QRS complex and the T wave. [sent-39, score-0.214]
15 Additionally a small U wave (following the T wave) is occasionally present. [sent-40, score-0.305]
16 The cardiac cycle begins with the P wave (the start and end points of which are referred to as Pon and Poff ), which corresponds to the period of atrial depolarization in the heart. [sent-41, score-0.47]
17 The T wave follows the QRS complex and corresponds to the period of ventricular repolarization. [sent-44, score-0.373]
18 The end point of the T wave is referred to as Toff and represents the end of the cardiac cycle (presuming the absence of a U wave). [sent-45, score-0.407]
19 2 ECG Interval Analysis The timing between the onset and offset of particular features of the ECG (referred to as an interval) is of great importance since it provides a measure of the state of the heart and can indicate the presence of certain cardiological conditions. [sent-47, score-0.214]
20 The two most important intervals in the ECG waveform are the QT interval and the PR interval. [sent-48, score-0.267]
21 The QT interval is defined as the time from the start of the QRS complex to the end of the T wave, i. [sent-49, score-0.176]
22 Toff − Q, and corresponds to the total duration of electrical activity (both depolarization and repolarization) in the ventricles. [sent-51, score-0.163]
23 Similarly, the PR interval is defined as the time from the start of the P wave to the start of the QRS complex, i. [sent-52, score-0.446]
24 Q − Pon , and corresponds to the time from the onset of atrial depolarization to the onset of ventricular depolarization. [sent-54, score-0.144]
25 The measurement of the QT interval is complicated by the fact that a precise mathematical definition of the end of the T wave does not exist. [sent-55, score-0.431]
26 Thus T wave end measurements are inherently subjective and the resulting QT interval measurements often suffer from a high degree of inter- and intra-analyst variability. [sent-56, score-0.509]
27 An automated ECG interval analysis system, which could provide robust and consistent measurements (together with an associated degree of confidence in each measurement), would therefore be of great benefit to the medical community. [sent-57, score-0.2]
28 3 Previous Work on Automated ECG Interval Analysis The vast majority of algorithms for automated QT analysis are based on threshold methods which attempt to predict the end of the T wave as the point where the T wave crosses a predetermined threshold [3]. [sent-59, score-0.687]
29 An exception to this is the work of Koski [4] who trained a hidden Markov model on raw ECG data using the Baum-Welch algorithm. [sent-60, score-0.125]
30 More recently, Graja and Boucher have investigated the use of hidden Markov tree models for segmenting ECG signals encoded with the discrete wavelet transform [2]. [sent-62, score-0.369]
31 3 Data Collection In order to develop an automated system for ECG interval analysis, we collected a data set of over 100 ECG waveforms (sampled at 500 Hz), together with the corresponding waveform feature boundaries3 as determined by a group of expert ECG analysts. [sent-63, score-0.367]
32 Due to time constraints it was not possible for each expert analyst to label every ECG waveform in the data set. [sent-64, score-0.203]
33 Therefore we chose to distribute the waveforms at random amongst the different experts (such that each waveform was measured by one expert only). [sent-65, score-0.206]
34 For each ECG waveform, the following points were labelled: Pon , Poff , Q, J and Toff (if a U wave was present the Uoff point was also labelled). [sent-66, score-0.305]
35 In addition, the point corresponding to the start of the next P wave (i. [sent-67, score-0.323]
36 the P wave of the following heart beat), NPon , was also labelled. [sent-69, score-0.335]
37 4 A Hidden Markov Model for ECG Interval Analysis It is natural to view the ECG signal as the result of a generative process, in which each waveform feature is generated by the corresponding cardiological state of the heart. [sent-71, score-0.347]
38 In addition, the ECG state sequence obeys the Markov property, since each state is solely 3 We developed a novel software application which enabled an ECG analyst to label the boundaries of each of the features of an ECG waveform, using a pair of “onscreen calipers”. [sent-72, score-0.258]
39 P wave Baseline 1 QRS complex T wave Baseline 2 U wave 5. [sent-73, score-0.947]
40 Thus, hidden Markov models (HMMs) would seem ideally suited to the task of segmenting an ECG signal into its constituent waveform features. [sent-111, score-0.321]
41 Using the labelled data set of ECG waveforms we trained a hidden Markov model in a supervised manner. [sent-112, score-0.157]
42 The parameters of the transition matrix aij were computed using the maximum likelihood estimates, given by: aij = nij / ˆ nik (1) k where nij is the total number of transitions from state i to state j over all of the label sequences. [sent-114, score-0.286]
43 We estimated the observation (or emission) probability densities bi for each state i by fitting a Gaussian mixture model (GMM) to the set of signal samples corresponding to that particular state4 . [sent-115, score-0.17]
44 In our initial experiments, we found that the use of a single state to represent all the regions of baseline in the ECG waveform resulted in poor performance when the model was used to infer the underlying state sequence of new unseen waveforms. [sent-117, score-0.447]
45 In particular, a single baseline state allowed for the possibility of the model returning to the P wave state, following a P wave - Baseline sequence. [sent-118, score-0.788]
46 Therefore we decided to partition the Baseline state into two separate states; one corresponding to the region of baseline between the P off and Q points (which we termed “Baseline 1”), and a second corresponding to the region between the Toff and NPon points5 (termed “Baseline 2”). [sent-119, score-0.178]
47 This was done in order to normalise the dynamic range of the signals and stabilise the baseline sections. [sent-122, score-0.091]
48 Once the model had been trained, the Viterbi algorithm [9] was used to infer the optimal state sequence for each of the signals in the test set. [sent-123, score-0.127]
49 Table 1 shows the resulting confusion matrix (computed from the state assignments on a sample-point basis). [sent-124, score-0.131]
50 Although reasonable classification accuracies are obtained for the QRS complex and T wave states, the P wave state is almost entirely misclassified as Baseline 1, Baseline 2 or U wave. [sent-125, score-0.749]
51 In order to improve the performance of the model, we require an encoding of the ECG that captures the key temporal and spectral characteristics of the waveform features in a more informative representation than that of the raw time series data alone. [sent-126, score-0.301]
52 Thus we now examine the use of wavelet methods for this purpose. [sent-127, score-0.206]
53 5 If a U wave was present the Uoff point was used instead of Toff . [sent-129, score-0.305]
54 P wave Baseline 1 QRS complex T wave Baseline 2 U wave 74. [sent-130, score-0.947]
55 4 Table 2: Percentage confusion matrix for an HMM trained on the wavelet encoded ECG. [sent-157, score-0.268]
56 They are able to capture the non-stationary spectral characteristics of a signal by decomposing it over a set of atoms which are localised in both time and frequency. [sent-160, score-0.118]
57 The most popular wavelet transform algorithm is the discrete wavelet transform (DWT), which uses the set of dyadic scales (i. [sent-162, score-0.479]
58 those based on powers of two) and translates of the mother wavelet to form an orthonormal basis for signal analysis. [sent-164, score-0.264]
59 An alternative transform is derived by allowing the translation parameter to vary continuously, whilst restricting the scale parameter to a dyadic scale (thus, the set of time-frequency atoms now forms a frame). [sent-166, score-0.109]
60 This leads to the undecimated wavelet transform6 (UWT), which for a signal s ∈ L2 (R), is given by: 1 wυ (τ ) = √ υ +∞ s(t) ψ ∗ −∞ t−τ υ dt υ = 2k , k ∈ Z, τ ∈ R (2) where wυ (τ ) are the UWT coefficients at scale υ and shift τ , and ψ ∗ is the complex conjugate of the mother wavelet. [sent-167, score-0.344]
61 The UWT is particularly well-suited to ECG interval analysis as it provides a timefrequency description of the ECG signal on a sample-by-sample basis. [sent-169, score-0.147]
62 In order to find the most effective wavelet basis for our application, we examined the performance of HMMs trained on ECG data encoded with wavelets from the Daubechies, Symlet, Coiflet and Biorthogonal wavelet families. [sent-171, score-0.454]
63 In the frequency domain, a wavelet at a given scale is associated with a bandpass filter7 of a particular centre frequency. [sent-172, score-0.207]
64 Thus the optimal wavelet basis will correspond to the set of bandpass filters that are tuned to the unique spectral characteristics of the ECG. [sent-173, score-0.266]
65 In our experiments we found that the Coiflet wavelet with two vanishing moments resulted in the highest overall classification accuracy. [sent-174, score-0.191]
66 It is evident that the UWT encoding results in a significant improvement in classification accuracy (for all but the U wave state), when compared with the results obtained on the raw ECG data. [sent-176, score-0.367]
67 6 The undecimated wavelet transform is also known as the stationary wavelet transform and the translation-invariant wavelet transform. [sent-177, score-0.699]
68 005 0 0 0 50 100 150 State duration (ms) 200 0 0 50 100 State duration (ms) 150 0 100 200 300 State duration (ms) 400 Figure 2: Histograms of the true state durations and those decoded by the HMM. [sent-197, score-0.669]
69 2 HMM State Durations A significant limitation of the standard hidden Markov model is the manner in which it models state durations. [sent-199, score-0.166]
70 For a given state i with self-transition coefficient aii , the probability density of the state duration d is a geometric distribution, given by: pi (d) = (aii )d−1 (1 − aii ) (3) For the waveform features of the ECG signal, this geometric distribution is inappropriate. [sent-200, score-0.601]
71 Figure 2 shows histograms of the true state durations and the durations of the states decoded by the HMM, for each of the P wave, QRS complex and T wave states. [sent-201, score-0.81]
72 In each case it is clear that a significant number of decoded states have a duration that is much shorter than the minimum state duration observed with real ECG signals. [sent-202, score-0.455]
73 Thus for a given ECG waveform the decoded state sequence may contain many more state transitions than are actually present in the signal. [sent-203, score-0.46]
74 The resulting HMM state segmentation is then likely to be poor and the resulting QT and PR interval measurements unreliable. [sent-204, score-0.275]
75 One solution to this problem is to post-process the decoded state sequences using a median filter designed to smooth out sequences whose duration is known to be physiologically implausible. [sent-205, score-0.312]
76 A more principled and more effective approach, however, is to model the probability density of the individual state durations explicitly, using a hidden semi-Markov model. [sent-206, score-0.281]
77 5 A Hidden Semi-Markov Model for ECG Interval Analysis A hidden semi-Markov model (HSMM) differs from a standard HMM in that each of the self-transition coefficients aii are set to zero, and an explicit probability density is specified for the duration of each state [5]. [sent-207, score-0.344]
78 In this way, the individual state duration densities govern the amount of time the model spends in a given state, and the transition matrix governs the probability of the next state once this time has elapsed. [sent-208, score-0.356]
79 To model the durations pi (d) of the various waveform features of the ECG, we used a Gamma density since this is a positive distribution which is able to capture the inherent skewness of the ECG state durations. [sent-210, score-0.404]
80 For each state i, maximum likelihood estimates of the shape and scale parameters were computed directly from the set of labelled ECG signals (as part of the cross-validation procedure). [sent-211, score-0.171]
81 In order to infer the most probable state sequence Q = {q1 q2 · · · qT } for a given observation sequence O = {O1 O2 · · · OT }, the standard Viterbi algorithm must be modified to P wave QRS complex 0. [sent-212, score-0.465]
82 005 0 0 0 50 100 150 State duration (ms) 200 0 0 50 100 State duration (ms) 150 0 100 200 300 State duration (ms) 400 Figure 3: Histograms of the true state durations and those decoded by the HSMM. [sent-230, score-0.669]
83 handle the explicit state duration densities of the HSMM. [sent-231, score-0.264]
84 We start by defining the likelihood of the most probable state sequence that accounts for the first t observations and ends in state i: δt (i) = max p(q1 q2 · · · qt = i, O1 O2 · · · Ot |λ) (4) q1 q2 ···qt−1 where λ is the set of parameters governing the HSMM. [sent-232, score-0.392]
85 The recurrence relation for computing δt (i) is then given by: δt (i) = max max δt−di (j)aji pi (di ) Πt =t−di +1 bi (Ot ) t di j (5) where the outer maximisation is performed over all possible values of the state duration d i for state i, and the inner maximisation is over all states j. [sent-233, score-0.418]
86 At each time t and for each state i, the two arguments that maximise equation (5) are recorded, and a simple backtracking procedure can then be used to find the most probable state sequence. [sent-234, score-0.235]
87 The time complexity of the Viterbi decoding procedure for an HSMM is given by O(K 2 T Dmax ), where K is the total number of states, and Dmax is the maximum range of state durations over all K states, i. [sent-235, score-0.222]
88 Figure 3 shows histograms of the resulting state durations for an HSMM trained on a wavelet encoding of the ECG (using 5-fold cross-validation). [sent-240, score-0.493]
89 Clearly, the durations of the decoded state sequences are very well matched to the true durations of each of the ECG features. [sent-241, score-0.421]
90 This improvement in duration modelling is reflected in the accuracy and robustness of the segmentations produced by the HSMM. [sent-242, score-0.153]
91 Model HMM on raw ECG HMM on wavelet encoded ECG HSMM on wavelet encoded ECG Pon 157 12 13 Q 31 11 3 J 27 20 7 Toff 139 46 12 Table 3: Mean absolute segmentation errors (in milliseconds) for each of the models. [sent-243, score-0.497]
92 On the important task of accurately determining the Q and T off points for QT interval measurements, the HSMM significantly outperforms the HMM. [sent-245, score-0.105]
93 6 Discussion In this work we have focused on the two core issues in developing an automated system for ECG interval analysis: the choice of representation for the ECG signal and the choice of model for the segmentation. [sent-247, score-0.203]
94 We have demonstrated that wavelet methods, and in particular the undecimated wavelet transform, can be used to generate an encoding of the ECG which is tuned to the unique spectral characteristics of the ECG waveform features. [sent-248, score-0.674]
95 With this representation the performance of the models on new unseen ECG waveforms is significantly better than similar models trained on the raw time series data. [sent-249, score-0.093]
96 We have also shown that the robustness of the segmentation process can be improved through the use of explicit state duration modelling with hidden semi-Markov models. [sent-250, score-0.358]
97 The robustness with which we can detect such unreliable QT interval measurements based on this log likelihood score is one of the main focuses of our current research. [sent-257, score-0.16]
98 Evaluation of an automatic threshold based detector e ia, of waveform limits in Holter ECG with QT database. [sent-279, score-0.162]
99 Continuously variable duration hidden Markov models for automatic speech recognition. [sent-289, score-0.195]
100 The dose-response relationship between Terfenadine (Seldane) and the QTc interval on the scalar electrocardiogram in normals and patients with cardiovascular disease and the QTc interval variability. [sent-304, score-0.258]
wordName wordTfidf (topN-words)
[('ecg', 0.796), ('wave', 0.305), ('wavelet', 0.191), ('qrs', 0.169), ('waveform', 0.162), ('qt', 0.139), ('duration', 0.121), ('durations', 0.115), ('state', 0.107), ('interval', 0.105), ('decoded', 0.084), ('uwt', 0.072), ('baseline', 0.071), ('hsmm', 0.06), ('hidden', 0.059), ('hmm', 0.058), ('automated', 0.056), ('pon', 0.052), ('electrocardiogram', 0.048), ('undecimated', 0.048), ('labelled', 0.044), ('depolarization', 0.042), ('aii', 0.042), ('cardiac', 0.042), ('signal', 0.042), ('transform', 0.039), ('measurements', 0.039), ('raw', 0.039), ('atoms', 0.036), ('cardiological', 0.036), ('dwt', 0.036), ('ventricular', 0.036), ('segmenting', 0.034), ('markov', 0.033), ('complex', 0.032), ('mother', 0.031), ('ms', 0.031), ('histograms', 0.03), ('heart', 0.03), ('trained', 0.027), ('waveforms', 0.027), ('dmax', 0.027), ('ot', 0.027), ('drug', 0.027), ('encoded', 0.026), ('patient', 0.025), ('segmentation', 0.024), ('analyst', 0.024), ('atrial', 0.024), ('coi', 0.024), ('graja', 0.024), ('npon', 0.024), ('qtc', 0.024), ('repolarization', 0.024), ('terfenadine', 0.024), ('uo', 0.024), ('confusion', 0.024), ('constituent', 0.024), ('pr', 0.024), ('characteristics', 0.023), ('encoding', 0.023), ('di', 0.023), ('hmms', 0.022), ('viterbi', 0.022), ('states', 0.022), ('end', 0.021), ('densities', 0.021), ('onset', 0.021), ('probable', 0.021), ('sudden', 0.021), ('death', 0.021), ('nij', 0.021), ('features', 0.02), ('signals', 0.02), ('dence', 0.02), ('dyadic', 0.019), ('syndrome', 0.019), ('maximisation', 0.019), ('wavelets', 0.019), ('tuned', 0.019), ('coef', 0.018), ('oxford', 0.018), ('gmm', 0.018), ('ltd', 0.018), ('start', 0.018), ('referred', 0.018), ('informative', 0.017), ('expert', 0.017), ('spectral', 0.017), ('comprised', 0.017), ('robustness', 0.016), ('modelling', 0.016), ('po', 0.016), ('bandpass', 0.016), ('cients', 0.015), ('explicit', 0.015), ('whilst', 0.015), ('examine', 0.015), ('speech', 0.015), ('aij', 0.015)]
simIndex simValue paperId paperTitle
same-paper 1 0.99999988 123 nips-2003-Markov Models for Automated ECG Interval Analysis
Author: Nicholas P. Hughes, Lionel Tarassenko, Stephen J. Roberts
Abstract: We examine the use of hidden Markov and hidden semi-Markov models for automatically segmenting an electrocardiogram waveform into its constituent waveform features. An undecimated wavelet transform is used to generate an overcomplete representation of the signal that is more appropriate for subsequent modelling. We show that the state durations implicit in a standard hidden Markov model are ill-suited to those of real ECG features, and we investigate the use of hidden semi-Markov models for improved state duration modelling. 1
2 0.098295674 70 nips-2003-Fast Algorithms for Large-State-Space HMMs with Applications to Web Usage Analysis
Author: Pedro F. Felzenszwalb, Daniel P. Huttenlocher, Jon M. Kleinberg
Abstract: In applying Hidden Markov Models to the analysis of massive data streams, it is often necessary to use an artificially reduced set of states; this is due in large part to the fact that the basic HMM estimation algorithms have a quadratic dependence on the size of the state set. We present algorithms that reduce this computational bottleneck to linear or near-linear time, when the states can be embedded in an underlying grid of parameters. This type of state representation arises in many domains; in particular, we show an application to traffic analysis at a high-volume Web site. 1
3 0.070807546 119 nips-2003-Local Phase Coherence and the Perception of Blur
Author: Zhou Wang, Eero P. Simoncelli
Abstract: unkown-abstract
4 0.056739435 91 nips-2003-Inferring State Sequences for Non-linear Systems with Embedded Hidden Markov Models
Author: Radford M. Neal, Matthew J. Beal, Sam T. Roweis
Abstract: We describe a Markov chain method for sampling from the distribution of the hidden state sequence in a non-linear dynamical system, given a sequence of observations. This method updates all states in the sequence simultaneously using an embedded Hidden Markov Model (HMM). An update begins with the creation of “pools” of candidate states at each time. We then define an embedded HMM whose states are indexes within these pools. Using a forward-backward dynamic programming algorithm, we can efficiently choose a state sequence with the appropriate probabilities from the exponentially large number of state sequences that pass through states in these pools. We illustrate the method in a simple one-dimensional example, and in an example showing how an embedded HMM can be used to in effect discretize the state space without any discretization error. We also compare the embedded HMM to a particle smoother on a more substantial problem of inferring human motion from 2D traces of markers. 1
5 0.049794707 179 nips-2003-Sparse Representation and Its Applications in Blind Source Separation
Author: Yuanqing Li, Shun-ichi Amari, Sergei Shishkin, Jianting Cao, Fanji Gu, Andrzej S. Cichocki
Abstract: In this paper, sparse representation (factorization) of a data matrix is first discussed. An overcomplete basis matrix is estimated by using the K−means method. We have proved that for the estimated overcomplete basis matrix, the sparse solution (coefficient matrix) with minimum l1 −norm is unique with probability of one, which can be obtained using a linear programming algorithm. The comparisons of the l1 −norm solution and the l0 −norm solution are also presented, which can be used in recoverability analysis of blind source separation (BSS). Next, we apply the sparse matrix factorization approach to BSS in the overcomplete case. Generally, if the sources are not sufficiently sparse, we perform blind separation in the time-frequency domain after preprocessing the observed data using the wavelet packets transformation. Third, an EEG experimental data analysis example is presented to illustrate the usefulness of the proposed approach and demonstrate its performance. Two almost independent components obtained by the sparse representation method are selected for phase synchronization analysis, and their periods of significant phase synchronization are found which are related to tasks. Finally, concluding remarks review the approach and state areas that require further study. 1
6 0.04323652 37 nips-2003-Automatic Annotation of Everyday Movements
7 0.043131836 64 nips-2003-Estimating Internal Variables and Paramters of a Learning Agent by a Particle Filter
8 0.040971603 176 nips-2003-Sequential Bayesian Kernel Regression
9 0.036163867 162 nips-2003-Probabilistic Inference of Speech Signals from Phaseless Spectrograms
10 0.033996195 187 nips-2003-Training a Quantum Neural Network
11 0.030678982 33 nips-2003-Approximate Planning in POMDPs with Macro-Actions
12 0.029589314 85 nips-2003-Human and Ideal Observers for Detecting Image Curves
13 0.029284947 167 nips-2003-Robustness in Markov Decision Problems with Uncertain Transition Matrices
14 0.027941009 93 nips-2003-Information Dynamics and Emergent Computation in Recurrent Circuits of Spiking Neurons
15 0.027173216 20 nips-2003-All learning is Local: Multi-agent Learning in Global Reward Games
16 0.026845457 125 nips-2003-Maximum Likelihood Estimation of a Stochastic Integrate-and-Fire Neural Model
17 0.025595488 78 nips-2003-Gaussian Processes in Reinforcement Learning
18 0.025463197 116 nips-2003-Linear Program Approximations for Factored Continuous-State Markov Decision Processes
19 0.025055913 186 nips-2003-Towards Social Robots: Automatic Evaluation of Human-Robot Interaction by Facial Expression Classification
20 0.02402835 177 nips-2003-Simplicial Mixtures of Markov Chains: Distributed Modelling of Dynamic User Profiles
topicId topicWeight
[(0, -0.093), (1, 0.046), (2, 0.026), (3, -0.003), (4, -0.037), (5, -0.0), (6, 0.059), (7, 0.007), (8, -0.001), (9, 0.027), (10, 0.021), (11, -0.047), (12, -0.022), (13, 0.026), (14, 0.017), (15, -0.019), (16, -0.001), (17, -0.015), (18, 0.001), (19, -0.028), (20, -0.008), (21, 0.032), (22, 0.022), (23, -0.057), (24, -0.087), (25, -0.062), (26, -0.089), (27, 0.008), (28, -0.017), (29, 0.029), (30, -0.064), (31, 0.033), (32, -0.007), (33, -0.063), (34, -0.068), (35, 0.008), (36, -0.01), (37, -0.224), (38, -0.076), (39, -0.034), (40, 0.094), (41, 0.083), (42, 0.161), (43, -0.007), (44, 0.045), (45, -0.006), (46, -0.122), (47, -0.012), (48, -0.057), (49, -0.007)]
simIndex simValue paperId paperTitle
same-paper 1 0.93025446 123 nips-2003-Markov Models for Automated ECG Interval Analysis
Author: Nicholas P. Hughes, Lionel Tarassenko, Stephen J. Roberts
Abstract: We examine the use of hidden Markov and hidden semi-Markov models for automatically segmenting an electrocardiogram waveform into its constituent waveform features. An undecimated wavelet transform is used to generate an overcomplete representation of the signal that is more appropriate for subsequent modelling. We show that the state durations implicit in a standard hidden Markov model are ill-suited to those of real ECG features, and we investigate the use of hidden semi-Markov models for improved state duration modelling. 1
2 0.64028221 70 nips-2003-Fast Algorithms for Large-State-Space HMMs with Applications to Web Usage Analysis
Author: Pedro F. Felzenszwalb, Daniel P. Huttenlocher, Jon M. Kleinberg
Abstract: In applying Hidden Markov Models to the analysis of massive data streams, it is often necessary to use an artificially reduced set of states; this is due in large part to the fact that the basic HMM estimation algorithms have a quadratic dependence on the size of the state set. We present algorithms that reduce this computational bottleneck to linear or near-linear time, when the states can be embedded in an underlying grid of parameters. This type of state representation arises in many domains; in particular, we show an application to traffic analysis at a high-volume Web site. 1
3 0.5261088 75 nips-2003-From Algorithmic to Subjective Randomness
Author: Thomas L. Griffiths, Joshua B. Tenenbaum
Abstract: We explore the phenomena of subjective randomness as a case study in understanding how people discover structure embedded in noise. We present a rational account of randomness perception based on the statistical problem of model selection: given a stimulus, inferring whether the process that generated it was random or regular. Inspired by the mathematical definition of randomness given by Kolmogorov complexity, we characterize regularity in terms of a hierarchy of automata that augment a finite controller with different forms of memory. We find that the regularities detected in binary sequences depend upon presentation format, and that the kinds of automata that can identify these regularities are informative about the cognitive processes engaged by different formats. 1
4 0.49152493 119 nips-2003-Local Phase Coherence and the Perception of Blur
Author: Zhou Wang, Eero P. Simoncelli
Abstract: unkown-abstract
5 0.46631277 91 nips-2003-Inferring State Sequences for Non-linear Systems with Embedded Hidden Markov Models
Author: Radford M. Neal, Matthew J. Beal, Sam T. Roweis
Abstract: We describe a Markov chain method for sampling from the distribution of the hidden state sequence in a non-linear dynamical system, given a sequence of observations. This method updates all states in the sequence simultaneously using an embedded Hidden Markov Model (HMM). An update begins with the creation of “pools” of candidate states at each time. We then define an embedded HMM whose states are indexes within these pools. Using a forward-backward dynamic programming algorithm, we can efficiently choose a state sequence with the appropriate probabilities from the exponentially large number of state sequences that pass through states in these pools. We illustrate the method in a simple one-dimensional example, and in an example showing how an embedded HMM can be used to in effect discretize the state space without any discretization error. We also compare the embedded HMM to a particle smoother on a more substantial problem of inferring human motion from 2D traces of markers. 1
6 0.46413884 179 nips-2003-Sparse Representation and Its Applications in Blind Source Separation
7 0.43756825 116 nips-2003-Linear Program Approximations for Factored Continuous-State Markov Decision Processes
8 0.42770055 89 nips-2003-Impact of an Energy Normalization Transform on the Performance of the LF-ASD Brain Computer Interface
9 0.37254402 167 nips-2003-Robustness in Markov Decision Problems with Uncertain Transition Matrices
10 0.34504417 196 nips-2003-Wormholes Improve Contrastive Divergence
11 0.33978686 6 nips-2003-A Fast Multi-Resolution Method for Detection of Significant Spatial Disease Clusters
12 0.33175719 25 nips-2003-An MCMC-Based Method of Comparing Connectionist Models in Cognitive Science
13 0.28142104 64 nips-2003-Estimating Internal Variables and Paramters of a Learning Agent by a Particle Filter
14 0.27724937 184 nips-2003-The Diffusion-Limited Biochemical Signal-Relay Channel
15 0.2760095 163 nips-2003-Probability Estimates for Multi-Class Classification by Pairwise Coupling
16 0.26575047 162 nips-2003-Probabilistic Inference of Speech Signals from Phaseless Spectrograms
17 0.25911134 13 nips-2003-A Neuromorphic Multi-chip Model of a Disparity Selective Complex Cell
18 0.25726995 90 nips-2003-Increase Information Transfer Rates in BCI by CSP Extension to Multi-class
19 0.25069758 68 nips-2003-Eye Movements for Reward Maximization
20 0.24525125 38 nips-2003-Autonomous Helicopter Flight via Reinforcement Learning
topicId topicWeight
[(0, 0.052), (11, 0.018), (29, 0.01), (30, 0.03), (35, 0.103), (53, 0.06), (68, 0.01), (71, 0.056), (76, 0.043), (77, 0.337), (82, 0.011), (85, 0.049), (91, 0.076), (93, 0.011)]
simIndex simValue paperId paperTitle
same-paper 1 0.7980122 123 nips-2003-Markov Models for Automated ECG Interval Analysis
Author: Nicholas P. Hughes, Lionel Tarassenko, Stephen J. Roberts
Abstract: We examine the use of hidden Markov and hidden semi-Markov models for automatically segmenting an electrocardiogram waveform into its constituent waveform features. An undecimated wavelet transform is used to generate an overcomplete representation of the signal that is more appropriate for subsequent modelling. We show that the state durations implicit in a standard hidden Markov model are ill-suited to those of real ECG features, and we investigate the use of hidden semi-Markov models for improved state duration modelling. 1
2 0.68970376 121 nips-2003-Log-Linear Models for Label Ranking
Author: Ofer Dekel, Yoram Singer, Christopher D. Manning
Abstract: Label ranking is the task of inferring a total order over a predefined set of labels for each given instance. We present a general framework for batch learning of label ranking functions from supervised data. We assume that each instance in the training data is associated with a list of preferences over the label-set, however we do not assume that this list is either complete or consistent. This enables us to accommodate a variety of ranking problems. In contrast to the general form of the supervision, our goal is to learn a ranking function that induces a total order over the entire set of labels. Special cases of our setting are multilabel categorization and hierarchical classification. We present a general boosting-based learning algorithm for the label ranking problem and prove a lower bound on the progress of each boosting iteration. The applicability of our approach is demonstrated with a set of experiments on a large-scale text corpus. 1
3 0.4315443 91 nips-2003-Inferring State Sequences for Non-linear Systems with Embedded Hidden Markov Models
Author: Radford M. Neal, Matthew J. Beal, Sam T. Roweis
Abstract: We describe a Markov chain method for sampling from the distribution of the hidden state sequence in a non-linear dynamical system, given a sequence of observations. This method updates all states in the sequence simultaneously using an embedded Hidden Markov Model (HMM). An update begins with the creation of “pools” of candidate states at each time. We then define an embedded HMM whose states are indexes within these pools. Using a forward-backward dynamic programming algorithm, we can efficiently choose a state sequence with the appropriate probabilities from the exponentially large number of state sequences that pass through states in these pools. We illustrate the method in a simple one-dimensional example, and in an example showing how an embedded HMM can be used to in effect discretize the state space without any discretization error. We also compare the embedded HMM to a particle smoother on a more substantial problem of inferring human motion from 2D traces of markers. 1
4 0.42626223 72 nips-2003-Fast Feature Selection from Microarray Expression Data via Multiplicative Large Margin Algorithms
Author: Claudio Gentile
Abstract: New feature selection algorithms for linear threshold functions are described which combine backward elimination with an adaptive regularization method. This makes them particularly suitable to the classification of microarray expression data, where the goal is to obtain accurate rules depending on few genes only. Our algorithms are fast and easy to implement, since they center on an incremental (large margin) algorithm which allows us to avoid linear, quadratic or higher-order programming methods. We report on preliminary experiments with five known DNA microarray datasets. These experiments suggest that multiplicative large margin algorithms tend to outperform additive algorithms (such as SVM) on feature selection tasks. 1
5 0.42509833 122 nips-2003-Margin Maximizing Loss Functions
Author: Saharon Rosset, Ji Zhu, Trevor J. Hastie
Abstract: Margin maximizing properties play an important role in the analysis of classi£cation models, such as boosting and support vector machines. Margin maximization is theoretically interesting because it facilitates generalization error analysis, and practically interesting because it presents a clear geometric interpretation of the models being built. We formulate and prove a suf£cient condition for the solutions of regularized loss functions to converge to margin maximizing separators, as the regularization vanishes. This condition covers the hinge loss of SVM, the exponential loss of AdaBoost and logistic regression loss. We also generalize it to multi-class classi£cation problems, and present margin maximizing multiclass versions of logistic regression and support vector machines. 1
6 0.42076418 146 nips-2003-Online Learning of Non-stationary Sequences
7 0.42019838 189 nips-2003-Tree-structured Approximations by Expectation Propagation
8 0.41842097 116 nips-2003-Linear Program Approximations for Factored Continuous-State Markov Decision Processes
9 0.41661313 158 nips-2003-Policy Search by Dynamic Programming
10 0.41592002 50 nips-2003-Denoising and Untangling Graphs Using Degree Priors
11 0.41576678 78 nips-2003-Gaussian Processes in Reinforcement Learning
12 0.4153325 20 nips-2003-All learning is Local: Multi-agent Learning in Global Reward Games
13 0.41457739 101 nips-2003-Large Margin Classifiers: Convex Loss, Low Noise, and Convergence Rates
14 0.41345665 34 nips-2003-Approximate Policy Iteration with a Policy Language Bias
15 0.41322884 100 nips-2003-Laplace Propagation
16 0.41138217 113 nips-2003-Learning with Local and Global Consistency
17 0.40949473 70 nips-2003-Fast Algorithms for Large-State-Space HMMs with Applications to Web Usage Analysis
18 0.40710706 33 nips-2003-Approximate Planning in POMDPs with Macro-Actions
19 0.40640497 109 nips-2003-Learning a Rare Event Detection Cascade by Direct Feature Selection
20 0.40618193 69 nips-2003-Factorization with Uncertainty and Missing Data: Exploiting Temporal Coherence