8 ms·

Linear logic and deep learning [pdf]

170 points by adamnemecek 9y ago

YeGoblynQueenne 9y ago
>> So I’d like to begin by summarising some of the recent history in the field of artificial intelligence, or machine learning as its now called. To be more precise, the field is still known as AI, but people outside the field only know (and care) about machine learning, presumably because that's what Googe, Facebook, et al are recruiting for. This is a bit of a sad situation, really. AI, in its drive to solve major hard problems (that still remain unsolved btw), has always contributed powerful programming techniques and even entire language paradigms to computer science (functional programming, object orientation that basically started with Minsky's frames, all sorts of search algos etc). Machine learning is just one such technique which has gained popularity outside AI. It's powerful, for restricted problems. But if it somehow replaces AI in peoples' mind, the goose that lays the golden eggs might just die.
- thomasahle 9y ago
  > Machine learning is just one such technique which has gained popularity outside AI. I'd argue the machine learning label can be applied to any AI system that's data-driven in some sense (even self-generating the data using reinforcement learning). Wikipedia lists the following approaches to Machine Learning. Surely you wouldn't call them all 'one technique'?: Decision tree learning, Association rule learning, Artificial neural networks, Deep learning, Inductive logic programming, Support vector machines, Clustering, Bayesian networks, Reinforcement learning, Representation learning, Similarity and metric learning, Sparse dictionary learning, Genetic algorithms.
  - regularfry 9y ago
    AI used to cover Expert Systems, which have nothing we'd recognise as a "learning" phase at all. Hell, it used to cover parsers.
  - YeGoblynQueenne 9y ago
    Let's say that it's a class of techniques that learn models (or progams, in the case of ILP) from data. My main concern is not about defining what machine learning is, however. Rather, I'm worried about the definition of AI shrinking to "it's what we now call machine learning". Which is at the very least unhistorical.
    - breatheoften 9y ago
      I thought it was common for people to think of AI as largely disjoint from machine learning ... AI covering all the expert/rule based systems, grammars, and search algorithms with ML being pretty strictly referring to techniques for building predictive models from datasets ...
      - YeGoblynQueenne 9y ago
        Well, machine learning arose partly from the need to find a better way to create rule-bases than hand-crafting them, painstakingly and at great cost. You can see this more clearly in the work of early pioneers like Ryszard Michalski, or in inductive inference (the field preoccupied with learning automata from examples). All these have always been well in the purview of classical AI. Then of course there's the connectionist branch that explicitly set out to take inspiration from the human brain. I don't think that anyone ever saw neural networks as anything but AI for the last 50 years or so. In any case, when the connectionist were having arguments, they were having them with other AI folks, not with, say, statisticians, or mathematicians. Then, if you think about the classic tasks that machine learning systems perform, they're all firmly classic AI tasks: classification, game-playing, machine vision, speech processing, etc etc. I mean, the fact that models are "predictive" on its own doesn't tell you that machine learning is separate from AI. After all, an intelligent agent must be able to make predictions about its environment and the outcome of its actions on this environment.
- davesque 9y ago
  Isn't it kind of reaching to say that the field of AI contributed the entire functional paradigm of computation? Can you say more about why you think that's the case?
noelwelsh 9y ago
I haven't had time to get into the details of this, but I'm very interested in differentiable programming that doesn't repeat the mistakes of imperative programming. I'd like to understand how the model in this work differs from, e.g. http://www.bcl.hamilton.ie/~barak/papers/sound-efficient-ad2008.pdf http://www.bcl.hamilton.ie/~barak/papers/sound-efficient-ad2...
- neel_k 9y ago
  At a super high level, the central problem is higher-order functions. If you have a programming language, you can think of differentiation as being a higher-order function that takes a function a and returns a new function as a result. If your language has support for higher-order functions, then (a) you have to extend the definition of the derivative to cope with differentiation at higher type, and (b) ideally you'd like differentiation to be an operator in your programming language. In general this is hard, so you have to cut the problem somewhere. Pearlmutter and Siskind's basic idea is to use Reynolds defunctionalization transformation to turn higher-order programs into first-order programs, and then apply automatic differentiation to the resulting first-order program. The approach in this talk is inspired by "differential lambda calculus", which is a setting where you retain full first-class functions, but restrict how you can use them by imposing certain typing constraints upon them (basically to ensure smoothness/differentiability of definable functions). There is a mysterious connection between these ideas, since defunctionalization is closely related to the "geometry of interaction" semantics of linear logic, and differential lambda calculus is closely related to the vector space semantics of linear logic. In addition to these semantic issues, there's also the question of how you hook it up to the actual algorithms people use to do gradient descent -- eg you need to use the Riesz representation theorem to justify representing the gradient as a matrix -- and that constrains how things could work even further. This is simultaneously annoying (because it makes things harder) and helpful (at higher type we have too much freedom in how to define the derivative, and so additional requirements help constrain the solution space). So you might ask: why do we care so much about higher-order functions? The answer is that "higher-order function" is how semanticists pronounce "linking" and "separate compilation". It would be super great if we could take a bunch of teeny-tiny separately-developed models together, stick them together, and have everything work no problem.
tw1010 9y ago
To a trained mathematician, deep learning is so so far away from the cutting edge. If there's anything that's going to make a massive, revolutionary not evolutionary, change in the deep learning landscape, it's not going to come from engineers walking around on the surface of what's already there, it'll come from pure mathematicians connecting it to the insights ripe for the picking found deep deep down in the theoretical dirt.
- regularfry 9y ago
  Often the trick is not to make the new thing, but to make the old thing comprehensible so someone else can pick it up and run with it.
  - tw1010 9y ago
    I agree. The real low hanging fruit is not new research, but to make the easy, basic first or second year graduate math understandable in the context of ML.
  - alexilliamson 9y ago
    Or applying the old thing in a new way to a different audience, like Einstein using Lorentzian manifolds.
- lou1306 9y ago
  On a similar note, taking a look at a mathematician's coursebooks made me realize how puny our mathematical tools are. Most Computer Science topics only rely on (relatively) basic concepts from logic, algebra, calculus, and/or probability. The hardest course I ever attended was a quantum computing one, and even that does not require much, apart from a generalization of probability theory to complex numbers. I bet there are lots of brilliant results that a smart mind could apply to our field.
  - reader5000 9y ago
    I think the human brain is capable of only grasping so much abstraction. I'm sure every genius working in the deepest areas of advanced mathematics has heard of deep learning. If there was some amazing concept from their field directly applicable to deep learning we would have heard about it by now.
dmurfet 9y ago
Author here. The theoretical background can be found in: https://arxiv.org/abs/1407.2650 https://arxiv.org/abs/1407.2650 https://arxiv.org/abs/1701.01285 https://arxiv.org/abs/1701.01285 http://therisingsea.org/notes/MScThesisJamesClift.pdf http://therisingsea.org/notes/MScThesisJamesClift.pdf As neel_k notes, a good way to understand this picture is in terms of differential linear logic (a refinement of simply-typed differential lambda calculus). I did not provide references in the talk as unfortunately I did not understand the subject at the time, but the introduction to the second paper above hopefully serves to remedy that omission. Suffice to day that Ehrhard and Regnier discovered something quite profound in differential lambda calculus, the implications of which are still being explored; this discovery should have significant bearing on what people refer to as differentiable programming, I think. The third link above is the master’s thesis of my talented student James Clift. We have subsequently extended that work and are finishing a paper which explains the computational content of derivatives of Turing machines, according to differential linear logic. This might be of interest to people here. I will post a link when we put it online.
- yaseer 9y ago
  Fantastic stuff! Does your work still keep the non-determinism of Ehrhard and Regnier? This was the part that 'bothered' me, but it provided evidence of a link with process calculi. I've also thought Ehrhard and Regnier's work was groundbreaking. It potentially opens up not just insights into differentiable programming, but a theory of concurrent computation and an algebraic theory of computation. My expectation is that it will reveal some deep links with other areas of mathematics, like group theory.
  - yaseer 9y ago
    P.S - Silly question, I can see it does. I responded before reading.
  - dmurfet 9y ago
    I think you are right, the meaning of the sums that appear in syntactic derivatives is quite subtle, and I don’t claim to have an authoritative answer as to their deep meaning. Semantically, however, I think things are clearer. The denotation of the syntactic derivative of a proof is a limit, and the terms in the limit have an interpretation as probabilistic processes in a (close to) standard sense. So while the sum-over-linear-substitutions doesn’t have a clear probabilistic interpretation (at least that I can see) it is the limit of computational processes where you run the probability of making a substitution to zero. I don’t know anything about process calculi, unfortunately!
