{'fraction_non_alphanumeric': 0.05813953488372093, 'fraction_numerical': 0.0070278558650651675, 'mean_word_length': 3.419254658385093, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 8, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 33, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Junction trees constructions in Bayesian networks

Junction trees are used as graphical structures over which propagation will be carried out through a very important property called the ruining intersection property. This paper examines an alternative method for constructing junction trees that are essential for the efficient computations of probabilities in Bayesian networks. The new proposed method converts a sequence of subsets of a Bayesian network into a junction tree, in other words, into a set of cliques that has the running intersection property. The obtained set of cliques and separators coincide with the junction trees obtained by the moralization and triangulation process, but it has the advantage of adapting to any computational task by adding links to the Bayesian network graph.


Introduction
Inference is one of the important tasks in Bayesian networks (BNs). It consists of computing marginal probabilities P A , the probability of X A = (X i ) i∈A where A is a subset of the BN variables), and conditional probabilities P A|B (probability of X A conditioned on X B , where A and B are two disjoint subsets of the BN variables). It is essentially an optimization calculation problem, as it becomes increasingly heavy with the complexity of the graph relative to the number of variables and their values. The correspondence between the graphical structure and the associated probabilistic structure bring many of the problems with inference to graphs problems. However these problems are relatively complex and give rise to a lot of research: [2], [7], [12]. Therefore, inference in BNs is a complex and a difficult task. [4] showed that this problem is NP-hard, although more research has been undertaken to develop efficient algorithms for such problems ( [3], [10]).
There are two primary methods in literature (and in software) for constructing junction trees. The most commonly used method is by moralization and triangulation, see [5], [6], [8] for details. The other method recursively constructs a proper sequence of cliques that satisfies the running intersection property (see definition in section 3 below), introduced in [1] and [5].
For our part, after presenting the concept of the junction tree (JT), or equivalently, a proper sequence satisfying the running intersection property (RIP), we propose an algorithm that allows  constructing a sequence of subsets of the BN that has the RIP, without restrictive conditions on the set of subsets, as is the case with the junction tree algorithm. Section 2 provides the details on the above-mentioned inference problem and the motivation behind our work. Section 3 offers complementary information about junctions trees and proper covering sequences that satisfy the running intersection property. Section 4 presents our new technique for constructing a JT on a given family of subsets in the BN.

Bayesian Networks and Junction Trees
Consider X I = (X i ) i∈I a family of discrete random variables. For each i, X i has values in the finite domain Ω i . For each J ⊆ I, we denote with X J , the subset (X i ) i∈J , which has values in the finite domain Ω J = i∈J Ω i and P J the joint probability of X J .
Given C, a collection of subsets that covers I, let us recall that C and the probability P I of the family (X i ) i∈I are compatible if P I is written as follows: where for each C, f C is a known function from Ω C in R + and usually called potential of C; we can write (1) as: where α is the normalization constant. Given a BN on I, C, in this case, is the set of subsets {i ∪ pa(i)}, where pa(i) is the set of parents of i and f {i∪pa(i)} is the probability of X i conditioned on X pa(i) = (X j ) j∈pa(i) , α is known and is 1.
The computation algorithms seek to only sum over subsets Ω C where a smaller C is desired than I and well chosen in function of the probability and conditional probability of the subsets of X I that we would like to compute.
However, if P I is compatible with C, a fundamental algorithm proposed by Lauritzen [8], the JT algorithm, provides a computing method for all probabilities P C of subsets X C (= (X i ) i∈C ) under the condition that C is a JT.
Given a set K of subsets of I, to compute the probability P K for each K ∈ K. We notice that if C is a set of subsets of I such that ∀ K ∈ K ∃ C ∈ C s.t. K ⊆ C, and we are able to obtain the probabilities P C , we can deduce each P K by choosing a C such as K ⊆ C and by eliminating the random variables in C − K; that is, if we decompose x C to the pair (x K , x C−K ), we have Given P I is compatible with the covering J , a method of computing the probability of all targets P K (K ∈ K) is given as follows: A. Construct a collection of cliques C of C ∪ K, which is a JT. B. Use the compatibility of P I with C to compute P C . C. Compute P K from P C .
Step A, which is purely from the graph theory, consists of constructing a JT that is a covering of C ∪ K. This step can be heavy. We propose in what follows a new method for constructing a proper covering sequence that has the RIP, We think our method will significantly improve the original method and it can be adapted to any computation task.
3. Junction trees and proper covering Sequence that has the RIP 3.1. Junction Tree -Separators Definition 1 Given a set I, we call a proper covering sequence of I any sequence (C 1 , . . . , C k ) The In other words, a covering is proper if there is no inclusion among its elements.
Clearly, each non-proper covering can be associated with a proper covering by simply removing the parts that are subsets of others, and keeping just one part in case they are equal parts. Definition 2 Given I a finite set, we call a JT on I every tree (C, H), where C is a proper covering of I satisfying the following property: for each pair (C, C ) of non-adjacent elements of C, each intermediate vertex C on the path in H joining C and C satisfies C ∩ C ⊂ C . Remark 1 If card (C) ≤ 2, the property interfering in the definition of junctions trees is empty. They are trivially JTs when: -for k = 1, C = {I} (a tree with only one element, so zero arcs), -for k = 2, any pair {C, C } such that C ∪ C = I, C − C = ∅, C − C = ∅. Definition 3 Given (C, H) a JT on a set I, the separators associated with this tree are the intersections C ∩ C , where C and C are two elements of C that are adjacent for the structure of the tree H.
We notice that if the cardinality of C is k, there a k − 1 separators (number of arcs in a tree with k vertices).
An equivalent presentation of JTs is given by the following theorem. Theorem 1 Consider C a proper covering of I and H a tree structure on C.
(C, H) is a JT if and only if, for each i ∈ I, the set of subsets of C to which i belongs, noted as C i , constitutes a subtree of (C, H)

