Sunday, March 18, 2007

AI modelling with undefined state

Roy Simpson, a colleague back at STL in the 1980s where we were doing Artificial Intelligence (AI) and Computer Science (CS) research, wrote to me about some work he was doing which touched on my Ph. D. research here. This is what he said.

"Some years ago I found some theorems and related ideas in the logical basis of CS & AI which looked like they would have interesting implications. Grouped together these ideas got dubbed: "TTM-Network Theory" - the working claim being that it provides the best ever logical foundation for Computational Network theory. A big claim for a small set of results - so the challenge has been to confront well known areas of CS with the TTM ideas to see if the established areas can be improved (& maybe the TTM side improved as well).

Anyway after some encouraging initial results, last year I decided to turn attention to the SRS Model (and Reactive Systems Theory in general). Again the question was: Do the TTM ideas cause any form of re-evaluation of the SRS Model and/or its conclusions? The SRS Model as presented, for example on your website.

The answer was that an ambiguity has been identified in the basic presentation of the SRS Model. The crux of the problem is that we dont get told whether or not the object update functions f1 etc are total or partial. From this ambiguity a series of issues concerning the formal presentation of the material then unwind, these issues may also spill over into the general conclusions (see below).

A possible view is that the functions are total - this is certainly how all the examples are laid out: SCP, L-R, etc. But totality of the functions is a restriction and not the general case - so why should these functions be total? If it is any consolation none of the books or articles I have read on "Computation and Physics" address this question - they all silently assume that such functions will be total. As you can imagine another branch of the TTM research is whether it could make physical (especially quantum) sense to allow partial functions here.

So maybe the SRS update functions are partial? In that case a world like the following can arise:

w(3) = {(a,(1,1),f1),(b,(2,2),f2),(c,(3,U),f3),(d,(4,4),f4)}

- here object c has its external state undefined as a result of the non-termination of its update function from an earlier time.

The next formal problem is how to we define Next to get to w(4)?

Next could be strict so that w(4)=U. This does not seem the proper way to model such a situation (because object c might be independent of the others), so I would argue for Next to be non-strict. We have to be more careful in our formal analysis though, because non-computable functions are also non-strict.....

This was where I left the situation last year (except I checked out current theories of Reactive systems - but that is another story). Recently I have returned to the SRS model to see whether and how these issues might ripple deeper into the SRS model - and another discovery (at least for me) was awaiting!

The problem now is with the PTL (Propositional Temporal Logic) definitions - specifically the valuation function. Consider any predicate on worlds like:

P (w) = For all objects in world w. internal state value=external state value.

Condition P is nearly satisfied by w(3) above except for object c. The undefined value for object c's external state makes the valuation function here undefined. The common solution is to introduce 3-valued logic to model possible non-termination logics (as we know). If we stick to a 2-valued valuation function then the valuation function is non-computable. Anyway I then realised that PTL is actually a Modal Logic and I was now considering a 3 - valued Modal logic for the SRS Model! Except I had never heard of 3-valued Modal logic before! None of the standard references (Hughes, Cresswell, etc) cover it.

I have had to do a Web search for papers on 3-valued (nowadays n-valued or even Heyting algebra valued) Modal Logics. I can see that it is an area that is evolving - with some similarities and differences with the two valued case. Specifically duality between necessity and possibility modal operators is in general lost - they have to be defined separately.

So my recent objective has again been achieved - to show that the theorems which drive the TTM work can open up new areas.

As far as the SRS Theory is concerned there would need to be a re-examination to see how the arguments above affects your conclusions. I am aware that a key part of this re-examination is the question: Does the computational (ie non-termination option) of the model's functions actually help in Cognitive Modelling (ditto physical modelling)? Does the model really just want reliable total functions?

Interestingly your final conclusion is that the multi-agent extension collapsed into well known Protocol theory. Well I wonder if that is still true in the 3-valued case? Three valued Modal logic isnt well known. Then again maybe Protocol theory isnt that general either - another target for my TTM work one day."


--------------------- and my reply

"I think this is quite interesting and would make only three points in response.

1. The SRS model is probably too constrained to be the most suitable structure for the mathematical analysis of either synchronous automata with undefined state-elements or three-valued modal logics. The extra structure in the model is there to handle psychological states. However, I am sure there is some really interesting maths in the addition of undefined elements in automata theory/modal logic, as you suggest.

2. In my naive ontology, which I was getting at with the SRS model, I put in the minimum necessary structure for a multi-object/multi-agent world with non-transparent behaviour (via hidden, private state) which would allow the introduction of intentional modelling (epistemic, doxastic, conative operators). My intuitions did not extend to situations where object next-states would be undefined (and still don't!). If you get any fresh insights at the intentional level please let me know. Of course, in physics terms, the SRS model is hopeless: absolute simultaneity is structurally built-in, plus complete determinacy. It's through-and-through Newtonian!

3. My Ph.D research, as written up on my site, was really modelling bacterium/insect levels of behaviour (despite references to rats and Skinner boxes). I was obviously interested to see to what extent the approach could be extended to human-level cognition, and was led to concerns about ‘what problem does human-level cognition actually solve’. This is now the field of evolutionary psychology, but my stuff was before that.

Just adding in a requirement to communicate doesn't help much, because once you define a 'distributed communications problem' the answer is to design a communications protocol. You gets ants, not people. I concluded that I couldn't easily find a simple framework which transcended this and which led to a tractable model saying something about human cognition, and then time ran out at STL as we became BNR.

I think the fact that this is a really hard problem is evident in the lack of progress since - I suspect that we need lots more brain-scan type data on brain architecture and function before we will have the insights as to what specifically the human brain does differently than, say, that of an insect or a rat - most notably in the consciousness space."