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?


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.