8
$\begingroup$

Is there a machine learning algorithm that maps a single input to an output list of variable length? If so, are there any implementations of the algorithm for public use? If not, what do you recommend as a workaround?

In my case, the input is a single scalar and the output is a list of scalars with variable length. For example, suppose I wanted to output a list of ones given the length of the list as input. Then <input, output> could be <1, [1]>, <2, [1, 1]>, etc. A small tweak would be providing the square root of the length in which case <2, [1, 1, 1, 1]> would be an answer. Note: the input need not be tied directly to the output.

For a more complex example, suppose I want to learn the look-and-say sequence. Valid <input, output> pairs would be: <1, [1]>, <2, [1, 1]>, <3, [2, 1]>, <4, [1, 2, 1, 1]>, <5, [1, 1, 1, 2, 2, 1]>, etc. My problem is also similar in that I can generate more examples; I am not restricted to a finite set of examples.

|improve this question|||||
$\endgroup$
  • $\begingroup$ Can you give an example of what you mean? I'm confused whether you're asking about a single input variable mapped to multiple different output variables, or a single input variable being mapped to a list of the same variable. $\endgroup$ – NBartley Dec 24 '15 at 22:21
  • 2
    $\begingroup$ All the examples that you have shown thus far have a single output that can be deterministically mapped to a variable length list. Here is the single input/single output: <1,1>,<2,2>,<2,4> and a simple deterministic script can turn this into <1,[1]>,<2,[1,1]>,<2,[1,1,1,1]>. I suggest you split the problem into the machine learning piece and the deterministic piece. $\endgroup$ – AN6U5 Dec 27 '15 at 17:27
  • $\begingroup$ Thanks for the additional information. However, I don't think there is enough information provided to formulate a response beyond a high level heuristic discussion as seen in the answer that is provided. The unlimited bound precludes classification algorithms as discussed below, so this looks more like a problem for a Hidden Markov Model. But the example you provided still lacks a statistical component that points to solution by a statistical learning method. Is the 'look-and-say sequence' the real problem or is there a statistically distributed data set that you are really working with? $\endgroup$ – AN6U5 Dec 29 '15 at 23:04
  • $\begingroup$ The actual problem I'm interested in is the Collatz Conjuecture. In particular, what insights can I gain from a learning algorithm trying to learn <Mersenne number, hailstone sequence>. $\endgroup$ – ricksmt Dec 30 '15 at 17:39
  • 1
    $\begingroup$ Off-topic because the question is a deterministic pure mathematics problem recast in the guise of machine learning. A statistical sample is not provided, rather, a small set of cases from an infinite mathematical series is referenced. The OP is hoping to recover a nonlinear relationship between the input feature and the list of prime numbers corresponding with the input feature's Mersenne Number. This is not well posed, nor does it fall within the data science topic list. $\endgroup$ – AN6U5 Dec 30 '15 at 20:30
2
$\begingroup$

I would try to set a multilabel classification algorithm and make the output standard by adding zeros. So if your data is like this: <1, 1>, <2, [1, 1]>, <3, [2, 1]>, <4, [1, 2, 1, 1]>, <5, [1, 1, 1, 2, 2, 1]>. The maximum number of output is 6. So you could transform your data into something like: <1, [1,0,0,0,0,0]>, <2, [1, 1,0,0,0,0]>, <3, [2, 1,0,0,0,0]>, <4, [1, 2, 1, 1,0,0]>, <5, [1, 1, 1, 2, 2, 1]>

Another option that occurs to me is to add the limit dynamically. Let say you have your training and test set. You can search for the biggest length and create an algorithm that adds the zeros to both datasets. Then let's say a new data you want to predict has a bigger length, then you'll need to recompute all training and test with for this new prediction. You can even check how extending the limit affects your model.

|improve this answer|||||
$\endgroup$
  • $\begingroup$ This isn't feasible if there's no maximum length, correct? $\endgroup$ – ricksmt Dec 29 '15 at 22:11
  • $\begingroup$ yes, that's a problem if you don't have a limit. Let me edit the answer $\endgroup$ – hoaphumanoid Dec 29 '15 at 22:14
  • $\begingroup$ That's a reasonable workaround. Any response to the first question? Is there an algorithm that can produce a varying number of outputs? $\endgroup$ – ricksmt Dec 29 '15 at 22:24
  • $\begingroup$ I'm sorry but it doesn't occur to me. I don't know how a variable output could be managed mathematically. I've always worked with fixed inputs and outputs. $\endgroup$ – hoaphumanoid Dec 29 '15 at 22:27
  • $\begingroup$ No worries. I've never heard of such an algorithm, so I'm not surprised it hasn't been done yet. And as far as I know, most data sets people are interested in are or can be set up with fixed input and output lengths. I'll wait a few days in case someone else knows something we don't, but this is roughly what I expected. $\endgroup$ – ricksmt Dec 29 '15 at 22:33
1
$\begingroup$

So a couple of ways that can be conceived:

  1. @Miguel Gonzalez-Fierro's answer of 0-padding. probably the easiest to implement and makes sense.
  2. If padding is not sensible for your problem, if your output is a time series, you could learn a neural translation model of sorts and have a STOP/END token in your output.
  3. Have a generator based model (like an alteration on a VAE) and then generate a whole bunch of possible inputs, and you can take any # of draws that suffice some criterion (like a mode with little shift having some calculated conditional information).

There are probably others, but I can't think of them right now.

|improve this answer|||||
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.