4 ms·

A transformer is unable to really represent logic, let alone higher order logic and theorem proving.

neolog 6y ago
Where can I read more about this?
6gvONxR4sf7o 6y ago
A transformer is a universal function approximator. The question is whether it can do so reasonably efficiently. Trained on natural language linear sequences, I’m with you. Trained on abstract logical graph representations? I don’t think that question’s answered yet, unless I’m missing something.
- westurner 6y ago
  How do transformers handle with truth tables, logical connectives, and propositional logic / rules of inference, and first-order logic? Truth table: https://en.wikipedia.org/wiki/Truth_table https://en.wikipedia.org/wiki/Truth_table Logical connective: https://en.wikipedia.org/wiki/Logical_connective https://en.wikipedia.org/wiki/Logical_connective Propositional logic: https://en.wikipedia.org/wiki/Propositional_calculus https://en.wikipedia.org/wiki/Propositional_calculus Rules of inference: https://en.wikipedia.org/wiki/Rule_of_inference https://en.wikipedia.org/wiki/Rule_of_inference DL: Description logic: https://en.wikipedia.org/wiki/Description_logic https://en.wikipedia.org/wiki/Description_logic (... The OWL 2 profiles (EL, QR, RL; DL, Full) have established decideability and complexity: https://www.w3.org/TR/owl2-profiles/ https://www.w3.org/TR/owl2-profiles/ ) FOL: First-order logic: https://en.wikipedia.org/wiki/First-order_logic https://en.wikipedia.org/wiki/First-order_logic HOL: Higher-order logic: https://en.wikipedia.org/wiki/Higher-order_logic https://en.wikipedia.org/wiki/Higher-order_logic In terms of regurgitating without critical reasoning? Critical reasoning: https://en.wikipedia.org/wiki/Critical_thinking https://en.wikipedia.org/wiki/Critical_thinking
  - riku_iki 6y ago
    Transformer is a function from seq of symbols to seq of symbols. For example, truth table is exactly similar kind of function from variables to [True, False] alphabet. Transformer can represent some very complex logical operations, and per this article is turing complete: https://arxiv.org/abs/1901.03429 https://arxiv.org/abs/1901.03429, meaning any computable function, including theorem prover can be represented as transformer. Another question is if it is feasible/viable/rational to build transformer for this? My intuition says: no.
  - 6gvONxR4sf7o 6y ago
    Think about a program that can write code but not execute it. It’s not hard to get a transformer to learn to write python code like merge sort or simple arithmetic code, even though a transformer can’t reasonably learn to sort, nor can it learn simple arithmetic. It’s an important disambiguation. In one view it appears it can’t (learn to sort) and in another it demonstrably can (learn to code up a sort function). It can learn to usefully manipulate the language without needing the capacity to execute the language. They probably can’t learn to “execute” what you’re talking about (execute being a loose analogy), but I’d say the jury’s out on whether they can learn to usefully manipulate it.

Where can I read more about this?

A transformer is a universal function approximator. The question is whether it can do so reasonably efficiently. Trained on natural language linear sequences, I’m with you. Trained on abstract logical graph representations? I don’t think that question’s answered yet, unless I’m missing something.

westurner 6y ago
How do transformers handle with truth tables, logical connectives, and propositional logic / rules of inference, and first-order logic? Truth table: https://en.wikipedia.org/wiki/Truth_table https://en.wikipedia.org/wiki/Truth_table Logical connective: https://en.wikipedia.org/wiki/Logical_connective https://en.wikipedia.org/wiki/Logical_connective Propositional logic: https://en.wikipedia.org/wiki/Propositional_calculus https://en.wikipedia.org/wiki/Propositional_calculus Rules of inference: https://en.wikipedia.org/wiki/Rule_of_inference https://en.wikipedia.org/wiki/Rule_of_inference DL: Description logic: https://en.wikipedia.org/wiki/Description_logic https://en.wikipedia.org/wiki/Description_logic (... The OWL 2 profiles (EL, QR, RL; DL, Full) have established decideability and complexity: https://www.w3.org/TR/owl2-profiles/ https://www.w3.org/TR/owl2-profiles/ ) FOL: First-order logic: https://en.wikipedia.org/wiki/First-order_logic https://en.wikipedia.org/wiki/First-order_logic HOL: Higher-order logic: https://en.wikipedia.org/wiki/Higher-order_logic https://en.wikipedia.org/wiki/Higher-order_logic In terms of regurgitating without critical reasoning? Critical reasoning: https://en.wikipedia.org/wiki/Critical_thinking https://en.wikipedia.org/wiki/Critical_thinking
- riku_iki 6y ago
  Transformer is a function from seq of symbols to seq of symbols. For example, truth table is exactly similar kind of function from variables to [True, False] alphabet. Transformer can represent some very complex logical operations, and per this article is turing complete: https://arxiv.org/abs/1901.03429 https://arxiv.org/abs/1901.03429, meaning any computable function, including theorem prover can be represented as transformer. Another question is if it is feasible/viable/rational to build transformer for this? My intuition says: no.
- 6gvONxR4sf7o 6y ago
  Think about a program that can write code but not execute it. It’s not hard to get a transformer to learn to write python code like merge sort or simple arithmetic code, even though a transformer can’t reasonably learn to sort, nor can it learn simple arithmetic. It’s an important disambiguation. In one view it appears it can’t (learn to sort) and in another it demonstrably can (learn to code up a sort function). It can learn to usefully manipulate the language without needing the capacity to execute the language. They probably can’t learn to “execute” what you’re talking about (execute being a loose analogy), but I’d say the jury’s out on whether they can learn to usefully manipulate it.