kruhft 9y ago
"Lively Linear Lisp--'Look Ma, No Garbage!'". ACM Sigplan Notices 27, 8 (August 1992),89-98. How to implement a 'linear' language efficiently through 'behind the scenes' hash consing. http://home.pipeline.com/~hbaker1/LinearLisp.html http://home.pipeline.com/~hbaker1/LinearLisp.html
- kruhft 9y ago
  From the abstract: Linear logic has been proposed as one solution to the problem of garbage collection and providing efficient "update-in-place" capabilities within a more functional language. Linear logic conserves accessibility, and hence provides a mechanical metaphor which is more appropriate for a distributed-memory parallel processor in which copying is explicit. However, linear logic's lack of sharing may introduce significant inefficiencies of its own. We show an efficient implementation of linear logic called Linear Lisp that runs within a constant factor of non-linear logic. This Linear Lisp allows RPLACX operations, and manages storage as safely as a non-linear Lisp, but does not need a garbage collector. Since it offers assignments but no sharing, it occupies a twilight zone between functional languages and imperative languages. Our Linear Lisp Machine offers many of the same capabilities as combinator/graph reduction machines, but without their copying and garbage collection problems.
- deleted 9y ago
  [deleted]
bitL 9y ago
Is it possible to extend this to relevance logic?
- dmurfet 9y ago
  I don’t think so, but I haven’t really thought about it.
osense 9y ago
I don't understand why the type of bint was chosen, and what impact, exactly, does it have on the usability of the network. Or, asked differently: Given some task that you want to train your network for, how do you decide which type you should choose?
- danharaj 9y ago
  The type bint is an encoding of binary sequences, so it's simple enough as a working example but it's nontrivial enough that you could construe any sort of learning algorithm as operating on it. The type you choose is part of the model you're training so your question is as difficult as "what kind of network topology should I use?".
  - dmurfet 9y ago
    Right. In practice one would want to use more complicated types (such as the type of Turing machines, explained in Clift’s thesis) but in the talk I did not have time to explain more interesting examples.
mjgeddes 9y ago
Yes, we need a logic-based approach rather than a statistical one for NLP if you want to incorporate things like attention and memory. The full range of non-classical logics should be looked at, including Modal, Fuzzy etc. We need to extend the logic-based approach to deal with reasoning under uncertainty, so many-valued logic is needed. Also, we need the logic to be able to model discrete, dynamical systems, so we need to look at Temporal Logic, Situation Calculus , Event Calculus etc etc. You can call all this 'Computational Logic'; it may actually be more general than probability theory. See my wiki-book listing the central concepts of 'Computational Logic' here: https://en.wikipedia.org/wiki/User:Zarzuelazen/Books/Reality_Theory:_Computational%26Non-Classical_Logic https://en.wikipedia.org/wiki/User:Zarzuelazen/Books/Reality... Functional programming is best for handling the logic-based approach, for example Haskell. Functional programming languages work at a higher-level than ordinary imperative and procedural programming, since functional programming deals with the manipulation of knowledge itself rather states of the computer. I'd also look closely at the pure mathematical origins of computational logic, including classical mathematical logic and category theory. Type theory (a constructive form of category theory) looks like it forms the basis for language rules, thus making it ideal for NLP. I conjecture that an extension of computational logic leads to a solution to machine psychology (inc. NLP), analogous to how machine learning can be viewed as an extension of probability and statistics. Probability&Stats >>> Machine Learning By analogy, Computational Logic >>> Machine Psychology (inc. NLP)

