4 ms·

For anyone coming in a bit confused by this, the magic here is in the concept of "differentiable". I'm fairly frequently touting the benefits of thinking in ter

For anyone coming in a bit confused by this, the magic here is in the concept of "differentiable". I'm fairly frequently touting the benefits of thinking in terms of differentiable programming and the most common response is "what does that even mean?" The core idea is that any program that is "differentiable" means you can take the derivative of that program the same way you can take the derivative of a simple function in calculus. Why does that matter? Well being able to take the derivative of any problem in turn means you can then optimize that problem with gradient descent. Chris Olah recently had a great discussion on Twitter [0] about what's great about gradient descent, in short: > Simple gradient descent creates mind-boggling structure and behavior, just as evolution creates the awe inspiring complexity of nature. Differentiable programming is, in a strange way, similar to logic programming in the sense that you can start solving problems by defining what the solution looks like. In this example you define the input and desired output and then learn the FSM that maps one to the other. Recall from Theory of Computation classes that a FSM the simplest, least powerful programming language (FSM an example of a regular language). What's amazing here is that you're essentially seeing gradient descent writing a program. IMHO, that is insanely cool. What makes differentiable programming so interesting compared to something like logic programming is that you have a potentially much larger space of problems that can be solved in this manner and compared to the backtracking algorithm used by logic programming languages, gradient descent allows for potentially faster (though also approximate) solutions at scale. Currently the vast majority of differentiable programming examples are essentially just building neural nets, but examples like this one show that we can think much more broadly about problems in terms of differentiable programming as a proper programming paradigm. 0. https://twitter.com/ch402/status/1533164918886703104?cxt=HHwWgICpxdzX8sYqAAAA https://twitter.com/ch402/status/1533164918886703104?cxt=HHw...

nshm 4y ago
Seems like in this differentiable FSM implementation you only differentiate edge weighs, you can not introduce or change nodes. So it is quite far from differentiation of programs.
- uoaei 4y ago
  But if you add a huge number of nodes and put regularization on the sparsity of the edge weights, you have essentially a model which can adapt to problems using subsets of its structure. Somewhat like the "lottery ticket" hypothesis in NN theory. Then you can think of each traversal choice as a conditional branch and voila, the program runs! You can see this in effect actually in the article when the author uses the penalty on the entropy of the transition probabilities.
  - jiggawatts 4y ago
    Something that just occurred to me: finite state machines don't have to be a single "flat" graph. There are hierarchical/nested variations. For example, imagine a factory with many identical machines, where each machine has the same FSM for its operation, and then there's a FSM for the factory as a whole, modelling the interactions of the machines. I wonder, I wonder, I wonder... could there be a differentiable and deeply nested FSM hierarchy model that -- like deep learning for neural nets -- can solve qualitatively different categories of problems compared to a "plain" FSM? As in, just as deep learning revolutionised ML, I wonder if there is an equivalent "deep FSM learning". It smells like there's something fundamental there: Take "any" simple, differentiable systems like a layer of neural nets, an FSM, or whatever... and then make it "deep". Similarly, I wonder if all of the other concepts from NNs could have equivalents for similar differentiable systems, such as convolution, etc...
    - nshm 4y ago
      The standard operation for FSM to compose knowledge sources is composition. You can compose different level graphs and differentiate them too. Awni's paper talks about that https://openreview.net/pdf?id=MpStQoD73Mj https://openreview.net/pdf?id=MpStQoD73Mj. The problem is that you need to differentiate graph structure, not just weights. This is a problem since the weights are inherently non-continuous.
melony 4y ago
Regular expressions were invented to model neurons (predating gradient descent) by Kleene of the Kleene star. C.f. "Representation of Events in Nerve Nets and Finite Automata" Before backpropagation was a glimmer in LeCun's eyes.
jonstewart 4y ago
“In the terms of Brzozowski…”
JohnHaugeland 4y ago
> For anyone coming in a bit confused by this, the magic here is in the concept of "differentiable". I'm fairly frequently touting the benefits of thinking in terms of differentiable programming and the most common response is "what does that even mean?" One way of looking at it is "differentiable is a specific mathematical claim from calculus, usually about equations or inequalities, that says that you can perform a specific operation to get a reduced variant." People in ML care about differentiability because many of our most important tools, such as gradient descent, require it as a characteristic. Another way of looking at it is "this is not a useful product and with enough vocabulary people may not notice that"

nshm 4y ago

Seems like in this differentiable FSM implementation you only differentiate edge weighs, you can not introduce or change nodes. So it is quite far from differentiation of programs.

uoaei 4y ago
But if you add a huge number of nodes and put regularization on the sparsity of the edge weights, you have essentially a model which can adapt to problems using subsets of its structure. Somewhat like the "lottery ticket" hypothesis in NN theory. Then you can think of each traversal choice as a conditional branch and voila, the program runs! You can see this in effect actually in the article when the author uses the penalty on the entropy of the transition probabilities.
- jiggawatts 4y ago
  Something that just occurred to me: finite state machines don't have to be a single "flat" graph. There are hierarchical/nested variations. For example, imagine a factory with many identical machines, where each machine has the same FSM for its operation, and then there's a FSM for the factory as a whole, modelling the interactions of the machines. I wonder, I wonder, I wonder... could there be a differentiable and deeply nested FSM hierarchy model that -- like deep learning for neural nets -- can solve qualitatively different categories of problems compared to a "plain" FSM? As in, just as deep learning revolutionised ML, I wonder if there is an equivalent "deep FSM learning". It smells like there's something fundamental there: Take "any" simple, differentiable systems like a layer of neural nets, an FSM, or whatever... and then make it "deep". Similarly, I wonder if all of the other concepts from NNs could have equivalents for similar differentiable systems, such as convolution, etc...
  - nshm 4y ago
    The standard operation for FSM to compose knowledge sources is composition. You can compose different level graphs and differentiate them too. Awni's paper talks about that https://openreview.net/pdf?id=MpStQoD73Mj https://openreview.net/pdf?id=MpStQoD73Mj. The problem is that you need to differentiate graph structure, not just weights. This is a problem since the weights are inherently non-continuous.

melony 4y ago

Regular expressions were invented to model neurons (predating gradient descent) by Kleene of the Kleene star. C.f. "Representation of Events in Nerve Nets and Finite Automata" Before backpropagation was a glimmer in LeCun's eyes.

jonstewart 4y ago

“In the terms of Brzozowski…”

JohnHaugeland 4y ago

> For anyone coming in a bit confused by this, the magic here is in the concept of "differentiable". I'm fairly frequently touting the benefits of thinking in terms of differentiable programming and the most common response is "what does that even mean?" One way of looking at it is "differentiable is a specific mathematical claim from calculus, usually about equations or inequalities, that says that you can perform a specific operation to get a reduced variant." People in ML care about differentiability because many of our most important tools, such as gradient descent, require it as a characteristic. Another way of looking at it is "this is not a useful product and with enough vocabulary people may not notice that"