4
$\begingroup$

currently AI is advancing fast in deep learning: Entire human chess knowledge learned and surpassed by DeepMind's AlphaZero in four hours.

As a layman, I'm taking this as a quite powerful searching algorithm, using artificial neural networks to identify the patterns of each game.

However, how good is AI doing in math?

For example, the key to the theory of the game Nim is the binary digital sum of the heap sizes, that is, the sum (in binary) neglecting all carries from one digit to another. This operation is also known as "exclusive or" (xor) or "vector addition over GF(2)".

Is AI good enough to discover/invite operations/logics such as "exclusive or", or, more advanced, abstract algebra in finite field?

$\endgroup$
5
$\begingroup$

Nim was actually one of the first games ever played by an electronic machine. It was called the Nimatron and was displayed at the 1940 New York World's Fair.

It is also well known that neural networks can model the Xor-function, if they have enough layers. Despite that, Marvin Minsky is supposed to have killed neural networks in the sixties, by asserting that networks with a single hidden layer, cannot model XOR.

I think there were also some large scale projects to classify finite groups using computers.

Additionally there have long been automated theorem proving programs, that had some success in mathematical logic. I recently saw a paper that used Deep learning to improve one of these theorem provers.

That being said, doing real mathematics is probably as difficult as real language understanding. There doesn't seem to have been a real breakthrough yet.

$\endgroup$
  • $\begingroup$ May I ask 1) where did Marvin Minsky went wrong? 2) i suppose AI to classify groups still needs human input on the “group” concept? How far is AI from “invent” the concept? Similar to “recognise” an XOR operation for nim? $\endgroup$ – athos Dec 7 '17 at 13:28
  • $\begingroup$ Marvin Minsky didn't go wrong. It was just that the readers of his book over interpreted his statements. Yes, I'm not even sure the group classification can be called AI. I don't know when AI will "invent" the concept of a group, nor am I sure what that would even look like. $\endgroup$ – BlindKungFuMaster Dec 7 '17 at 14:02
2
$\begingroup$

The question of whether nets can be trained to take over more and more of what was entirely within the domain of production systems was asked (to the dismay of those who worked on first order predicate calculus inference in the LISP community) back in the early 1990s.

Artificial Networks Performing Logical Inference

At Stanford University's Department of Linguistics the learning of the logic required to assemble a semantic graph by an artificial net has been demonstrated and documented in Recursive Neural Networks Can Learn Logical Semantics by Samuel R. Bowman, Christopher Potts, and Christopher D. Manning.

Even the earliest work on artificial networks were targetted toward learning logic, such as the elusive exclusive-or operation, which was achieved by adding a second layer to the original perceptron design and applying what we now call gradient descent.

Distinct from Automatic Theorem Proving

Most of the early work on computer proofs of theorems was based on the production system approach (sometimes call expert systems). These are rules based systems, not artificial networks. It was thought that the rules of predicate logic could be executed in proper sequence by pattern matching the antecedents (conditions in which a mathematical technique based on axiomatic information and already proven theory may be applied) in proper order. Some success was achieved using heuristic meta rules.

Using artificial networks to prove a theorem is an entirely different approach. To take semantic learning further so that an artificial network could learn how to assemble a mathematical proof requires three further levels of abstraction in the network learning model.

  • Learning the known first order predicate logic rules of inference
  • Learning the mechanics of applying those rules to proposed theorems
  • Learning functional heuristics to know what to try first

Evidence It Can Be Done

The evidence that artificial networks may be developed which can learn to construct a mathematical proof is not that current artificial nets can perform some natural language functioning or creatively develop a melody or some interior design. The reason DARPA has traditionally invested in neural network research pointed in the direction of simulating logic is the proof of concept proposed by Minsky.

The strongest evidence that neural networks can potentially learn the various layers of abstraction listed above to actually do math is that human children cannot prove a theorem or even read one out loud understandably, yet some may grow up to be proficient in theorem proving. The biological neural nets of the brain must learn such proficiency.

As of this writing, no counter-example exists that an artificial network cannot achieve the proficiency of Gauss or Gödel, so the idea cannot logically be dismissed. Many advanced research projects continue to target higher cognitive skills as their AI objective.

Public Access

It is likely, since much of the work on logical inference and the investigation into whether artificial networks could be trained to do it was funded by government bodies, that some of the results of research is not available to the public.

$\endgroup$
0
$\begingroup$

In maths exist P and NP problems, so AI solve problems (with common algorithms) that are 'verified in polynomial time', because require computational work , if condition solve or converge to solution,well a NP = P, but other cases not converge. Depend of algorithm and election of problem. but when is NP not solve computational work.

$\endgroup$
  • $\begingroup$ Don’t quite get your point, maybe rephrase it a bit? $\endgroup$ – athos Sep 26 '18 at 4:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.