1
$\begingroup$

I am looking for some known approach, or some previous work, on the following problem:

Let $\Sigma$ be an alphabet of symbols and $\Sigma^*$ be the set of all the strings that you can compose from this alphabet. Furthermore, let $f:\Sigma^*\rightarrow2^{\Sigma^*}$ be a function that assigns a certain set of $\Sigma$-strings to each $\Sigma$-string. Suppose you have a dataset $\mathcal{D}\subseteq\Sigma^*\times2^{\Sigma^*}$ of input-output pairs.

With this data, the goal is to learn a function $f^\prime:\Sigma^*\rightarrow2^{\Sigma^*}$ that, given a string $\sigma\in\Sigma^*$, gives any superset of $f(\sigma)$, e.g. $f^\prime(\sigma)\supseteq f(\sigma)$. Of course, returning the set of all strings is not a good solution, so $f^\prime(\sigma)$ should not be much larger than $f(\sigma)$ (to give a rough idea, if $|f(\sigma)|=10$, then $|f^\prime(\sigma)|=100$ would still be ok, but $|f^\prime(\sigma)|=10000$ wouldn't). To give an intuitive reason behind this, I have already an algorithm which, given a $\sigma$ and a set $S\supseteq f(\sigma)$, returns $f(\sigma)$. However, this algorithm has a extremely high time-complexity (growing with $|S|$), and I want to use this machine learning approach to narrow down the search.

I would like to use any Machine Learning approach (from Evolutionary Computing to Deep Learning) to solve this problem.

So far my only idea would be to use an encoder-decoder architecture. I construct character embeddings for all symbols in $\Sigma$, and then through some neural architecture (I was thinking about an LSTM) I aggregate them to obtein a string representation. Given this, the decoder generates in sequence all elements of the corresponding set (by a similar, but inverse, fashion).

This is clearly not optimal, because sets lack any meaningful order, and this approach is order-dependent (by nature of LSTMs and decoders in general). Of course I could always sort all sets, but this still imposes a structure to my problem that is not there, and I feel like this could make it harder to solve.

So, in sum, my question is: Is there any known approach to the problem of generating sets of objects from a given input in the literature? If not, how could I improve my approach?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.