Monthly Archives: January 2017

Bootstrapping CAIA Part II: Choosing a new domain

 There are many ways to increase the range of problems that CAIA could solve. For instance, one can introduce continuous variables, or define unknowns with an infinite number of possible values. It would also be interesting to consider meta-problems, that can be convenient to CAIA when it is solving a problem, for instance to monitor the search for solutions. Meta-problems are particularly useful in a bootstrap; however, when I made my last choice, I was afraid that it was too early to include such meta-problems: I didn’t have enough experience for monitoring the search for a solution. For this reason, I chose to consider problems where the unknowns may have an infinite number of possible values.

Firstly, this allows to have a large number of problems, mainly in arithmetic. More importantly, this necessitates to find new methods, different from those used for solving constraint satisfaction problems. Indeed, for these problems, the combinatorial method always gives all the solutions; it may be practically unusable, especially when the problem is intractable. However, this is a starting point, which can be improved.

Naturally, when an unknown may have an infinite number of possible values, one can no longer use the combinatorial method. Other methods must be used, some of them similar to theorem proving. This does not prevent to develop a tree, for instance one can consider several possibilities for an unknown: x<0, x=0, and x>0, or also x is even and x is odd. For many problems, looking at all the possible values, even very cleverly, is not always the best method; CAIA is obliged to experiment with other approaches in this new domain.

When the system stops, the result from these problems may be:

The proof that there is no solution: find two integers a and b such that 4a+3b²=34.

The discovery of all the solutions: find three integers a, b, et c, greater than a given integer k, such that the three remainders of the division of a.b by c, of b.c by a, and of c.a by b are all equal to k. For instance, if k=12, one solution is a=293892, b=1884, and c=156; in all, there are 792 solutions.

The discovery of one or several families describing an infinite number of solutions, which include all the possible solutions: find two integers a and b such that 4a+3b²=36 (any integer value for x, a=9-3x², b=2x).

There is a solution for every combination of the possible values of the unknowns: find n such that 2006 divides 2005n-1887n-1954n+1836n ; this constraint is true for any positive integer value of n.

No solution, or a finite, or an infinite number of solutions, have been found, but one has not proven that there is no other solution. This happens when one is stuck for at least one leaf of the tree.

For the combinatorial search in constraint satisfaction problems, sometimes one has not all the results because the resolution may require too much time, especially when the problem is intractable. Here, there is a new possibility: one does not see what could be done, all the known methods have been unsuccessfully used. In the tree, we have not only as value for the leaves: solution, or contradiction, or not enough time, but also: one does not know what to do.

 When a system results from a bootstrap, too often it does not find some solutions, although it believes that it has completed its task. When CAIA finds a solution, it is always correct; however, as the search is not as systematic as when the set of possible values are finite, sometimes it erroneously concludes that there is a contradiction, or it wrongly eliminates a possible value for an unknown. When a system builds itself its method for finding solutions, a misguided modification in the knowledge that creates these methods can improve its performances in some situations, but may introduce particularly vicious mistakes in parts that led before to excellent results. I have experimented with systems where I gave knowledge, and with others where I also gave meta-knowledge creating knowledge. Undeniably, developing the second approach is tremendously more difficult. One reason is that, if AI systems are brittle, systems that result from a bootstrap are much more brittle. In another post, we have seen the problems coming from meta-bugs.

Naturally, to proceed further, it is necessary to introduce new kinds of problems, until it can solve any problem. As of now, I do not want to consider other families of basic problems, such as games or various mathematical theories. I prefer to add families of meta-problems that will be useful at the meta level, where one has to build new methods for solving problems, or to monitor efficiently the search for solutions. It is much more necessary for quickly moving forward in this bootstrap, and particularly to have a less brittle system: experience has shown that, when CAIA does something for me, it does it better than myself.