Comment by YeGoblynQueenne | Hacker News Reader

Comment by YeGoblynQueenne | Hacker News Reader

YeGoblynQueenne

>> First, the tool asks for an input-output example of the desired tensor transformation. Then, it runs a combinatorial search to find TensorFlow expressions that perform that transformation.

Ouch! The combinatorial space of arbitrary programs is huge. This can't work for programs of any but the smallest size.

Indeed:

>> There are limitations to TF-Coder. It can currently find solutions involving 3-4 operations within a minute of searching, but solutions involving 6 or more operations are too complex to find in a reasonable amount of time.

Btw, my PhD research is pretty much on something like this but learning Prolog programs from examples, rather than Python. The problem is extremly hard and all solutions so far look at ways to restrict the large hypothesis search spaces, mainly by imposing some kind of strong inductive or language bias (i.e. restricting what can be learned and how) but there is always a point beyond which any way one tries to search for an arbitrary program will fall into a huge search space and disappear down a myriad winding paths that lead nowhere. So while it's interesting to see this effort (taking hints from natural language is a nice touch) program syntehsis or program learning will not be solved by any search-based algorithm.

Edit: Actually, the bit about how solutions involving 6 or more operations take forever to return, is eerily familiar. An algorithm I was working on at the start of my PhD was pretty much limited to programs of 5 clauses (roughly, 5 function calls). I'm sure it's a coincidence but, golly.

I think the intended usage is not to find your whole program from example. Instead the programmer breaks the program down into simple operations, and uses this tool to remember what the name of that operation is. And finding short compositions is a bonus.

There is certainly a lot of use that one can make out of a program with this kind of limitation, but it is a limitation- if it wasn't, there wouldn't be a warning about it in the article.

In any case, if there was no such limitation most people here would be out of a job now, so it's an important limitation.

>> And finding short compositions is a bonus.

You mean because they can be easily inspected and debugged and edited by hand if required? If so, yes, I agree. But, for example, the algorithm I worked with, that I discuss above, a big criticism of the underlying technique has always been that _in practice_ it's limited to learning small programs.

No, I mean finding short compositions is a bonus feature over finding a single function from example.

OK, I don't understand what you mean. Can you explain?

Being able to find one_hot from input/output example is already useful, because you might skip over that name thinking it's some weird machine learning thing and you just want to set element values.

You could easily lose an hour building and testing a solution based on stacking your desired indices with ranges and feeding it to scatter_nd.

I think I understand now, but just to be sure- you mean that being able to find expressions that do what you want fom examples of what you want, is a big bonus because it speeds up your programming? i.e. a sort of enhanced search function?

Yes exactly. But only for tensorflow. Not for programming languages in general.

I can give another example use case.

Say I know math but don't know tf api. I already know how to matrix multiply with `@` but don't know the function for matrix power.

Then in theory it should be fairly quick for me to create a random matrix and feed it `mat @ mat`, `mat @ mat @ mat`, `mat @ mat @ mat @ mat`, etc until it spits out the correct tf function I should call for matrix_power.

This is even better than googling since it guarantees that the function it found is correct for your example (googling returns tf.pow tf.exp tf.expm, none of which are actually what you want!)

Thanks, I see what you two mean. It didn't occur to me that programming with tensors can be so challenging and I thought the authors just big it up a little to motivate the work - as one does :)

It's more that programming with math is hard.

When communicating in mathematics you often assume the reader can understand precisely which mathematical object you're talking by extrapolating from ellipses "...". For example "the naturals are 1,2,3,4,..." or "the evens are 2,4,6,8,..."

Or I might tell you a shift matrix is something that looks like:

  [0 1 0 0 0]
  [0 0 1 0 0]
  [0 0 0 1 0]
  [0 0 0 0 1]
  [0 0 0 0 0]

And that single example with the suggestive naming should be enough for most people to understand what a shift matrix is for arbitrary size.

But if you want to explain what a shift matrix is to a computer, you must use a formal definition (and to do it idiomatically you need to know esoteric details like that numpy.diagonal takes in an offset parameter so you can do something like https://stackoverflow.com/a/30230801).

It would be nice if we can talk math with a computer in the same intuitive language we use with humans, just give it a few examples and it will generate the the rest and let you double check the formula is correct.

So I see stuff like tf-coder as a great step, not for synthesizing programs we don't know how to solve, but for language translation: between math notation and programming notation.

And the reason it's hard is because of how heavily tensorflow discourages flow control and reusable general purpose constructs for efficiency and differentiability reasons. Instead you have to use the list of blessed special purpose things.

I wonder whether the same effect could be achieved with a better designed programming language, though. If the problem is ambiguity- there's nothing stopping a programming language from accepting ambiguous statements, which of course it would then interpret unambigously, according to context. It's just that this takes a lot of work and it's really not the done thing in terms of programming languages as far as I can tell- for reasons of eficiency of parsing also, I think.

Anyway I guess I'm turnning into the typical stuffy academic who can't even begin to think of real-world applications, hah. Thanks for pointing out the practical uses of the work described in the article.

Reply on news.ycombinator.com