comp_pat
Description:
Compares a (learned) chain graph pattern to the (supposed) true pattern. The two patterns should have the same vertex set in order for the function to return a meaningful result.
Usage:
comp_pat(truepat, pat)
Arguments:
| truepat | the adjacency matrix of the true pattern. |
| pat | the adjacency matrix of the pattern to be compared with the true one. |
Details:
The function simply compares two np.arrays and finds the differences in provided patterns. It also computers error measures(TPR, FPR, ACC, etc)
Value:
| trueArrows | Number of true arrows |
| missingArrows | Number of missing arrows in the learned pattern |
| extraArrows | Number of extra arrows in the learned pattern |
| shd | Structural Hamming Distance |
| tpr | TPR |
| tdr | TDR |
| fpr | FPR |
| acc | Accuracy |
Example:
matrix1 = np.array([[1, 1, 1],[0, 0, 0],[0, 0, 0]])
matrix2 = np.array([[0, 0, 0],[0, 0, 0],[1, 1, 1]])
resultDict = comp_pat(matrix1, matrix2)
References:
Tsamardinos, I., Brown, L., and Aliferis, C. (2006). The max-min hill-climbing Bayesian network structure learning algorithm. Mach. Learn., 65(1):31-78.
comp_skel
Description:
Compares a (learned) chain graph skeleton to the (supposed) true skeleton. The two patterns should have the same vertex set in order for the function to return a meaningful result.
Usage:
comp_skel(trueskel, skel)
Arguments:
| trueskel | the adjacency matrix of the true skeleton. |
| skel | the adjacency matrix of the skeleton to be compared with the true one. |
Details:
The function simply compares two np.arrays and finds the differences in provided skeletons. It also computers error measures(TPR, FPR, ACC, etc)
Value:
| numTrueEdges | Number of true edges |
| missingEdges | Number of missing edges in the learned skeleton |
| extraEdges | Number of extra edges in the learned skeleton |
| shd | Structural Hamming Distance |
| tpr | TPR |
| tdr | TDR |
| fpr | FPR |
| acc | Accuracy |
Example:
matrix1 = np.array([[0, 1, 1],[1, 0, 1],[0, 1, 1]])
matrix2 = np.array([[0, 1, 1],[1, 0, 1],[0, 1, 1]])
resultDict = comp_skeleton(matrix1, matrix2)
References:
Tsamardinos, I., Brown, L., and Aliferis, C. (2006). The max-min hill-climbing Bayesian network structure learning algorithm. Mach. Learn., 65(1):31-78.
is_chain_graph
Description:
Checks if a given graph is a chain graph.
Usage:
is_chain_graph(adj_matrix)
Arguments:
| adj_matrix | the adjacency matrix of the graph. |
Details:
The function tries to find a partially directed cycle. If found, it is not a chain graph
Value:
| Result | True/False |
| cycle_path | If there is a cycle, it is returned as a list of vertices |
Example:
matrix1 = np.array([[0, 1, 1],[1, 0, 1],[0, 1, 1]])
result,cycle = is_chain_graph(matrix1)
References:
Cowell, R. G., Dawid, A. P., Lauritzen, S. L. and Spiegelhalter, D. J. (1999) Probabilistic Networks and Expert Systems. Springer-Verlag, New York.
get_moralize_matrix
Description:
Converts chain graph into its moralized graph
Usage:
get_moralize_matrix(adj_matrix)
Arguments:
| adj_matrix | the adjacency matrix of the chain graph. |
Details:
The function joins all complex spouse with undirected edge and then converts all arrows into lines
Value:
| Result | adjacency matrix of the moral graph |
Example:
matrix1 = np.array([[0, 1, 1],[1, 0, 1],[0, 1, 1]])
result = get_moralize_matrix(matrix1)
References:
Lauritzen, S. L. (1996). Graphical Models. Clarendon Press, Oxford.
skeleton
Description:
Returns skeleton of a graph
Usage:
skeleton(adj_matrix)
Arguments:
| adj_matrix | the adjacency matrix of the graph. |
Details:
The function converts all arrows into lines
Value:
| Result | adjacency matrix of the skeleton |
Example:
matrix1 = np.array([[0, 1, 1],[1, 0, 1],[0, 1, 1]])
result = skeleton(matrix1)
References:
is_separated
Description:
Returns skeleton of a graph
Usage:
is_separated(setA, setB, setSeparator, adj_matrix)
Arguments:
| setA | first set of vertices |
| setB | sevond set of vertices |
| setSeparator | set of vertices that based on which we want to check C-separation of setA and setB |
| adj_matrix | the adjacency matrix of the graph. |
Details:
The function checks if vertices from set A are C-separated from vertcies from setB given a set, setSeparator(can be empty)
Value:
| Result | True/False |
Example:
matrix1 = np.array([[0, 1, 1],[1, 0, 1],[0, 1, 1]])
result = is_separated({0}, {1}, {2}, matrix1)
References:
Lauritzen, S. L. (1996). Graphical Models. Clarendon Press, Oxford. Studeny, M. and Bouckaert, R. R. (1998). On chain graph models for description of conditional independence structures. Annals of Statistics 26 1434-1495.
is_triangulated
Description:
Performs a maximum cardinality search on an undirected graph to determine whether it is triangulated.
Usage:
is_triangulated(adj_matrix)
Arguments:
| adj_matrix | the adjacency matrix of the undirected graph. |
Details:
The function checks if given undirected matrix is triangulated or not and also returns the perfect numbering of vertices based on simple linear-time algorithms to test chordality of graphs given by Tarjan, R. E. and Yannakakis. See referecnce for details
Value:
| is.triangulated | True/False - a logical value indicating whether the input graph is triangulated or not. |
| perfect.numbering | a perfect numbering of the vertices. |
| card | number of unlabeled neighbors when labeling each variable, with order compatible to the perfect numbering. |
| pi.record | a record of unlabeled neighbors during the execution of the algorithm. |
Example:
matrix1 = np.array([[0, 1, 1],[1, 0, 1],[0, 1, 1]])
resultDict = is_triangulated(matrix1)
References:
Tarjan, R. E. and Yannakakis, M. (1984). Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM Journal on Computing, 13, 566-79.
triangulate
Description:
Triangulates an undirected graph to a chordal graph.
Usage:
triangulate(adj_matrix)
Arguments:
| adj_matrix | the adjacency matrix of the undirected graph. |
Details:
This function coverts a graph into triangulated graph. For this purpose it use One Step Look Ahead Triangulation algorithm (see references)
Value:
| adj_matrix | the adjacency matrix of the triangulated graph. |
Example:
matrix1 = np.array([[0, 1, 1],[1, 0, 1],[0, 1, 1]])
result = triangulate(matrix1)
References:
Cowell, R. G., Dawid, A. P., Lauritzen, S. L. and Spiegelhalter, D. J. (1999) Probabilistic Networks and Expert Systems. Springer-Verlag, New York.
ug_to_jtree
Description:
Constructs a junction tree for an undirected graph.
Usage:
ug_to_jtree(adj_matrix)
Arguments:
| adj_matrix | the adjacency matrix of the undirected graph. |
Details:
This function and its helpers implement the junction tree construction algorithm described in detail in Section 4.3 and 4.4 of Cowell, et al (1999).
Value:
| result | An object of class SepTree |
Example:
matrix1 = np.array([[0, 1, 1],[1, 0, 1],[0, 1, 1]])
result = ug_to_jtree(matrix1)
References:
Cowell, R. G., Dawid, A. P., Lauritzen, S. L. and Spiegelhalter, D. J. (1999) Probabilistic Networks and Expert Systems. Springer-Verlag, New York.
SepTree
Description:
Objects representing separation tree as described in Xie, Geng and Zhao (2006) and Ma, Xie and Geng (2008), which includes junction tree of cliques as a special case.
Data members:
| tree_struct | the adjacency matrix of the junction tree. |
| cliques | the list of cliques on the junction tree. |
| separators | the list of separators on the junction tree, each element on the list has two components: the separator compoenent is the set of graph vertices in the separator and edge is the edge on the tree that the separator is attahced to |
Details:
This function and its helpers implement the junction tree construction algorithm described in detail in Section 4.3 and 4.4 of Cowell, et al (1999).
Example:
matrix1 = np.array([[0, 1, 1],[1, 0, 1],[0, 1, 1]])
result = ug_to_jtree(matrix1)
# result will be an object of SepTree
References:
Ma, Z., Xie, X. and Geng, Z. (2008). Structural learning of chain graphs via decomposition. J. Mach. Learn. Res., 9, 2847-2880. Xie, X., Geng, Z. and Zhao, Q. (2006). Decomposition of structural learning about directed acyclic graphs. Artif. Intell., 170, 422-439.
get_uig_norm
Description:
Learns an undirected independence graph from a given data set. The data are assumed to be normally distributed.
Usage:
get_uig_norm(data, p_value)
Arguments:
| data | The data matrix with rows corresponding to observations and columns corresponding to random variables. |
| p_value | The thresholding p-value for each conditional independence test. |
Details:
The function learns an undirected independence graph by computing the partial correlations between variables based on the provided data matrix. It uses a thresholding p-value to determine the existence of edges in the graph.
Value:
The function returns the adjacency matrix of the learned undirected independence graph.
Example:
data = np.array([[1.0, 2.0, 3.0], [4.0, 5.0, 6.0], [7.0, 8.0, 9.0]])
p_value = 0.05
adj_matrix = get_uig_norm(data, p_value)References:
Lauritzen, S. L. (1996). Graphical Models. Clarendon Press, Oxford.
gaussCItest
Description:
Performs the Gaussian conditional independence test between two variables with a set of conditioning variables.
Usage:
gaussCItest(x, y, S, stuffStat)
Arguments:
| x, y | Indices of the variables for which to perform the test. |
| S | Set of conditioning variables. |
| stuffStat | Dictionary containing relevant statistical information. |
Details:
The function performs a Gaussian conditional independence test between variables `x` and `y`, given a set of conditioning variables `S`. It calculates the test statistic `z` based on the statistical information provided in the `stuffStat` dictionary. It then computes the p-value for the test
Value:
The function returns the p-value of the Gaussian conditional independence test.
Example:
x = 0
y = 1
S = [2, 3]
stuffStat = {'C': [0.2, 0.3, 0.5, 0.1], 'n': 100}
p_value = gaussCItest(x, y, S, stuffStat)References:
Whittaker, J. (1990). Graphical Models in Applied Mathematical Multivariate Statistics. John Wiley and Sons, Chichester, England.
gaussian_pc_learn
Description:
Learns the structure of a directed acyclic graph (DAG) using the PC algorithm for Gaussian data.
Usage:
gaussian_pc_learn(cov, n, p_value, vertexNames=[])
Arguments:
| cov | The covariance matrix of the data. |
| n | The number of observations in the data. |
| p_value | The threshold p-value for conditional independence tests. |
| vertexNames | (Optional) List of names for each vertex in the graph. |
Details:
The function implements the PC algorithm for learning the structure of a directed acyclic graph (DAG) from Gaussian data. It starts with a complete undirected graph and iteratively removes edges based on conditional independence tests. The algorithm considers zero-order, first-order, second-order, and so on conditional independence relations to thin the graph. The resulting graph represents the learned DAG structure.
Value:
| amat | The adjacency matrix of the learned DAG. |
| sep_pairs | A list of separation pairs representing d-separation relationships in the learned DAG. Each separation pair contains the vertices and separation set for d-separation. |
Example:
cov_matrix = np.array([[1, 0.5, 0], [0.5, 1, 0], [0, 0, 1]])
n_observations = 1000
p_value_threshold = 0.05
vertex_names = ['A', 'B', 'C']
result = gaussian_pc_learn(cov_matrix, n_observations, p_value_threshold, vertex_names)References:
Mohammad Ali Javidian, Marco Valtorta, and Pooyan Jamshidi. "An Order-Independent Algorithm for Learning Chain Graphs" Proceedings of the 34th International Florida Artificial Intelligence Research Society Conference (FLAIRS-34), 2021
learn_skeleton_norm
Description:
Learns the skeleton of a graphical model using the PC algorithm for Gaussian data.
Usage:
learn_skeleton_norm(tree: SepTree, cov, n, p_value, drop=True)
Arguments:
| tree | A SepTree object representing the tree structure of the graphical model. |
| cov | The covariance matrix of the data. |
| n | An integer specifying the sample size. |
| p_value | A significance level used in statistical tests. |
| drop | (Optional) A boolean indicating whether to drop edges or not (default is True). |
Details:
The function implements the PC algorithm for learning the skeleton of a graphical model from Gaussian data. It starts with a given SepTree object representing the tree structure of the graphical model. The function then learns local undirected graphs within each clique of the tree, and then removes edges based on conditional independence tests using the PC algorithm. The resulting graph represents the skeleton of the graphical model.
Value:
| amat | The adjacency matrix of the learned skeleton. |
| sep_pairs | A list of separation pairs representing d-separation relationships in the learned skeleton. Each separation pair contains the vertices and separation set for d-separation. |
Example:
tree_structure = SepTree(...)
cov_matrix = np.array([[1, 0.5, 0], [0.5, 1, 0], [0, 0, 1]])
n_observations = 1000
p_value_threshold = 0.05
result = learn_skeleton_norm(tree_structure, cov_matrix, n_observations, p_value_threshold)References:
gaussian_skeleton_mkb
Description:
Performs skeleton learning by iteratively removing edges based on conditional independence tests for Gaussian data.
Usage:
gaussian_skeleton_mkb(cov, n, p_value)
Arguments:
| cov | The covariance matrix of the variables. |
| n | An integer specifying the number of sample cases (number of rows in the data). |
| p_value | A threshold p-value for conditional independence tests. |
Details:
The function performs skeleton learning by iteratively removing edges based on conditional independence tests. It starts with a given covariance matrix of the variables and performs Phase 1 of the MKB (Markov blanket) algorithm to learn the Markov blankets for each variable. It then removes edges between variables that are not in each other's Markov blankets. Finally, it applies the PC algorithm to further remove edges based on conditional independence tests using the given p-value threshold. The resulting graph represents the learned skeleton of the graphical model.
Value:
| amat | The adjacency matrix of the learned skeleton. |
| sep_pairs | A list of separation pairs indicating the separation sets between variables. Each separation pair contains the vertices and separation set for d-separation. |
Example:
cov_matrix = np.array([[1, 0.5, 0], [0.5, 1, 0], [0, 0, 1]])
n_observations = 1000
p_value_threshold = 0.05
result = gaussian_skeleton_mkb(cov_matrix, n_observations, p_value_threshold)References:
Mohammad Ali Javidian, Marco Valtorta, and Pooyan Jamshidi.
"Learning LWF Chain Graphs: A Markov Blanket Discovery Approach"
Proceedings of the Thirty Sixth Conference on Uncertainty in
Artificial Intelligence (UAI-2020), pages: 1069-1078, 2020.
Margaritis, D., and Thrun, S. 1999. Bayesian network
induction via local neighborhoods. In Proceedings of the NIPS’99,
505–511.
get_pattern_matrix
Description:
Generates the pattern matrix from the adjacency matrix of a directed graph.
Usage:
get_pattern_matrix(adjacency_matrix)
Arguments:
| adjacency_matrix | A NumPy array representing the adjacency matrix of the directed graph. |
Details:
The function generates the pattern matrix by finding all the edges that are part of at least one minimal complex in the directed graph. The function then converts the input adjacency matrix into the adjacency matrix for the pattern by making all the remaining directional edges undirectional.
Value:
Returns the pattern matrix as a NumPy array.
Example:
adjacency_matrix = np.array([[0, 1, 1], [0, 0, 1], [0, 0, 0]])
pattern_matrix = get_pattern_matrix(adjacency_matrix)References:
Studeny, M. (1997). A recovery algorithm for chain graphs. Int. J. Approx. Reasoning, 17, 265-293.
learn_complex_norm
Description:
Learns a complex using a skeleton and covariance matrix.
Usage:
learn_complex_norm(skel, cov, n, p_value)
Arguments:
| skel | Skeleton |
| cov | Covariance matrix. |
| n | Size of the data sample. |
| p_value | Threshold p-value for significance. |
Details:
The function learns a complex based on the skeleton and covariance matrix. It returns a pattern.
Value:
Returns the pattern matrix.
Example:
skel = {
"amat": wmat,
"sep.pairs": sep_pairs
}
cov = np.array(...)
n = 100
p_value = 0.05
pattern_matrix = learn_complex_norm(skel, cov, n, p_value)
References:
as_freq_tb
Description:
Convert a discrete data matrix into a frequency table.
Usage:
as_freq_tb(mat)
Arguments:
| mat | Input matrix. |
Details:
The function converts the input matrix into a frequency table object.
Value:
Returns the frequency table object.
Example:
mat = np.array([[1, 2, 1], [3, 1, 2], [2, 3, 2]])
freq_table = as_freq_tb(mat)
References:
freq_tb
Description:
Stores a frequency table object.
Usage:
freq_tb(table, levels, colnames=None)
Arguments:
| table | Frequency table matrix. |
| levels | List of levels (unique values) for each column in the frequency table. |
| colnames | List of column names. |
Details:
The `freq_tb` class is used to store a frequency table object. It contains the frequency table matrix, the list of levels (unique values) for each column in the table, and optionally the column names.
Example:
table = np.array([[1, 2, 1], [3, 1, 2], [2, 3, 2]])
levels = [3, 3, 2]
colnames = [0, 1, 2]
frequency_table = freq_tb(table, levels, colnames)
References:
compress_freq_tb
Description:
Compresses a frequency table by removing specified columns.
Usage:
compress_freq_tb(tb, subset=None)
Arguments:
| tb | Frequency table object to be compressed. |
| subset | A list of indices indicating the subset of variables to be compressed on. The default is the whole variable set. |
Details:
Compresses a frequency table to a subset of the variables.
Value:
Returns the compressed frequency table object.
Example:
table = freq_tb(...)
subset = [0, 1, 2]
compressed_table = compress_freq_tb(table, subset)
References:
multinom_ci_test
Description:
Performs a conditional independence test for variables u and v with conditioning set cond.
Usage:
multinom_ci_test(tb, u, v, cond=[])
Arguments:
| tb | Frequency table object. |
| u | First variable index. |
| v | Second variable index. |
| cond | List of variable indices for the conditional set. Defaults to an empty list. |
Details:
The function performs a conditional independence test using a frequency table object. It calculates the p-value, deviance, and degrees of freedom for the test and returns them in a dictionary.
Value:
Returns a dictionary containing the p-value, deviance, and degrees of freedom.
Example:
table = freq_tb(...)
u = 0
v = 1
cond = [2, 3]
result = multinom_ci_test(table, u, v, cond)
References:
Agresti, A. (2002). Categorical Data Analysis. 2nd Ed. John Wiley and Sons. Hoboken, NJ.