Graph Entropy

Sergio Hernández Cerezo

Entropy issue #1: Cross-entropy

Gibbs cross-entropy for two distributions P, Q is not well defined: whenever q_i is zero and p_i is not, H is not defined, as log(0) makes no sense.

We present generalised forms of cross-entropy without this limitation.

​

H₃(Q,P) = 1 + log_e(∏(2-q_i^pi))

H_Gibbs(Q,P) = -∑(p_i×log(q_i))

H₁(Q,P) = ∑(1-q_i^pi)

H₂(Q,P) = ∏(2-q_i^pi)

Product-based forms of cross-entropy

Formulations for H₃ cross-entropy

H₃(P) entropy and cross-entropy can be defined using several interesting formulations.�

​

H₃(Q,P) = ∑(log_e(e×(2-q_i^pi)))

H₃(Q, P) = 1 + log_e(H₂(Q, P))

H₃(Q,P) = log_e(e×∏(2-q_i^pi))

H₃(Q, P) = log_e(e×H₂(Q, P))

H₃(Q,P) = 1 + ∑(log_e(2-q_i^pi))

Entropy issue #2: Distributions only

Gibbs entropy can only be used on probability distributions:

• One-level flat structure.
• ∑ p_i = 1 ({p_i} represent a partition).

Instead, we will be defining entropy as:

H₃(P) = 1+log_e(∏(2-p_i^pi))

Graph Entropy: Relations

A “relation” is the basic structure on graph entropy.

• Nodes ‘A’ and ‘B’ represent properties of the system and will hold an entropy.
• Edges represent the relation between two properties and hold a conditional probability P(A|B).

H₃(B) = 1 + log_e(H₃(A) × (2 - p^p))

Graph Entropy: Relation networks

Any acyclic directed graph where edges has assigned a probability can be decomposed as a set of “relations”.

• Nodes without inputs are considered “leaf nodes” with a default entropy of 1.
• The “root” node has no outgoing connections and holds the entire graph entropy.

Graph Entropy: Nodes

Initialization:

• Raw entropy = H₂ = 1

When a new input S arrives:

• Update H₂ = H₂ × S
• Recalculate H₃
• Output H₃

H₂ = ∏ S_i

H₃ = 1+log_e(H₂)

Input S₁ ...

Input S_n

Output

Graph Entropy: Edges

Initialization:

• P = S = ɸ = ɸ’ = 1

When P or S change:

• ɸ is recalculated.
• Output = (ɸ / ɸ’)
• ɸ’ = ɸ

Input

P = P(A|B)

S = Input

Output

ɸ = S × (2-P^P)

Output = ɸ/ɸ’

Example: Cars by engine

Cars can have a Gas engine, an Electric engine, or both if they are Hybrids.

Classically we define a partition of the space {G=gas only, E=electric only, H=hybrids} with some ‘flat’ probability distribution {0.7, 0.1, 0.2} as if they were independent and had no internal structure.

Distribution vs Graph

Considering that the experiment generated a distribution is not a complete view of the information.

​

Using a graph would allow us to include all the internal structure and take this into account in the entropy.

Cars by engine: graph

• G* = Has gas eng. p=0.7+0.2=0.9
• E* = Has elec. eng. p=01+0.2=0.3

Repeating over G* and E*:

• P(G*|G*) = P(E*|E*) = 1
• P(E*|G*) = 0.2/0.9 = 0.222
• P(G*|E*) = 0.2/0.3 = 0.666

Adding structure made entropy to grow from H_Dist=1.63 to H_Graph=1.77

Separation axioms (product form)

Max(H₃(P), H₃(Q))

H₃(P|Q)

H₃(P) x H₃(Q)

H₃(P&Q)

Multiplicative form of the 3^th axiom

Maximum between:

​

H₃(P)= 1+log(𝚷(2-p_i^pi))

H₃(Q)= 1+log(𝚷(2-q_i^qi))

X_ij = P(p_i|q_j) = (p_i×q_j)

​

1+log(𝚷(2-X_ij^Xij))

​

(1+log(𝚷(2-p_i^pi)))

×

(1+log(𝚷(2-q_i^qi)))

​

1+log(H₃(Q)×𝚷(2-p_i^pi))

=

1+log(H₃(Q)×H₂(P))

For P, Q independent:

Separation axioms (summary form)

Max(H₃(P), H₃(Q))

H₃(P|Q)

H₃(P) x H₃(Q)

H₃(P&Q)

Multiplicative form of the 3^th axiom

Maximum between

​

H₃(P)=1+∑(log(2-p_i^pi)) H₃(Q)=1+∑(log(2-q_i^qi))

X_ij = P(p_i|q_j) = (p_i×q_j)

​

H₃(P)=1+∑(log(2-X_ij^Xij))

​

1+∑(log(2-p_i^pi))

×

1+∑(log(2-q_i^qi))

​

​

log(H₃(Q)) + H₃(P)

For P, Q independent: