0

I've run into a problem where I have a set of inputs, as well as a couple known input-output pairs. I am interested in the output, but in order to get that, I need to figure out how the input is used to generate the output.

So for example, I might have the following input strings along with a few known output strings

char001 --> dasjudash2 // known input/output
char002 --> ef2y789e2y // known
char003 --> jnjxf9823d // known
char004 --> ?          // unknown output
char005 --> ?          // unknown output

I believe that there may exist some algorithm that takes an input and produces the given output, but this algorithm is unknown. It is very possible that the pairs are randomly generated as well (eg: look at the sky, randomly pick a string of characters). I could stare at it long and hard and try to think of how they are related, but computers can probably help me out.

Basically, given known inputs and outputs, is it possible to come up with potential functions that will take known inputs and generate known outputs, and then use that to take the rest of the inputs and generate the corresponding outputs?

Given that the solution may be one of an infinite possibilities (including the possibility that no solution exists, in the case that someone did just look at the sky and pick random characters out of a hat), I would quickly dismiss it as a computationally infeasible task, but perhaps my intuition is wrong and there is research evidence to show that this problem is solvable?

closed as unclear what you're asking by gnat, Kilian Foth, user40980, Dan Pichelman, jwenting Jul 14 '14 at 9:49

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 3
    Read a book about machine learning; you'll learn how to ask your question in a more meaningful way. – Basile Starynkevitch Jul 10 '14 at 5:12
  • @BasileStarynkevitch Can you explain how the question could be asked in a more meaningful way? While your advice appears to be helpful based on vote count, I have no idea what you are referring to. – That Umbrella Guy Jul 10 '14 at 15:48
  • You are not giving explicitly enough constraints or [mathematical] requirements on your function... (you might want it to be continously differentiable, or whatever....) See the several answers below, and read something about Machine Learning (that I don't know well)... – Basile Starynkevitch Jul 10 '14 at 15:49
  • @BasileStarynkevitch I am only given a set of inputs and outputs and asked whether I can figure out a way to determine how to generate more outputs given additional inputs. The outputs are arbitrary strings of alphanumeric, case-sensitive characters of length 10, and the inputs follow a particular pattern that is described in th example. Other than that, I have no idea whether such a function that I am looking for even exists (because the mappings could be randomly generated) – That Umbrella Guy Jul 10 '14 at 15:55
  • Just a cardinality argument tells you that there are more (arbitrary, uncomputable) functions from A to B than there are elements in A or in B. You did not tell that input has 6 chars and output has 9 chars exactly! – Basile Starynkevitch Jul 10 '14 at 16:19
6

This is a classic machine learning problem. It's an example of regression. You'd want to split your set of "knowns" into two groups, one to train with, and one to test against. Set up the appropriate machine learning algorithm* and train with part of your knowns. Then input the other set of inputs to check the reliability of the answer against the known outputs. Repeat.

That's the short version -- there's lots of work and learning that goes in the middle.

One note, however, is that odds are, when you find some mapping from the inputs to the outputs, you won't be able to decipher what it means. It might be in the form of a series of rectangular arrays of floating point numbers. The actual solution that does the mapping will probably end up being a bunch of parameters to some underlying calculation that just works, without being clear why.

* insert tons of hard work here

  • This really is the correct answer. – Silviu Burcea Jul 10 '14 at 7:15
4

You should definitely get more experience in theoretical computer science. This function is trivial to define. Say you have pairs p_i = (I_i, O_i) of input/output pairs, then you can define f(I) by a simple chained if-else, in which you test whether I == I_i and then return O_i for each i. Given that your I_i are unique (i.e. your pairs show determinism of the output calculation), this function clearly reproduces all your input/output pairs correctly.

Therefore, there may never be no solution. However, it will also never be an interesting solution, as it doesn't do much of anything, let alone correctly handle other inputs. Furthermore, you can never guess a function that returns the correct result for the new input char004, simply, because the definition of correct is lacking.

Mathematically speaking, you are always free to define functions partially, i.e. f(x) = x for all x except your I_i inputs and f(I_1) = O_1, f(I_2) = O_2, .... Due to that, if you only provide a certain number of points, you can never be able to tell anything about a general function that produces it. In mathematics we therefore often limit the function we are looking for in certain ways. For example, if you want to find a non-partially defined polynomial function, then a pair of input/outputs can get you much closer. But for that to work, we have to rely on things like continuity.

Unless you add some similar restriction for your desired functions, there will always be infinitely many uninteresting solutions.

  • Yes, which is why I specified that the algorithm would search for "candidate" solutions, of which one may be correct, because the process of determining whether it is correct or not is up to something else. – That Umbrella Guy Jul 10 '14 at 15:47
1

It is trivial to generate functions that map the known inputs to known outputs and the other inputs to some outputs. It is, however, impossible to generate functions that map the other inputs to the "right" outputs, simply because you don't know what the "right" outputs are.

Or, put another way: since you don't know what the outputs should be, I can give you just about any function and you have no reason to believe that it is not the correct one.

def algorithm_guesser(name, known_inputs)
  define_method(name) do |input| known_inputs[input] or raise ArgumentError end
end

algorithm_guesser(:mystery_function, 
  'char001' => 'dasjudash2', 
  'char002' => 'ef2y789e2y', 
  'char003' => 'jnjxf9823d')

mystery_function('char001')
# => 'dasjudash2'

mystery_function('char004')
# ArgumentError

Of course, this is not terribly useful, but it is as correct as any other function you can come up with.

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