Proper
Covering Sequences that have the RIP Definition 4 A sequence of subsets of a set I, (C 1 , . . . , C k ), is said to have the RIP if The RIP can be also written as follows: We notice that this property is always satisfied for j = 2, with = 1.
We are particularly interested in proper covering sequences that have the RIP. We notice the following two such sequences: -The sequence has one element (I).
-Any proper covering sequence with 2 elements:

Link between JTs and RIP
The most important property of junctions trees, for our needs, is given by the following theorem. Theorem 2 Any JT on I gives induces to as many proper covering sequences with the RIP as there are topological orderings on this tree. Conversely, any proper covering sequence that satisfies the RIP can be associated with the structure of a JT. We omit the proof of the theorem due to space limitation. 4. An Alternative Method 4.1. Context Given a finite covering F of I, our goal is to construct step by step a proper covering sequence, (C 1 , . . . , C p ), that has the RIP and such that every F ∈ F is included in at least one of the C j (1 ≤ j ≤ p).
The algorithm requires that there be an order on I denoted I = {1, . . . , n}; we consider the smallest element of each F (F ∈ F) for this ordering, and we take the union of subsets F that have same smallest element. Ordering these unions by their smallest elements, we obtain a covering sequence (Q 1 , . . . , Q r ) (where r ≤ n) such that, if we denote α k (where 1 ≤ k ≤ r) the smallest element of Q k , the sequence (α 1 , . . . , α r ) is strictly increasing.
The imposed condition by our problem-that each F is included in one of the C j -is obviously equivalent to the inclusion of each Q k in one of the C j .
The sequence (Q 1 , . . . , Q r ) is not necessarily proper, which will not change anything to the problem if we clean it first; in other words, removing each subset that is already strictly included in another one. We notice in this regard, by construction, that the inclusion of Q j ⊆ Q j cannot hold with j < j , because we will then have α j ∈ Q j but α j ∈ Q j because all of the elements of Q j are greater or equal to α j , which is strictly greater than α j .
The cleaning consists of eliminating all Q j satisfying ∃ j < j s.t. Q j ⊂ Q j , but the algorithm we are proposing does not require that the sequence (Q 1 , . . . , Q r ) be proper.
The problem that the algorithm should solve is as follows: Given a covering sequence (Q j ) 1≤j≤r of non-empty subsets of I = {1, . . . , n} such that, if we note α j = inf(Q j ), the sequence (α 1 , . . . , α r ) is strictly increasing. We have to construct a proper covering sequence (C 1 , . . . , C p ) that satisfies the RIP such that for each j (1 ≤ j ≤ r), exists k (1 ≤ k ≤ p) satisfying Q j ⊆ C k . We notice that, necessarily, α 1 = 1.
In the case of BNs, where F contains {{i ∪ pa(i)}/i ∈ I}, we achieve the construction of (Q 1 , . . . , Q r ) as follows: -For I, we adopt an anti-hierarchical order relative to the structure of the directed acyclic graph: for each i, its parents are superior to it (in other words, given I is {1, . . . , n}, the order (n, n − 1, . . . , 1) is hierarchical).
-For each i we defineQ i as the union of {i}, pa(i) and, if they exist, subsets belonging to F, not of the form {i ∪ pa(i)}, where i is the smallest element.
The alternative method will construct a sequence (C 1 , . . . , C r ) of non-empty subsets of I of a length equal to the given sequence (Q 1 , . . . , Q r ), that has the RIP such that for each j, k exists satisfying Q j ⊆ C k . The constructed sequence is not necessarily proper but has no inclusions C j ⊆ C j only if j < j. As a second step, we remove all elements included in others so we obtain the sequence (C 1 , . . . , C p ) that satisfies ∀ j ∃ k s.t.Q j ⊆ C k , we notice that making the sequence proper will be completed by respecting and keeping the RIP.
The alternative method constructs successive subsets, noted as D 1 , . . . , D r , such that the reversed sequence (D r , . . . , D 1 ) is the sequence (C 1 , . . . , C r ) or (C 1 , . . . , C p ) sought. In other words, the constructed sequence satisfies the reversed RIP, which means the following:

