4 ms·
> Besides if I understand correctly, Metamath, was used as the "ground truth" for evaluation and testing of the trained language model and the language model di
by alexlyzhov 6y ago
> Besides if I understand correctly, Metamath, was used as the "ground truth" for evaluation and testing of the trained language model and the language model didn't get anywhere near 100% performance, meaning it's far behind the ability of Metamath in automated theorem proving.
I'm new to this but wiki says Metamath refers to language + proof checker. It doesn't refer do a method of proof search right? Isn't it just a database of proofs? I'm confused.
Can you please shine light on traditional approaches that are better than DL approaches at proof search? And on how the setting they are evaluated in is different from the evaluation setting in this paper?
- YeGoblynQueenne 6y agoProof verification is traditionally considered an automated theorem proving task. In short, being able to automatically decide the validity of a proof is almost as useful as being able to generate a valid proof automatically. A lot of work has gone into automated theorem proving since the early 20th century. The wikipedia page is a place to start if you are interested in more details: https://en.wikipedia.org/wiki/Automated_theorem_proving https://en.wikipedia.org/wiki/Automated_theorem_proving This work includes proof checkers, for which wikipedia also has a page, though it doesn't have a lot of meat on its bones and you'll have to follow the links to the systems listed yourself: https://en.wikipedia.org/wiki/Proof_assistant https://en.wikipedia.org/wiki/Proof_assistant I'm not an expert on proof checkers, but I hear a lot about Coq and Lean, lately, so you might want to start there. Traditional approaches to automated theorem proving, in the sense of generating new proofs (rather than checking the validity of proofs) include, for example, Robinson's resolution algorithm that is at the heart of the logic programming language Prolog. Such traditional approaches are "better than DL" in the sense that they are provably sound (they only return correct results) and complete (they return all correct results) under certain assumptions. Given the impossibility of empirically checking the proof of every possible theorem, e.g. in first order logic, given finite resources, such system are typically evaluated theoretically, i.e. by proofs of their properties. So for instance, there are proofs of the soundness and completeness of resolution for the purpose of deciding entailment between FOL theories given as sets of Horn clauses. I keep returning to resolution because I happen to be familiar with it, but there are other approaches, of course, though I believe many use some kind of inference rule (e.g. Modus Ponens) and a search procedure usually assisted by some heuristics to find the best next step in a proof.
- lostmsu 6y ago> In short, being able to automatically decide the validity of a proof is almost as useful as being able to generate a valid proof automatically. This statement is not known to be true, and is definitely false in practice at the moment. Validating proofs is a P complexity task, so generating proofs is by definition NP, very likely NP-complete.
- YeGoblynQueenne 6y agoI'm sorry, but what is "practice at the moment"? I'm not any expert on interactive theorem provers.
- lostmsu 6y agoIt means there's no known polynomial algorithm.
- YeGoblynQueenne 6y agoHow does this have to do with "practice at the moment"? Don't you mean "practice" as in what people actually do, in practice? I don't understand where complexity comes in to that. From what I can tell, work in generating new proofs, in the style of Logic Theorist, has dried up and interactive theorem provers are very popular, even among some mathematicians, so they clearly are useful. Anycase, far be it from me to discourage opportunistic nitpicking or pedantry, my favourite sports, but, amicably, I don't understand what you are trying to tell me. I'm curious and I'd like to know. If you have the time and patience, please clarify.
- lostmsu 6y agoGenerating proof validity is a trivial task. Generating new proofs is not.
- YeGoblynQueenne 6y ago
- YeGoblynQueenne 6y agoAfter our conversation I had a look around and I found Vampire, which rang a bell. This is what deep learning theorem provers must beat: The World Championship for Automated Theorem Proving http://www.tptp.org/CASC/ http://www.tptp.org/CASC/ More to the point, they probably need to beat this: https://vprover.github.io/trophies.html https://vprover.github.io/trophies.html Vampire is an automated theorem prover that has been winning some category of the world championship since 1999. See, automated theorem provers can do pointless, stupid SOTA benchmarks, too.
- red75prime 6y agoNotice that 2018 winner in LTB category is MaLARea 0.6, NN-based theorem prover. History repeats itself. Programs, which use hand-crafted heuristics, compete with NN-based programs for a time and then they are left behind. Like Stockfish and Leela Zero.
- YeGoblynQueenne 6y agoMaLARea won a single category in two years, out of 11 categories in a competition running since 1996 (though not all categories were used each year). Furthermore, there were five other winners in the same category since the first entry of MaLARea. I think your enthusiasm is a little premature.
- red75prime 6y agoIt's just an observation that handcrafted heuristics, which are required to mitigate combinatorial explosion, time after time give way to heuristics produced by machine learning. Haar cascades, various OCR techniques, rule-based translation, chess heuristics for alpha-beta search, pre NN speech recognition techniques etc.
- YeGoblynQueenne 6y agoI'm not sure I like the "heuristics" terminology with respect to machine learning, but let's agree to it, for simplicity. Now, in automated theorem proving (ATP hence) there aren't only heuristics. For example, the resolution rule (used by the Vampire theorem prover) is not a heuristic, but an inference rule that comes with soundness and completeness results. It's what I would call a principled choice, i.e. one fully justified by theory. As to combinatorial explosion, in resolution that is not mitigated by heuristics, but by restricting the problem, e.g. to definite logic programs, etc. See, the problem with ATP is not that we don't know good ways to perform ATP tasks- we do. We have very good algorithms that do that kind of thing. Algorithms that come with theoretical guarantees of optimality. Complexity results. Soundness and completenes results. Decidability results. All that jazz. So there is no real reason to look for approximations of the same algorithms, as might be learned by a neural network- because, why approximate something for which you already have a precise definition? The real problem with ATP is the huge, unmanageable size of the hypothesis spaces - and the many negative rersults, e.g. of the undecidability of arbitrary first order logic languages, etc. These are not even efficiency problems that can really be addressed by better algorithms, or heuristics- they're fundamental problems associated with having finite resources, in a universe with finite time and having to explore an infinite domain. These are not the kinds of problems one solves by throwing a lot of data at an optimisation procedure. Contrast this with chess. The search space for chess moves is finite, though large. We don't have a principled "solution" for chess, like a closed-form solution, or an inference rule- just some search procedures guided by heuristics (minimax and its ilk, including MCTS). Here, an approximation is a good alternative, because really that's all we've been able to do so far. In ATP on the other hand, there are principled solutions and we don't have to rely on heuristics and approximations. So, one has no reason to expect that neural nets can do well in ATP just because they've done well in chess. As to the observation that neural nets have done well in diverse domains, here there's a bit of a survivorship bias at play I think, because for example, neither you nor me really are in a position to know in how many domains neural nets have been applied and didn't do so well, because that kind of work never sees the light of day- unlike the success stories, like chess or Go. So again you can't make very good predictions by looking at what has gone before. In any case, who knows. I might have to eat my words at some point. Never say never and all that. EDIT: Sorry about this part of my earlier comment: "I think your enthusiasm is a little premature." Re-reading it, it comes across as snarky and dismissive. That was not my intention, or if it was at the time of writing, I regret it.