On-line inference for multiple changepoint problems
We propose an on-line algorithm for exact filtering of multiple changepoint problems. This algorithm enables simulation from the true joint posterior distribution of the number and position of the changepoints for a class of changepoint models. The computational cost of this exact algorithm is quadr...
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
2007
|
| _version_ | 1797078693991940096 |
|---|---|
| author | Fearnhead, P Liu, Z |
| author_facet | Fearnhead, P Liu, Z |
| author_sort | Fearnhead, P |
| collection | OXFORD |
| description | We propose an on-line algorithm for exact filtering of multiple changepoint problems. This algorithm enables simulation from the true joint posterior distribution of the number and position of the changepoints for a class of changepoint models. The computational cost of this exact algorithm is quadratic in the number of observations. We further show how resampling ideas from particle filters can be used to reduce the computational cost to linear in the number of observations, at the expense of introducing small errors, and we propose two new, optimum resampling algorithms for this problem. One, a version of rejection control, allows the particle filter to choose the number of particles that are required at each time step automatically. The new resampling algorithms substantially outperform standard resampling algorithms on examples that we consider; and we demonstrate how the resulting particle filter is practicable for segmentation of human G+C content. © 2007 Royal Statistical Society. |
| first_indexed | 2024-03-07T00:35:23Z |
| format | Journal article |
| id | oxford-uuid:8136c820-980f-4129-ad03-9cababa5d0e1 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T00:35:23Z |
| publishDate | 2007 |
| record_format | dspace |
| spelling | oxford-uuid:8136c820-980f-4129-ad03-9cababa5d0e12022-03-26T21:28:52ZOn-line inference for multiple changepoint problemsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:8136c820-980f-4129-ad03-9cababa5d0e1EnglishSymplectic Elements at Oxford2007Fearnhead, PLiu, ZWe propose an on-line algorithm for exact filtering of multiple changepoint problems. This algorithm enables simulation from the true joint posterior distribution of the number and position of the changepoints for a class of changepoint models. The computational cost of this exact algorithm is quadratic in the number of observations. We further show how resampling ideas from particle filters can be used to reduce the computational cost to linear in the number of observations, at the expense of introducing small errors, and we propose two new, optimum resampling algorithms for this problem. One, a version of rejection control, allows the particle filter to choose the number of particles that are required at each time step automatically. The new resampling algorithms substantially outperform standard resampling algorithms on examples that we consider; and we demonstrate how the resulting particle filter is practicable for segmentation of human G+C content. © 2007 Royal Statistical Society. |
| spellingShingle | Fearnhead, P Liu, Z On-line inference for multiple changepoint problems |
| title | On-line inference for multiple changepoint problems |
| title_full | On-line inference for multiple changepoint problems |
| title_fullStr | On-line inference for multiple changepoint problems |
| title_full_unstemmed | On-line inference for multiple changepoint problems |
| title_short | On-line inference for multiple changepoint problems |
| title_sort | on line inference for multiple changepoint problems |
| work_keys_str_mv | AT fearnheadp onlineinferenceformultiplechangepointproblems AT liuz onlineinferenceformultiplechangepointproblems |