Phase 1: Constructing a Non Necessary Proper Sequence
The algorithm has exactly r steps; at each step j, it constructs a subset D j , containing Q j and contained in ∪ ≥j Q ; consequently, ∪ >j D = ∪ >j Q .
The sequence (D 1 , . . . , D r ) satisfies the reversed RIP but is not necessarily proper; however, by construction, all of its elements are non-empty and distinct, and the inclusions D j ⊆ D j cannot take place if only j > j. Let us denote, for each j, K j = {α j , . . . , α j+1 − 1} (in this special case where r = n therefore, for each j ∈ {1, . . . , n}, α j = j, on a K j = {j}).
Let us recall that the reversed RIP is automatically satisfied for the term before the last one of the sequence. For the sequence (D j ) 1≤j≤r to satisfy the reversed RIP, the algorithm saves in memory, for each j such that 1 ≤ j ≤ r − 2, S j = D j ∩ (∪ >j Q ). A sufficient condition for a subset D k (with k > j) to satisfy the reversed RIP for D j (in other words, satisfies D j ∩ (∪ >j D ) ⊆ D k ) is that S j ⊆ D k . Si S j = ∅, which means that D j ∩ (∪ >j D ) = ∅, so the reversed RIP is trivially satisfied for D j . Otherwise, the reversed RIP will be automatically satisfied for D j , including in D k , beside Q k , S j once K k ∩S j = ∅ (i.e., when α k ≤ inf(S j ) < α k+1 , with the convention α r+1 = r + 1), which will not only include in D k the elements greater or equal to α k contained in ∪ ≥k Q .
Outputs sequences of subsets of I: (D 1 , . . . , D r ) and (S 1 , . . . , S r−2 ); for each j such that S j = ∅, s j = inf(S j ). Initialization End of the algorithm j = n.
Example 1 Given the BN in figure 1, we would like to compute P i∪pa(i) (for each i ∈ I). We define the subsets: If we do not first clean the sequence, the algorithm will run as shown in Step We notice that the obtained sequence is not proper (D 2 ⊂ D 1 , D 8 ⊂ D 7 , and D 9 ⊂ D 8 ).
If we proceed by first making the sequence proper, we will preserve: then the algorithm will run as follows: Table 2.
Steps of the algorithm with prior cleaning.
Step j K j D j S j 1 1, 2 We notice that, in this case as well, the obtained sequence is not proper (D 7 ⊂ D 6 )

Phase 2: Cleaning the Sequence Obtained in Phase 1
By inverting the (D 1 , . . . , D n ) obtained by the algorithm, we obtain a covering sequence of distance elements (C 1 , . . . , C n ) that satisfies the RIP, and for each (i, j) such that 1 ≤ i < j ≤ n, C i ⊃ C j is false. If this sequence is not proper, the possibility of making it, that is removing each C i for which it exists j (> i), satisfying C i ⊂ C j is possible through the following algorithm. Description of the cleaning phase of the algorithm Inputs a covering sequence (C 1 , . . . , C n ) that has the RIP and such that C i ⊂ C j implies i < j. Current Object a covering sequence (C 1 , . . . , C k ) satisfying the same properties as the given sequence.
Outputs a proper covering sequence (C 1 , . . . , C k ) at the end of the algorithm. Initialization k = n, (C 1 , . . . , C k ) = (C 1 , . . . , C n ) Current Step Determine whether p = min{j ; ∃ i < j s.t.C i ⊂ C j } exists. If p does not exist, the algorithm ends. If p exists, consider K = {i < p ; C i ⊂ C p } and k = min K.
-If they exist, remove from the sequence the C i such that i ∈ K and i = k from the sequence.
-replace C p with C k .
-place C l = C l−p for all l greater than p.
The algorithm will eventually stop because at each step, the length of the sequence will strictly decrease.
Remark 2 Any other cleaning algorithm on (C 1 , . . . , C n ) would lead to a set of identical subsets to {C 1 , . . . , C k }, as it is constructed by the above-described algorithm and therefore has the JT structure. But the proposed algorithm has the advantage of getting it with an order ensuring the RIP.

Conclusion
In this paper, we have presented a method for constructing a proper covering sequence of cliquesa junction tree-that satisfies the running intersection property starting from a simple sequence of subsets in a Bayesian network. The proposed method is advantageous in that it provides a proper covering that has the RIP based on the computation task and without restrictions. The obtained set of cliques and separates coincide with the JTs obtained by the moralization and triangulation process, but it has the advantage of adapting to any computation task by adding links to the BN graph and therefore updates the set of subsets at the start of our algorithm. Future work will compare this method to the moralization and triangulation method on more complex examples of BNs and will also explore the algorithm's complexity and efficiency.