170 points by adamnemecek 9y ago

>> So I’d like to begin by summarising some of the recent history in the field of artificial intelligence, or machine learning as its now called. To be more precise, the field is still known as AI, but people outside the field only know (and care) about machine learning, presumably because that's what Googe, Facebook, et al are recruiting for. This is a bit of a sad situation, really. AI, in its drive to solve major hard problems (that still remain unsolved btw), has always contributed powerful programming techniques and even entire language paradigms to computer science (functional programming, object orientation that basically started with Minsky's frames, all sorts of search algos etc). Machine learning is just one such technique which has gained popularity outside AI. It's powerful, for restricted problems. But if it somehow replaces AI in peoples' mind, the goose that lays the golden eggs might just die.

thomasahle 9y ago
> Machine learning is just one such technique which has gained popularity outside AI. I'd argue the machine learning label can be applied to any AI system that's data-driven in some sense (even self-generating the data using reinforcement learning). Wikipedia lists the following approaches to Machine Learning. Surely you wouldn't call them all 'one technique'?: Decision tree learning, Association rule learning, Artificial neural networks, Deep learning, Inductive logic programming, Support vector machines, Clustering, Bayesian networks, Reinforcement learning, Representation learning, Similarity and metric learning, Sparse dictionary learning, Genetic algorithms.
- regularfry 9y ago
  AI used to cover Expert Systems, which have nothing we'd recognise as a "learning" phase at all. Hell, it used to cover parsers.
- YeGoblynQueenne 9y ago
  Let's say that it's a class of techniques that learn models (or progams, in the case of ILP) from data. My main concern is not about defining what machine learning is, however. Rather, I'm worried about the definition of AI shrinking to "it's what we now call machine learning". Which is at the very least unhistorical.
  - breatheoften 9y ago
    I thought it was common for people to think of AI as largely disjoint from machine learning ... AI covering all the expert/rule based systems, grammars, and search algorithms with ML being pretty strictly referring to techniques for building predictive models from datasets ...
    - YeGoblynQueenne 9y ago
      Well, machine learning arose partly from the need to find a better way to create rule-bases than hand-crafting them, painstakingly and at great cost. You can see this more clearly in the work of early pioneers like Ryszard Michalski, or in inductive inference (the field preoccupied with learning automata from examples). All these have always been well in the purview of classical AI. Then of course there's the connectionist branch that explicitly set out to take inspiration from the human brain. I don't think that anyone ever saw neural networks as anything but AI for the last 50 years or so. In any case, when the connectionist were having arguments, they were having them with other AI folks, not with, say, statisticians, or mathematicians. Then, if you think about the classic tasks that machine learning systems perform, they're all firmly classic AI tasks: classification, game-playing, machine vision, speech processing, etc etc. I mean, the fact that models are "predictive" on its own doesn't tell you that machine learning is separate from AI. After all, an intelligent agent must be able to make predictions about its environment and the outcome of its actions on this environment.
davesque 9y ago
Isn't it kind of reaching to say that the field of AI contributed the entire functional paradigm of computation? Can you say more about why you think that's the case?

noelwelsh 9y ago

I haven't had time to get into the details of this, but I'm very interested in differentiable programming that doesn't repeat the mistakes of imperative programming. I'd like to understand how the model in this work differs from, e.g. http://www.bcl.hamilton.ie/~barak/papers/sound-efficient-ad2008.pdf http://www.bcl.hamilton.ie/~barak/papers/sound-efficient-ad2...

