用以建構因果網路與檢視其特徵的演算法

Abstract

因果網路圖可以用來表示變數或事件之間的因果關係，此類圖由來已久， 所以用來替因果網路圖建立模型，或建構網路圖的演算法早已所在多有，例如包含馬可夫網路圖，貝氏網路圖，布林網路圖等。 然而隨著科技的進步和新測量方法的發明，產生了新形式的資料， 因果網路圖的研究也需要新的演算法協助，而我們的研究則針對因果網路建構及特徵辨識的演算法上。 第一部份的研究是設計新的演算法以比較一對隨時間而變化的變數，藉以找出兩者之間的關聯性，而比較的方式則是根據兩時間序列局部的高低排列方式。 我們採用區段樹的資料結構，並加入新的指標，能有效地從整段時間序列中擷取和比較局部的高低排列。 有了兩兩變數之間的關聯，就可以建構一個因果網路圖。 第二部份的研究則是想在因果網路中，刪除變數間的間接關聯，只保留直接的關聯。 我們將該問題模型化為一個最佳化的問題，證明該問題是NP-hard，並為這個問題提出了一個近似演算法。 第三部份的研究則是替因果網路圖做特徵的辨識，辨識的方式則是找該圖的穩定狀態。 在布林網路圖中，則是找該圖的獨身吸引子，而我們又只有著重在特殊的布林網路，也就是：呈現類似樹狀的結構布林網路，即該網路有一定範圍內的樹寬。 而對於不同的布林函數：AND/OR 布林函數、巢狀串聯函數和一般的布林函數，我們提出各自關於參數化複雜度的分析和演算法。

The causal network is a common representation showing causal relations between variables or events. There have been different algorithms to model and to construct causal networks such as Markov networks, Bayesian Networks, Boolean Networks, etc. With the advance of technologies and new types of data, new algorithms are needed for causal networks. We focus on the algorithms to construct and to characterize causal networks. The rst study is to design new algorithms to compare a pair of temporal variables in terms of local rankings to establish association. We adapt the segment tree data structure by adding new pointers to extract and compare local rankings efficiently. The second is to eliminate indirect relations in a causal network. We model the problem as an optimization problem and prove its NP-hardness. We also give an approximation algorithm for this problem. The third part is to characterize causal networks by finding their stable states in terms of singleton attractors in Boolean networks. We focus on AND/OR Boolean networks with bounded treewidth and give a fixed-parameter algorithm.