請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/82384完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 王奕翔(I-Hsiang Wang) | |
| dc.contributor.author | Jia-Wei Lin | en |
| dc.contributor.author | 林家緯 | zh_TW |
| dc.date.accessioned | 2022-11-25T07:30:05Z | - |
| dc.date.available | 2023-11-29 | |
| dc.date.copyright | 2021-12-14 | |
| dc.date.issued | 2021 | |
| dc.date.submitted | 2021-12-09 | |
| dc.identifier.citation | References [1] B. L. Bars, P. Humbert, A. Kalogeratos, and N. Vayatis. Learning the piecewise constant graph structure of a varying Ising model. In International Conference of Machine Learning. 2020. [2] J. Bento and A. Montanari. Which graphical models are difficult to learn? In Advances in Neural Information Processing Systems, pages 1303–1311. 2009. [3] G. Bresler and M. Karzand. Learning a treestructured Ising model in order to make predictions. In Annals of Statistics, pages 713–737. 2020. [4] C. Daskalakis, N. Dikkala, and G. Kamath. Testing Ising models. In IEEE Transaction of Information Theory, pages 6829–6852. 2019. [5] F. Fazayeli and A. Banerjee. Generalized direct change estimation in Ising model structure. In International Conference of Machine Learning, pages 2281–2290. 2016. [6] G. Fellouris, E. Bayraktar, and L. Lai. Efficient byzantine sequential change detection. In IEEE Transactions on Information Theory, page 3346–3360. 2018. [7] A. Gangrade, B. Nazer, and V. Saligrama. Limits on testing structural changes in Ising models. In Advances in Neural Information Processing Systems. 2020. [8] Y. Huang, Y. Huang, and S. Lin. Asymptotic optimality in byzantine distributed quickest change detection. In IEEE Transactions on Information Theory, pages 5942 – 5962. 2021. [9] A. Katiyar, V. Shah, and C. Caramanis. Robust estimation of tree-structured Ising models. In arXiv preprint. 2020. [10] D. Koller and N. Friedman. In Probabilistic Graphical Models: Principles and Techniques. 2009. [11] K. Liu, R. Zhang, and Y. Mei. Scalable sumshrinkage schemes for distributed monitoring large scale data streams. In Statistica Sinica, pages 1–22. 2019. [12] G. Lorden. Procedures for reacting to a change in distribution. In The Annals of Mathematical Statistics, pages 1897–1908. 1971. [13] G. Lorden and M. Pollak. Sequential changepoint detection procedures that are nearly optimal and computationally simple. In Sequential Analysis, pages 476–512. 2008. [14] Y. Mei. Sequential changepoint detection when unknown parameters are present in the prechange distribution. In Annals of Statistics, pages 92–122. 2006. [15] Y. Mei. Efficient scalable schemes for monitoring a large number of data streams. In Biometrika, pages 419–433. 2010. [16] G. Moustakides. Optimal stopping times for detecting changes in distributions. In Annals of Statistics, pages 1379–1387. 1986. [17] E. Page. Continuous inspection schemes. In Biometrika, pages 100–115. 1954. [18] M. Pollak. Optimal detection of a change in distribution. In Annals of Statistics, pages 206–227. 1985. [19] M. Pollak and D. Siegmund. Approximations to the expected sample size of certain sequential tests. In Annals of Statistics, pages 1267–1282. 1975. [20] A. Shiryaev. On optimum methods in quickest detection problems. In Theory of Probability and its Applications, pages 22–46. 1963. [21] D. Siegmund and E. Venkatraman. Using the generalized likelihood ratio statistics for sequential detection of a changepoint. In Annals of Statistics, pages 255–271. 1995. [22] N. Suh, R. Zhang, and Y. Mei. Adaptive online monitoring of the Ising model. In Annual Allerton Conference on Communication, Control, and Computing. 2019. [23] J. Unnikrishnan, V. Veeravalli, and S. Meyn. Minimax robust quickest change detection. In IEEE Transaction of Information Theory, pages 1604–1614. 2011. [24] V. V. Veeravalli and T. Banerjee. Quickest change detection. In Academic Press Library in Signal Processing: Array and Statistical Signal Processing, pages 209– 256. 2013. [25] M. Wainwright and M. Jordan. Graphical models, exponential families, and variational inference. In Foundations and Trends in Machine Learning, pages 1–305. 2008. [26] L. Xie, Y. Xie, and G. V. Moustakides. Sequential subspace change point detection. In Sequential Analysis, pages 307–335. 2020. [27] L. Xie, S. Zou, Y. Xie, and V. Veeravalli. Sequential (quickest) change detection: Classical results and new directions. In IEEE Journal on Selected Areas in Information Theory. 2021. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/82384 | - |
| dc.description.abstract | 本篇碩士論文在探討具有相關性的高維機率分布發生結構變異的最快速變化偵測問題。我們假設網路上蒐集的資料是基於易辛模型且在發生變化前後，資料的機率分布唯一的差異是易辛模型中的結構。在這樣的假設底下，我們發現此問題與伯努利的最快速變化偵測問題高度相關，甚至當我們適當強化易辛模型的假設，相應的伯努利最快速變化偵測問題將被大大簡化。正因如此，我們能夠提出了一個在新增多條邊的簡化易辛模型問題上，只需要知道變化前網路結構，就能夠達到最佳的最壞平均檢測延遲與平均時間至錯誤警告平衡的方法。在減少一條邊的簡化易辛模型問題上，我們雖然沒能夠在只知曉變化前網路結構下，做到最佳的最壞平均檢測延遲與平均時間至錯誤警告平衡，但是我們的方法從文獻中另一個評量標標準來看，已經達到最優。由於上述提出的方法在實際執行上複雜度較高，我們進一步利用了易辛模型的關聯性傳播特性，提出只需從網路上蒐集少數幾個節點的資料，就能夠順利偵測變化的方法。由於節點的選擇將會影響偵測的表現，我們將選擇解點的問題寫成一個最佳化問題，並提出解決此問題的演算法。 | zh_TW |
| dc.description.provenance | Made available in DSpace on 2022-11-25T07:30:05Z (GMT). No. of bitstreams: 1 U0001-0112202115540700.pdf: 1726786 bytes, checksum: 5d9ac465b826c550ecb53d48075141e4 (MD5) Previous issue date: 2021 | en |
| dc.description.tableofcontents | Contents Page Verification Letter from the Oral Examination Committee i Acknowledgements iii 摘要 v Abstract vii Contents ix List of Figures xiii Denotation xv Chapter 1 Introduction 1 1.1 Contribution of Thesis . . . . . . . . . . . . . . . . . . . . . . . . . 5 Chapter 2 Backgrounds 9 2.1 Quickest Change Detection (QCD) . . . . . . . . . . . . . . . . . . 9 2.1.1 Composite QCD . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.1.1.1 Postchange Unknown QCD . . . . . . . . . . . . . . 14 2.1.1.2 Prechange Unknown QCD . . . . . . . . . . . . . . . 15 2.1.1.3 Pre/Postchange Unknown QCD . . . . . . . . . . . . 16 2.2 Undirected Graphical Models . . . . . . . . . . . . . . . . . . . . . 17 2.2.1 Ising Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.2.1.1 Ising Model in a Forest . . . . . . . . . . . . . . . . . 20 Chapter 3 QCD for Edge Increased in Ising Models on a Forest 23 3.1 One Edge Increased/One Component Decreased with Known PreChange Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.1.1 Problem Setting . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.1.2 Proposed Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.2 One Edge Increased/One Component Decreased with only Structure of PreChange Distribution . . . . . . . . . . . . . . . . . . . . . . . 26 3.2.1 Problem Setting . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.2.2 Proposed Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.2.3 Important Property . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.2.4 Performance of Proposed Algorithm . . . . . . . . . . . . . . . . . 28 3.3 Multiple EdgeIncreased/OneComponentDecreased with only Structure of PreChange Distribution . . . . . . . . . . . . . . . . . . . . 30 3.3.1 Problem Setting . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.3.2 Proposed Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.3.3 Performance of Proposed Algorithm . . . . . . . . . . . . . . . . . 31 3.4 Representative Procedure for Edge Increased/Component Decreased . 34 3.4.1 Proposed Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.4.2 Performance for Proposed Algorithm . . . . . . . . . . . . . . . . . 36 3.4.3 Choosing the Representatives . . . . . . . . . . . . . . . . . . . . . 38 3.5 Alternatives to Generalized Likelihoods for Shifts in Bernoulli . . . . 40 3.5.1 Review of Bernoulli Generalized Likelihood Statistic . . . . . . . . 40 3.5.2 Bernoulli Mixture Likelihood Statistic . . . . . . . . . . . . . . . . 41 3.5.3 Consecutive Procedure . . . . . . . . . . . . . . . . . . . . . . . . 42 3.5.4 Fixed Window Procedure . . . . . . . . . . . . . . . . . . . . . . . 45 3.6 One Edge Increase in General Ising Models and Implications . . . . . 48 3.6.1 Problem Setting . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.6.2 Extended Algorithm from Subsection3.2.2 and its Performance . . . 49 3.6.3 Implications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.7 Some Lemmas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 Chapter 4 QCD for Edge Decreased in Ising Models on a Forest 53 4.1 One Edge Decreased/One Component Increased with Known Prechange Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 4.1.1 Problem Setting . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 4.1.2 Proposed Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 54 4.1.3 Performance of Algorithm . . . . . . . . . . . . . . . . . . . . . . 55 4.2 One Edge Decreased/One Component Increased with only Sign of Prechange Distribution . . . . . . . . . . . . . . . . . . . . . . . . 57 4.2.1 Problem Setting . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 4.2.2 Proposed Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 58 4.2.3 Performance of Algorithm . . . . . . . . . . . . . . . . . . . . . . 59 4.3 Representative Procedure for One Edge Decreased/One Component Increased . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 4.3.1 Proposed Procedure . . . . . . . . . . . . . . . . . . . . . . . . . . 62 4.3.2 Performance of Algorithm . . . . . . . . . . . . . . . . . . . . . . 63 4.3.3 Choosing the Representatives . . . . . . . . . . . . . . . . . . . . . 65 4.4 One Edge Decreased in General Ising Models and Implications . . . 67 4.4.1 Extension from Section4.1 . . . . . . . . . . . . . . . . . . . . . . 67 4.4.2 Discussion of Extension from Section4.2 . . . . . . . . . . . . . . . 68 4.5 Some Lemmas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 Chapter 5 Conclusion 71 5.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 5.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 References 75 | |
| dc.language.iso | en | |
| dc.subject | 易辛模型 | zh_TW |
| dc.subject | 最快速變化偵測 | zh_TW |
| dc.subject | Ising Model | en |
| dc.subject | Quickest Change Detection | en |
| dc.title | 結構變動之易辛模型的最快速變化偵測 | zh_TW |
| dc.title | Quickest Change Detection for Structural Changing Ising Model | en |
| dc.date.schoolyear | 110-1 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 林士駿(Hsin-Tsai Liu),黃昱智(Chih-Yang Tseng) | |
| dc.subject.keyword | 最快速變化偵測,易辛模型, | zh_TW |
| dc.subject.keyword | Quickest Change Detection,Ising Model, | en |
| dc.relation.page | 78 | |
| dc.identifier.doi | 10.6342/NTU202104499 | |
| dc.rights.note | 同意授權(全球公開) | |
| dc.date.accepted | 2021-12-09 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 電信工程學研究所 | zh_TW |
| dc.date.embargo-lift | 2023-11-29 | - |
| 顯示於系所單位： | 電信工程學研究所 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| U0001-0112202115540700.pdf | 1.69 MB | Adobe PDF | 檢視/開啟 |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。