neel_k 9y ago
At a super high level, the central problem is higher-order functions. If you have a programming language, you can think of differentiation as being a higher-order function that takes a function a and returns a new function as a result. If your language has support for higher-order functions, then (a) you have to extend the definition of the derivative to cope with differentiation at higher type, and (b) ideally you'd like differentiation to be an operator in your programming language. In general this is hard, so you have to cut the problem somewhere. Pearlmutter and Siskind's basic idea is to use Reynolds defunctionalization transformation to turn higher-order programs into first-order programs, and then apply automatic differentiation to the resulting first-order program. The approach in this talk is inspired by "differential lambda calculus", which is a setting where you retain full first-class functions, but restrict how you can use them by imposing certain typing constraints upon them (basically to ensure smoothness/differentiability of definable functions). There is a mysterious connection between these ideas, since defunctionalization is closely related to the "geometry of interaction" semantics of linear logic, and differential lambda calculus is closely related to the vector space semantics of linear logic. In addition to these semantic issues, there's also the question of how you hook it up to the actual algorithms people use to do gradient descent -- eg you need to use the Riesz representation theorem to justify representing the gradient as a matrix -- and that constrains how things could work even further. This is simultaneously annoying (because it makes things harder) and helpful (at higher type we have too much freedom in how to define the derivative, and so additional requirements help constrain the solution space). So you might ask: why do we care so much about higher-order functions? The answer is that "higher-order function" is how semanticists pronounce "linking" and "separate compilation". It would be super great if we could take a bunch of teeny-tiny separately-developed models together, stick them together, and have everything work no problem.

tw1010 9y ago

To a trained mathematician, deep learning is so so far away from the cutting edge. If there's anything that's going to make a massive, revolutionary not evolutionary, change in the deep learning landscape, it's not going to come from engineers walking around on the surface of what's already there, it'll come from pure mathematicians connecting it to the insights ripe for the picking found deep deep down in the theoretical dirt.

regularfry 9y ago
Often the trick is not to make the new thing, but to make the old thing comprehensible so someone else can pick it up and run with it.
- tw1010 9y ago
  I agree. The real low hanging fruit is not new research, but to make the easy, basic first or second year graduate math understandable in the context of ML.
- alexilliamson 9y ago
  Or applying the old thing in a new way to a different audience, like Einstein using Lorentzian manifolds.
lou1306 9y ago
On a similar note, taking a look at a mathematician's coursebooks made me realize how puny our mathematical tools are. Most Computer Science topics only rely on (relatively) basic concepts from logic, algebra, calculus, and/or probability. The hardest course I ever attended was a quantum computing one, and even that does not require much, apart from a generalization of probability theory to complex numbers. I bet there are lots of brilliant results that a smart mind could apply to our field.
- reader5000 9y ago
  I think the human brain is capable of only grasping so much abstraction. I'm sure every genius working in the deepest areas of advanced mathematics has heard of deep learning. If there was some amazing concept from their field directly applicable to deep learning we would have heard about it by now.

dmurfet 9y ago

Author here. The theoretical background can be found in: https://arxiv.org/abs/1407.2650 https://arxiv.org/abs/1407.2650 https://arxiv.org/abs/1701.01285 https://arxiv.org/abs/1701.01285 http://therisingsea.org/notes/MScThesisJamesClift.pdf http://therisingsea.org/notes/MScThesisJamesClift.pdf As neel_k notes, a good way to understand this picture is in terms of differential linear logic (a refinement of simply-typed differential lambda calculus). I did not provide references in the talk as unfortunately I did not understand the subject at the time, but the introduction to the second paper above hopefully serves to remedy that omission. Suffice to day that Ehrhard and Regnier discovered something quite profound in differential lambda calculus, the implications of which are still being explored; this discovery should have significant bearing on what people refer to as differentiable programming, I think. The third link above is the master’s thesis of my talented student James Clift. We have subsequently extended that work and are finishing a paper which explains the computational content of derivatives of Turing machines, according to differential linear logic. This might be of interest to people here. I will post a link when we put it online.

yaseer 9y ago
Fantastic stuff! Does your work still keep the non-determinism of Ehrhard and Regnier? This was the part that 'bothered' me, but it provided evidence of a link with process calculi. I've also thought Ehrhard and Regnier's work was groundbreaking. It potentially opens up not just insights into differentiable programming, but a theory of concurrent computation and an algebraic theory of computation. My expectation is that it will reveal some deep links with other areas of mathematics, like group theory.
- yaseer 9y ago
  P.S - Silly question, I can see it does. I responded before reading.
