I don't fully understand the Kraskov O-information implementation

[Thomas Varley]

Is there anywhere that explains the logic of the Kraskov O-information? I'm not Java literate, so maybe I'm missing something, but I'm looking at the source code and struggling to understand exactly what is happening.

I understand the basic logic of the classic bivariate Kraskov MI, but the extension to O-info appears to be beyond me.

The two references (Rosas et al., Kraskov et al.,,) I'm familiar with, but they don't detail the link between the two.

[Joseph Lizier]

Hi Thomas,

Pedro wrote this one, so I'll leave the expert opinion to him.

From my perspective in the meantime: the basis of the KSG algorithm is to set the scale based on the kNN distance in the full joint space, and then to project this scale back to the lower order spaces where you need neighbour counts for corresponding entropies (when you take the sum and difference of those with the full joint entropy). This allows all terms in the underlying KL entropies to cancel (pretty much) except the digamma terms of the neighbour counts.

This principle, applied to MI and multi information in the original KSG paper, can be applied to any measure which is a sum-difference of entropy terms, so long as the total dimension cancels in the end. (This is laid out formally in sec 2 and 3 of Gomez Herrero 2015 https://www.mdpi.com/1099-4300/17/4/1958).

This looks fine for total correlation (which is in essence a multi information) in the O-information, and for the Dual Total Correlation, and for their difference, and is what I assume is being done in our estimator here (Pedro can clarify).

--joe
+61 408 186 901 (Au mobile)

--
JIDT homepage: https://github.com/jlizier/jidt
---
You received this message because you are subscribed to the Google Groups "Java Information Dynamics Toolkit (JIDT) discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to jidt-discuss...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/jidt-discuss/18043d43-234d-4c12-9147-356cd024fb69n%40googlegroups.com.

[Mediano, Pedro A]

Hi everyone,

Thanks Joe for adding me (again) to the mailing list! Here's my reply to the issue (so it's in the list archives):

Joe is completely correct! The O-info KSG estimator was derived from the Gomez-Herrero Section 3 applied to the expression of O-info as an entropy combination (Definition 1 in the O-info PRE paper). The only relatively minor difference with respect to Eqs 1,3 in the Gomez-Herrero paper is that in the case of O-info the joint entropy term is scaled by a factor (n-2), where n is the number of variables in the system, so you'll see a factor (`dimensions - 2`) floating around the JIDT O-info implementation. Also, note that for each variable there are two range searchers, one for the "small marginals" (i.e. only for dimension j) and one for "big marginals" (i.e. for all dimensions except j).

I wrote this a while back and it seemed to work, but of course if you spot any issues please let me know!

Cheers,

P

---

From: Joseph Lizier <joseph...@sydney.edu.au>
Sent: 08 October 2024 1:15 PM
To: Mediano, Pedro A <p.me...@imperial.ac.uk>; thos....@gmail.com <thos....@gmail.com>
Subject: Re: Fw: [jidt-discuss] I don't fully understand the Kraskov O-information implementation

 

Great to hear, thanks Pedro!

I've just sent an invitation to the new address (it won't let me directly add). Let me know if you get the invitation and can post? (It would definitely be good if you can post the below once it's working so that's captured in the archive).

Anyway, yeah the n-2 factor does stand out, but it is legit since it pops out of the conditional entropies.

--joe
--
A/Prof. Joseph Lizier
The University of Sydney
School of Computer Science, Faculty of Engineering

On 8/10/24 19:57, Mediano, Pedro A wrote:

Hi both,

Thanks for the discussion on Kraskov O-information! I tried to reply back to the mailing list, but I got a bounce error saying I don't have permission to post to the mailing list. @Joe I tried to add myself with my new Imperial email address (p.me...@imperial.ac.uk), but I didn't get it to work. Do you know how could we get this email in the mailing list?

@Thomas see my answer below! The TLDR is that Joe was right on the money and the implementation is a combination of the Gomez-Herrero method applied to the entropy combination formula for O-info.

Cheers!

P

---

From: Mediano, Pedro A <p.me...@imperial.ac.uk>
Sent: 08 October 2024 9:00 AM
To: jidt-d...@googlegroups.com <jidt-d...@googlegroups.com>
Subject: Re: [jidt-discuss] I don't fully understand the Kraskov O-information implementation

 

Hi guys,

Joe is completely correct! The O-info KSG estimator was derived from the Gomez-Herrero Section 3 applied to the expression of O-info as an entropy combination (Definition 1 in the O-info PRE paper). The only relatively minor difference with respect to Eqs 1,3 in the Gomez-Herrero paper is that in the case of O-info the joint entropy term is scaled by a factor (n-2), where n is the number of variables in the system, so you'll see a factor (`dimensions - 2`) floating around the JIDT O-info implementation. Also, note that for each variable there are two range searchers, one for the "small marginals" (i.e. only for dimension j) and one for "big marginals" (i.e. for all dimensions except j).

I wrote this a while back and it seemed to work, but of course if you spot any issues please let me know!

Cheers,

P

---

From: jidt-d...@googlegroups.com <jidt-d...@googlegroups.com> on behalf of Joseph Lizier <joseph...@gmail.com>
Sent: 08 October 2024 12:22 AM
To: jidt-d...@googlegroups.com <jidt-d...@googlegroups.com>
Subject: Re: [jidt-discuss] I don't fully understand the Kraskov O-information implementation

 

To view this discussion on the web visit https://groups.google.com/d/msgid/jidt-discuss/CAL81BvTiyK4ggtOuJx9Nu41BVn6mVPDOB4szX%2B5TpoNiKGA0ew%40mail.gmail.com.

[Thomas Varley]

Thanks guys - this is very helpful. Esp. the references

Happy holidays,
~Thomas