Given an E-class, is it possible to sample a batch of equivalent terms from it?

[brando90]

I am interested to sample subset of terms from an e-class (in an E-graph). For example, in decreasing ast size/depth or even randomly. Is this possible? If yes how would one do it in egg?

[mwillsey]

Currently there isn't a built-in way to do it in egg. You can only extract one term from an e-class for a given cost function.

You could certainly build something to sample terms from an e-class by selecting random "representative' e-nodes for each e-class. Care must be taken to avoid cycles though. Here's some code that helps you locate e-nodes that make cycles.

[brando90]

actually let's take a step back to your idea of selecting e-nodes. Given an e-graph, how do I know which one is the "root e-class" (since the e-graph really is a set of asts so one must have been our starting node). Then I am find just selecting a random set of e-nodes (at least at first).

Later it would be nice to do what @Bastacyclop did and extract the N best terms according to a cost function.

[mwillsey]

The root e-class is a matter of perspective. You might have 0, 1, or many roots depending on what you inserted into the initial e-graph. Typically though, the root e-class is the e-class containing the initial term you added to the e-graph.

@Bastacyclop's Scala version is definitely a good source of inspiration, but if you just need to get an idea of what's in an e-class via sampling, I think the idea above would do just fine.

[brando90]

Thanks max! Just to clarify, what do you mean by "idea above"? Do you mean the one I suggested with a cost function that checks for size(ast) == number and returns 0 or 1 or something else?

Thanks again! :) Love egg and e-graphs.

[mwillsey]

This one: just selecting random e-nodes after cycle removal. Glad you're having fun!

[sqPoseidon]

@brando90 Hi, do you have any updates on this problem? I want to sample the equivalent terms too. Many thanks if you have any comments or suggestions.

[Bastacyclop]

I've personally implemented in a Scala port:

• extracting the N best terms of an e-class according to a cost function
• counting programs up to a certain size
• extracting random programs, however this recursively makes a random choice of e-node so the random distribution is not great (cycles may also be taken but I assume that the probability of exiting a cycle is high). I think that the random distribution could be improved by combining this with counting and a size limit (e.g. weigh the e-node choice by how many programs it represents).

[Bastacyclop]

@mwillsey Any idea how extracting the N best terms would work with LP extraction? Could we duplicate the variables to solve N times to get N solutions, and include the constraint that each solution should be different?

[mwillsey]

Hmm, interesting. I think it would be possible to do that, but I think you'll have a problem with diversity because of equivalent subterms. For example, f(g(a + b)) = f(g(b + a)). For "top k" extraction, I think my best idea so far is extract, delete a random e-node from the e-graph that was in the extracted term, and repeat.

[Bastacyclop]

I feel like the diversity issue would benefit from a problem-specific (dis)similarity function, see:
https://link.springer.com/chapter/10.1007/978-3-642-33715-4_1
https://arxiv.org/abs/1610.02424
https://dl.acm.org/doi/abs/10.1145/3485486

Maybe its possible to include such a function into the LP objective (i.e. maximize diversity between the N solutions), but that might be difficult / costly.

[brando90]

I don't unfortunately :( Get Outlook for Android<https://aka.ms/AAb9ysg>

…

________________________________ From: Sherbet Lemon ***@***.***> Sent: Tuesday, November 1, 2022 9:59:11 PM To: egraphs-good/egg ***@***.***> Cc: Brando Miranda ***@***.***>; Mention ***@***.***> Subject: Re: [egraphs-good/egg] Given an E-class, is it possible to sample a batch of equivalent terms from it? (Discussion #174) @brando90<https://github.com/brando90> Hi, do you have any updates on this problem? I want to sample the equivalent terms too. Many thanks if you have any comments or suggestions. — Reply to this email directly, view it on GitHub<#174 (reply in thread)>, or unsubscribe<https://github.com/notifications/unsubscribe-auth/AAOE6LTH4ZVIMNNHAKKUSM3WGHYJ7ANCNFSM5RSLBYRA>. You are receiving this because you were mentioned.Message ID: ***@***.***>

[sqPoseidon]

Emm, thank you.
@mwillsey Hi Max, you've mentioned that we can delete some enodes from the egraph. Can you provide me with some examples of how to delete the nodes? I didn't find that in the document.

[mwillsey]

You can reach into EClass::nodes and do whatever you want! It's just a Vec of Enodes.