Test #1 (Order score): Small datasets and orders

[M Charles]

The first test will compare hand calculations and program results for small orders/datasets. In the following, I will be using the notation from [Friedman & Koller, 2003] (so a parent will precede its child)

1 node
In the simplest case, assume there is only one binary node, X1. I think the probability of the data given the order can be simplified to:

1node.jpg (14 KiB) Viewed 1263 times

Now, running on some small datasets (1,2,and 3 entries), the results are:

• X1={0}:
  -0.693147180559945
• X1={0,1}:
  -2.07944154167984
• X1={0,0}:
  -0.980829253011726
• X1={0,0,0}:
  -1.16315080980568
• X1={0,0,1}:
  -2.77258872223978

and these appear to match the previous equation.

2 node
In the case of two nodes, X1 and X2, the equation for X1<X2 becomes

2node.jpg (18.02 KiB) Viewed 1261 times

where n_(a,b) is n_{X1=a,X2=b}. A couple test results are

• X1={0}
  X2={0}
  X1<X2: -0.693147180559945
  X2<X1: -0.693147180559945
• X1={0,0}
  X2={0,0}
  X1<X2: -1.21444410419323
  X2<X1: -1.21444410419323
• X1={0,1}
  X2={0,0}
  X1<X2: -2.54944517092557
  X2<X1: -2.54944517092557
• X1={0,1,0}
  X2={0,0,1}
  X1<X2: -5.03435182071357
  X2<X1: -5.03435182071357

3 node
A couple tests:

• X1={0}
  X2={0}
  X3={0}
  X1<X2<X3: 4.44089209850063e-16
  X1<X3<X2: 4.44089209850063e-16
  X2<X1<X3: 4.44089209850063e-16
  X2<X3<X1: 4.44089209850063e-16
  X3<X1<X2: 4.44089209850063e-16
  X3<X2<X1: 4.44089209850063e-16
• X1={0,0}
  X2={0,0}
  X3={0,0}
  X1<X2<X3: -0.708631022250785
  X1<X3<X2: -0.708631022250785
  X2<X1<X3: -0.708631022250785
  X2<X3<X1: -0.708631022250785
  X3<X1<X2: -0.708631022250785
  X3<X2<X1: -0.708631022250785
• X1={0,1}
  X2={0,0}
  X3={0,0}
  X1<X2<X3: -2.29351179678837
  X1<X3<X2: -2.29351179678837
  X2<X1<X3: -2.29351179678837
  X3<X1<X2: -2.29351179678837
  X2<X3<X1: -2.28836378027097
  X3<X2<X1: -2.28836378027097
• X1={0,1}
  X2={0,1}
  X3={0,0}
  X1<X2<X3: -2.94248775903518
  X2<X1<X3: -2.94248775903518
  X1<X3<X2: -2.8942856572173
  X2<X3<X1: -2.8942856572173
  X3<X1<X2: -2.8942856572173
  X3<X2<X1: -2.8942856572173
• X1={0,0,1}
  X2={0,0,0}
  X3={0,0,0}
  X1<X2<X3: -3.31084145201962
  X1<X3<X2: -3.31084145201962
  X2<X1<X3: -3.31084145201962
  X3<X1<X2: -3.31084145201962
  X2<X3<X1: -3.30491111588477
  X3<X2<X1: -3.30491111588477
• X1={0,0,1,0,0}
  X2={0,1,0,1,1}
  X3={0,1,0,0,0}
  X1<X3<X2: -10.049176787447
  X3<X1<X2: -10.049176787447
  X3<X2<X1: -10.0403062276219
  X2<X3<X1: -10.0403062276219
  X1<X2<X3: -10.0271462031263
  X2<X1<X3: -10.0271462031263