Re: AGI research using ocaml

Re: AGI research using ocaml

[oleg]

Eray Ozkural wrote:

> AFAICT, there is no [BER MetaOCaml] native code support for x64. 
> Are there any plans to upgrade to 3.12 and x64?

Well, 3.12 hasn't been officially released yet. There is strong
intention to upgrade to 3.12 once the release dust settles.

The byte-code BER MetaOCaml should work on all architectures supported
by OCaml. Native-code BER MetaOCaml will come after the port to 3.12.
It would be at first for i386, since that is the system I have access
to. Generally once native BER MetaOCaml is done, it should work on all
architectures that support dynamic linking; that claim has to be
experimentally confirmed though.

AGI research using ocaml

[Eray Ozkural]

Hello there,

I recently did some interesting research on Artificial General
Intelligence using ocaml. Following the
research directions we had set with late Ray Solomonoff, I designed an
incremental machine
learning system. You can read about it on the AGI-2010 site:
http://agi-conf.org/2010/conference-schedule/

There is an extended abstract in the conference, which contains a
hyperlink to a draft of a
technical description of the program. If you're curious, go ahead and
read it, please.

Basically, this is an implementation of Adaptive Levin Search, the
most sophisticated of its kind that I
know of. And we have made significant algorithmic improvements to make
that happen, as you can
imagine.

There is similar research going on at Google, but they're taking a
different approach AFAICT. I
favor mine, because I'm trying to make a good practical approximation
of Solomonoff induction
which will serve as an AGI kernel in several cognitive architectures.
So, mathematical rigor comes
first.

I've used the ocs interpreter for interpreting Scheme programs. Thanks
to Ocaml, I was able to try
out several different search and update algorithms rather
effortlessly. And I think it didn't take much
more  than a month for me to finish the implementation. I wrote the
bulk of the program in a weekend or
two. Who knows, perhaps a future AGI system will have been written in ocaml.

Of course, all of this is possible due to the genius of Ray. He will
be sorely missed.

Now, a small question. What is the best way for me to use a caml
interpreter in ocaml? I have to
run millions of small caml programs, so startup latency can't be
tolerated. (For instance I can't execute
a unix process to interpret a program) I've decided that caml
represents more technological progress
than scheme, and I can definitely use the type system for better
search performance.

Best,

-- 
Eray Ozkural, PhD candidate.  Comp. Sci. Dept., Bilkent University, Ankara
http://groups.yahoo.com/group/ai-philosophy
http://myspace.com/arizanesil http://myspace.com/malfunct

Re: [Caml-list] AGI research using ocaml

[blue storm]

[-- Attachment #1: Type: text/plain, Size: 2760 bytes --]

It is difficult to understand what you say with no previous knowledge of
your field (wich is probably not a common knowledge among OCaml hackers).
The fact that you paper is named "Stochastic Grammar Based Incremental
Machine Learning Using Scheme" doesn't help.

If I understand correctly (feel free to correct myself) :

1) your field of research is "automatic program generation to solve a set of
given tasks" : you generate random programs in a given language, with a
mathematic theory giving you probability distribution for various syntaxic
elements, until you find one that achieve your goal. You have a "learning
mechanism" that can reuse previous solution (such as declared functions) for
helping further tasks

2) You generate Scheme program fragments

3) Your algorithm/generator is written in OCaml, using the ocs Ocaml Scheme
interpreter to test your generated programs

4) You would like to generate OCaml program fragments instead of Scheme.
Your idea is that the type system, imposing more constraints on the legal
program, will reduce the search space and accelerate your generator.


In the example you give (square root, nand), you use only a tiny subset of a
general programming language features. Why did you choose to target the full
Scheme, instead of a minimalistic Lisp/Scheme subset ? It seems to me that
targeting a bigger language (wich additional feature your generator probably
doesn't know about anyway) will mainly incur an overhead on program
evaluation.
It is reasonable if you can access an already existing interpretor/evaluator
implementation that suit your need (reusing one of the available scheme
interpreters makes more sense than reimplementing one for scratch, maybe
even for a tiny subset of the langauge).
However, I'm not sure you can have something similar for OCaml : the only
used OCaml implementation is the INRIA implementation, wich has bytecode and
native compilers, but are not specially easy to invoke programmatically with
low startup times requirements. Perhaps the bytecode compiler would be quick
enough for your need, you should try.
I think the easiest way for you would be to implement a small language with
a ML typing system, and a tiny (but not algorithmically inefficient)
interpreter for it. On small program fragments, a small interpreter would
probably be much more interesting that calling an external tool. Besides,
you could design your small language accordingly to your generator
abilities.

You might also be interesting in minimal ML interpreters/compilers projects.
The two that I know of are :
- MiniML in Andrej Bauer "Programming language Zoo" :
http://andrej.com/plzoo/html/miniml.html
- MinCaml, a tiny ML compiler by Eijiro Sumii :
http://min-caml.sourceforge.net/index-e.html

[-- Attachment #2: Type: text/html, Size: 3007 bytes --]

Re: [Caml-list] AGI research using ocaml

[Eray Ozkural]

Hello BlueStorm,

I assume you're an AI of some sort ;)

On Sat, Mar 13, 2010 at 3:21 PM, blue storm <bluestorm.dylc@gmail.com> wrote:
> It is difficult to understand what you say with no previous knowledge of
> your field (wich is probably not a common knowledge among OCaml hackers).
> The fact that you paper is named "Stochastic Grammar Based Incremental
> Machine Learning Using Scheme" doesn't help.

It would be impossible for anybody to construct Algorithmic Probability Theory
on his own in little time. In fact, that's why I'm working on
incremental machine learning, for
there is no way one can simply come up with all the results in a
branch of science
from zero ground. We stand on the shoulders of the giants, which is the problem
I'm working on: general-purpose long-term memory.

> If I understand correctly (feel free to correct myself) :

Please go ahead, I'll do my best to clarify.

> 1) your field of research is "automatic program generation to solve a set of
> given tasks" : you generate random programs in a given language, with a
> mathematic theory giving you probability distribution for various syntaxic
> elements, until you find one that achieve your goal. You have a "learning
> mechanism" that can reuse previous solution (such as declared functions) for
> helping further tasks

Yes, although I don't generate random programs. Programs in the current system
are generated in a deterministic order. It's basically a search in the space of
leftmost-derivations of Scheme programming language. This is the induction step.

You are right, however, that program generation could be random.

I have a saying on the relation of all this to better known AI
research subjects:

Algorithmic Probability Theory is to Genetic Programming what
Statistical Learning Theory is to Neural Network Learning.

That is, it is a general principle of induction, that's known to have
very small generalization error. And there are proposed ways of
achieving this, like Adaptive Levin Search.

In a nutshell, you could say that it is an advanced kind of GP.

> 2) You generate Scheme program fragments