- dmurfet 9y ago
  I think you are right, the meaning of the sums that appear in syntactic derivatives is quite subtle, and I don’t claim to have an authoritative answer as to their deep meaning. Semantically, however, I think things are clearer. The denotation of the syntactic derivative of a proof is a limit, and the terms in the limit have an interpretation as probabilistic processes in a (close to) standard sense. So while the sum-over-linear-substitutions doesn’t have a clear probabilistic interpretation (at least that I can see) it is the limit of computational processes where you run the probability of making a substitution to zero. I don’t know anything about process calculi, unfortunately!

kruhft 9y ago

"Lively Linear Lisp--'Look Ma, No Garbage!'". ACM Sigplan Notices 27, 8 (August 1992),89-98. How to implement a 'linear' language efficiently through 'behind the scenes' hash consing. http://home.pipeline.com/~hbaker1/LinearLisp.html http://home.pipeline.com/~hbaker1/LinearLisp.html

kruhft 9y ago
From the abstract: Linear logic has been proposed as one solution to the problem of garbage collection and providing efficient "update-in-place" capabilities within a more functional language. Linear logic conserves accessibility, and hence provides a mechanical metaphor which is more appropriate for a distributed-memory parallel processor in which copying is explicit. However, linear logic's lack of sharing may introduce significant inefficiencies of its own. We show an efficient implementation of linear logic called Linear Lisp that runs within a constant factor of non-linear logic. This Linear Lisp allows RPLACX operations, and manages storage as safely as a non-linear Lisp, but does not need a garbage collector. Since it offers assignments but no sharing, it occupies a twilight zone between functional languages and imperative languages. Our Linear Lisp Machine offers many of the same capabilities as combinator/graph reduction machines, but without their copying and garbage collection problems.
deleted 9y ago
[deleted]

bitL 9y ago

Is it possible to extend this to relevance logic?

dmurfet 9y ago
I don’t think so, but I haven’t really thought about it.

osense 9y ago

I don't understand why the type of bint was chosen, and what impact, exactly, does it have on the usability of the network. Or, asked differently: Given some task that you want to train your network for, how do you decide which type you should choose?

danharaj 9y ago
The type bint is an encoding of binary sequences, so it's simple enough as a working example but it's nontrivial enough that you could construe any sort of learning algorithm as operating on it. The type you choose is part of the model you're training so your question is as difficult as "what kind of network topology should I use?".
- dmurfet 9y ago
  Right. In practice one would want to use more complicated types (such as the type of Turing machines, explained in Clift’s thesis) but in the talk I did not have time to explain more interesting examples.

mjgeddes 9y ago

Yes, we need a logic-based approach rather than a statistical one for NLP if you want to incorporate things like attention and memory. The full range of non-classical logics should be looked at, including Modal, Fuzzy etc. We need to extend the logic-based approach to deal with reasoning under uncertainty, so many-valued logic is needed. Also, we need the logic to be able to model discrete, dynamical systems, so we need to look at Temporal Logic, Situation Calculus , Event Calculus etc etc. You can call all this 'Computational Logic'; it may actually be more general than probability theory. See my wiki-book listing the central concepts of 'Computational Logic' here: https://en.wikipedia.org/wiki/User:Zarzuelazen/Books/Reality_Theory:_Computational%26Non-Classical_Logic https://en.wikipedia.org/wiki/User:Zarzuelazen/Books/Reality... Functional programming is best for handling the logic-based approach, for example Haskell. Functional programming languages work at a higher-level than ordinary imperative and procedural programming, since functional programming deals with the manipulation of knowledge itself rather states of the computer. I'd also look closely at the pure mathematical origins of computational logic, including classical mathematical logic and category theory. Type theory (a constructive form of category theory) looks like it forms the basis for language rules, thus making it ideal for NLP. I conjecture that an extension of computational logic leads to a solution to machine psychology (inc. NLP), analogous to how machine learning can be viewed as an extension of probability and statistics. Probability&Stats >>> Machine Learning By analogy, Computational Logic >>> Machine Psychology (inc. NLP)