結構變動之易辛模型的最快速變化偵測

Abstract

本篇碩士論文在探討具有相關性的高維機率分布發生結構變異的最快速變化偵測問題。我們假設網路上蒐集的資料是基於易辛模型且在發生變化前後，資料的機率分布唯一的差異是易辛模型中的結構。在這樣的假設底下，我們發現此問題與伯努利的最快速變化偵測問題高度相關，甚至當我們適當強化易辛模型的假設，相應的伯努利最快速變化偵測問題將被大大簡化。正因如此，我們能夠提出了一個在新增多條邊的簡化易辛模型問題上，只需要知道變化前網路結構，就能夠達到最佳的最壞平均檢測延遲與平均時間至錯誤警告平衡的方法。在減少一條邊的簡化易辛模型問題上，我們雖然沒能夠在只知曉變化前網路結構下，做到最佳的最壞平均檢測延遲與平均時間至錯誤警告平衡，但是我們的方法從文獻中另一個評量標標準來看，已經達到最優。由於上述提出的方法在實際執行上複雜度較高，我們進一步利用了易辛模型的關聯性傳播特性，提出只需從網路上蒐集少數幾個節點的資料，就能夠順利偵測變化的方法。由於節點的選擇將會影響偵測的表現，我們將選擇解點的問題寫成一個最佳化問題，並提出解決此問題的演算法。