Yes.

> 3) Your algorithm/generator is written in OCaml, using the ocs Ocaml Scheme
> interpreter to test your generated programs

That's right.

> 4) You would like to generate OCaml program fragments instead of Scheme.
> Your idea is that the type system, imposing more constraints on the legal
> program, will reduce the search space and accelerate your generator.

Absolutely. For simpler function induction problems, I assume this
could even be done automatically by inducing type constraints over a
set of examples. Part of future research, I think. I am afraid I'll
have to read many programming language papers!

> In the example you give (square root, nand), you use only a tiny subset of a
> general programming language features. Why did you choose to target the full
> Scheme, instead of a minimalistic Lisp/Scheme subset ? It seems to me that
> targeting a bigger language (wich additional feature your generator probably
> doesn't know about anyway) will mainly incur an overhead on program
> evaluation.

Correct. But that was done to illustrate two (mainly obscure) points.
First, that we
can tackle a real-world programming language in its whole glory.
Second, actually recursive
problems are not required to know that the system is in principle of
doing such, for recursive
problems have been previously solved.

Obviously, future problems will feature recursion. For instance, Towers of Hanoi
was solved previously. It would be interesting to reproduce that
result in Scheme to
see if that solution depended on a specific (lucky) initial condition.

> It is reasonable if you can access an already existing interpretor/evaluator
> implementation that suit your need (reusing one of the available scheme
> interpreters makes more sense than reimplementing one for scratch, maybe
> even for a tiny subset of the langauge).

Yes.

> However, I'm not sure you can have something similar for OCaml : the only
> used OCaml implementation is the INRIA implementation, wich has bytecode and
> native compilers, but are not specially easy to invoke programmatically with
> low startup times requirements. Perhaps the bytecode compiler would be quick
> enough for your need, you should try.

Compilation would probably be overkill. The evaluation shouldn't make
any unnecessary
syscall's, access files, etc.

> I think the easiest way for you would be to implement a small language with
> a ML typing system, and a tiny (but not algorithmically inefficient)
> interpreter for it. On small program fragments, a small interpreter would
> probably be much more interesting that calling an external tool. Besides,
> you could design your small language accordingly to your generator
> abilities.

Yes, something like that is done in ADATE IIRC.

> You might also be interesting in minimal ML interpreters/compilers projects.
> The two that I know of are :
> - MiniML in Andrej Bauer "Programming language Zoo" :
> http://andrej.com/plzoo/html/miniml.html
> - MinCaml, a tiny ML compiler by Eijiro Sumii :
> http://min-caml.sourceforge.net/index-e.html

Thank you.

Best Regards,

-- 
Eray Ozkural, PhD candidate.  Comp. Sci. Dept., Bilkent University, Ankara
http://groups.yahoo.com/group/ai-philosophy
http://myspace.com/arizanesil http://myspace.com/malfunct

Re: AGI research using ocaml

[Stefan Monnier]

>> 4) You would like to generate OCaml program fragments instead of Scheme.
>> Your idea is that the type system, imposing more constraints on the legal
>> program, will reduce the search space and accelerate your generator.
> Absolutely.  For simpler function induction problems, I assume this
> could even be done automatically by inducing type constraints over a
> set of examples.  Part of future research, I think.  I am afraid I'll
> have to read many programming language papers!

Depending on how you want to use types, it can help, but not
necessarily:

If you manage to use types to restrict your search, then that's great,
since your programs will be properly typed by construction (and the host
language may even know that, e.g. using GADTs or something equivalent)
and you may indeed be able to interpret them faster.

But if you don't, then you end up with programs which may or may not be
properly typed, in which case types will allow you to reject programs
before running them, but at the cost of having to type-check every
program.  So if the run time of each program is short compared to the
program's size, it may end up more costly to type-check the code than to
just run it.


        Stefan