Ms.FPOP: A Fast Exact Segmentation Algorithm with a Multiscale Penalty
<p>Given a time series in <math><mrow><mrow><mi>R</mi></mrow><mi>n</mi></mrow></math> with a piecewise constant mean and independent noises, we propose an exact dynamic programming algorithm for minimizing a least-squares criterion wi...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Published: |
2024
|
| Subjects: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1852024962262499328 |
|---|---|
| author | Arnaud Liehrmann (10970682) |
| author2 | Guillem Rigaill (413775) |
| author2_role | author |
| author_facet | Arnaud Liehrmann (10970682) Guillem Rigaill (413775) |
| author_role | author |
| dc.creator.none.fl_str_mv | Arnaud Liehrmann (10970682) Guillem Rigaill (413775) |
| dc.date.none.fl_str_mv | 2024-11-22T21:20:15Z |
| dc.identifier.none.fl_str_mv | 10.6084/m9.figshare.27629156.v2 |
| dc.relation.none.fl_str_mv | https://figshare.com/articles/dataset/Ms_FPOP_a_fast_exact_segmentation_algorithm_with_a_multiscale_penalty/27629156 |
| dc.rights.none.fl_str_mv | CC BY 4.0 info:eu-repo/semantics/openAccess |
| dc.subject.none.fl_str_mv | Biochemistry Microbiology Cell Biology Neuroscience Biotechnology Immunology Developmental Biology Cancer Infectious Diseases Computational Biology Mathematical Sciences not elsewhere classified Chemical Sciences not elsewhere classified Changepoint detection Discrete optimization Dynamic programming Functional pruning Maximum likelihood inference Multiscale penalty |
| dc.title.none.fl_str_mv | Ms.FPOP: A Fast Exact Segmentation Algorithm with a Multiscale Penalty |
| dc.type.none.fl_str_mv | Dataset info:eu-repo/semantics/publishedVersion dataset |
| description | <p>Given a time series in <math><mrow><mrow><mi>R</mi></mrow><mi>n</mi></mrow></math> with a piecewise constant mean and independent noises, we propose an exact dynamic programming algorithm for minimizing a least-squares criterion with a multiscale penalty, favoring well-spread changepoints. This penalty was proposed by Verzelen et al. and achieves optimal rates for changepoint detection and changepoint localization in a non-asymptotic scenario. Our proposed algorithm, Multiscale Functional Pruning Optimal Partitioning (Ms.FPOP), extends functional pruning ideas presented in Rigaill and Maidstone et al. to multiscale penalties. For large signals (<math><mrow><mi>n</mi><mo>≥</mo><mrow><mrow><mn>10</mn></mrow></mrow><mn>5</mn></mrow></math>) with sparse changepoints, Ms.FPOP is shown empirically to be quasi-linear and faster than the Pruned Exact Linear Time (PELT) method of Killick et al. applied to the multiscale penalty of Verzelen et al. which exhibits quadratic slowdown in these cases. We propose an efficient implementation of Ms.FPOP coded in C++ interfaced with R that can segment profiles of up to <math><mrow><mi>n</mi><mo>=</mo><mrow><mrow><mn>10</mn></mrow></mrow><mn>6</mn></mrow></math> in a matter of seconds. Our algorithm works for slightly more general multiscale penalties. In particular, it allows a minimum segment length to be imposed. Using simple simulations we then show that where profiles are sufficiently large (<math><mrow><mi>n</mi><mo>≥</mo><mrow><mrow><mn>10</mn></mrow></mrow><mn>4</mn></mrow></math>), Ms.FPOP using the multiscale penalty of Verzelen et al. is typically more powerful than optimizing a least-squares criterion with the BIC penalty of Yao, a criterion that was shown by Fearnhead and Rigaill to perfom well across a wide range of scenarios. Supplementary materials for this article are available online.</p> |
| eu_rights_str_mv | openAccess |
| id | Manara_e00aee5eae562c26526eda39b773fe87 |
| identifier_str_mv | 10.6084/m9.figshare.27629156.v2 |
| network_acronym_str | Manara |
| network_name_str | ManaraRepo |
| oai_identifier_str | oai:figshare.com:article/27629156 |
| publishDate | 2024 |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| rights_invalid_str_mv | CC BY 4.0 |
| spelling | Ms.FPOP: A Fast Exact Segmentation Algorithm with a Multiscale PenaltyArnaud Liehrmann (10970682)Guillem Rigaill (413775)BiochemistryMicrobiologyCell BiologyNeuroscienceBiotechnologyImmunologyDevelopmental BiologyCancerInfectious DiseasesComputational BiologyMathematical Sciences not elsewhere classifiedChemical Sciences not elsewhere classifiedChangepoint detectionDiscrete optimizationDynamic programmingFunctional pruningMaximum likelihood inferenceMultiscale penalty<p>Given a time series in <math><mrow><mrow><mi>R</mi></mrow><mi>n</mi></mrow></math> with a piecewise constant mean and independent noises, we propose an exact dynamic programming algorithm for minimizing a least-squares criterion with a multiscale penalty, favoring well-spread changepoints. This penalty was proposed by Verzelen et al. and achieves optimal rates for changepoint detection and changepoint localization in a non-asymptotic scenario. Our proposed algorithm, Multiscale Functional Pruning Optimal Partitioning (Ms.FPOP), extends functional pruning ideas presented in Rigaill and Maidstone et al. to multiscale penalties. For large signals (<math><mrow><mi>n</mi><mo>≥</mo><mrow><mrow><mn>10</mn></mrow></mrow><mn>5</mn></mrow></math>) with sparse changepoints, Ms.FPOP is shown empirically to be quasi-linear and faster than the Pruned Exact Linear Time (PELT) method of Killick et al. applied to the multiscale penalty of Verzelen et al. which exhibits quadratic slowdown in these cases. We propose an efficient implementation of Ms.FPOP coded in C++ interfaced with R that can segment profiles of up to <math><mrow><mi>n</mi><mo>=</mo><mrow><mrow><mn>10</mn></mrow></mrow><mn>6</mn></mrow></math> in a matter of seconds. Our algorithm works for slightly more general multiscale penalties. In particular, it allows a minimum segment length to be imposed. Using simple simulations we then show that where profiles are sufficiently large (<math><mrow><mi>n</mi><mo>≥</mo><mrow><mrow><mn>10</mn></mrow></mrow><mn>4</mn></mrow></math>), Ms.FPOP using the multiscale penalty of Verzelen et al. is typically more powerful than optimizing a least-squares criterion with the BIC penalty of Yao, a criterion that was shown by Fearnhead and Rigaill to perfom well across a wide range of scenarios. Supplementary materials for this article are available online.</p>2024-11-22T21:20:15ZDatasetinfo:eu-repo/semantics/publishedVersiondataset10.6084/m9.figshare.27629156.v2https://figshare.com/articles/dataset/Ms_FPOP_a_fast_exact_segmentation_algorithm_with_a_multiscale_penalty/27629156CC BY 4.0info:eu-repo/semantics/openAccessoai:figshare.com:article/276291562024-11-22T21:20:15Z |
| spellingShingle | Ms.FPOP: A Fast Exact Segmentation Algorithm with a Multiscale Penalty Arnaud Liehrmann (10970682) Biochemistry Microbiology Cell Biology Neuroscience Biotechnology Immunology Developmental Biology Cancer Infectious Diseases Computational Biology Mathematical Sciences not elsewhere classified Chemical Sciences not elsewhere classified Changepoint detection Discrete optimization Dynamic programming Functional pruning Maximum likelihood inference Multiscale penalty |
| status_str | publishedVersion |
| title | Ms.FPOP: A Fast Exact Segmentation Algorithm with a Multiscale Penalty |
| title_full | Ms.FPOP: A Fast Exact Segmentation Algorithm with a Multiscale Penalty |
| title_fullStr | Ms.FPOP: A Fast Exact Segmentation Algorithm with a Multiscale Penalty |
| title_full_unstemmed | Ms.FPOP: A Fast Exact Segmentation Algorithm with a Multiscale Penalty |
| title_short | Ms.FPOP: A Fast Exact Segmentation Algorithm with a Multiscale Penalty |
| title_sort | Ms.FPOP: A Fast Exact Segmentation Algorithm with a Multiscale Penalty |
| topic | Biochemistry Microbiology Cell Biology Neuroscience Biotechnology Immunology Developmental Biology Cancer Infectious Diseases Computational Biology Mathematical Sciences not elsewhere classified Chemical Sciences not elsewhere classified Changepoint detection Discrete optimization Dynamic programming Functional pruning Maximum likelihood inference Multiscale penalty |