Re: Looking for collaboration

Bill Armstrong (arms@cs.ualberta.ca)
Mon, 1 Jul 1996 12:28:48 +0200


In comp.ai.fuzzy you write:

..
>logical inference I have developed a fuzzy expert system shell EDIP for
>DOS and MS-Windows.

This sounds very interesting. Is the code for Windows available?

>The main notion of the approach is attribute model when a problem domain
>is described by a number of attributes each of them taking its values
>from the finite sets of the values. The universe is defined as Cartesian
>product of all sets of the values. Each combination of the values of
>attributes represents some state of the problem domain.

The restriction to a finite set of values will be unnecessary
if you change your approach to representing distributions.

>some states are disabled. So knowledge in such an approach is
>represented by a possibility distribution over the universe.

This is the very essence of what information is in computing science
-- and extremely powerful and general idea (but not new, of course).

The
>problem is that real domains are very large, so we need special
>techniques to deal with distributions over them (e.g., if there are 10
>attributes each taking 5 values then the universe consists of about
>10,000,000 elements and, obviously, it is hardly possible to work with
>it in explicit form).

Certainly, dealing with distributions in this way is impossible, but
you could use "neural networks" to learn to synthesize functions. I
put the term in quotes, because what I am going to suggest is not your
usual neural net, but rather an adaptive logic net (ALN) which creates
approximations from linear functions and the operations of max and min,
which are operations that look totally compatible with your operations.

>For representing knowledge in the form of possibility distributions a
>special language has been developed. Its elementary propositions are
>explicitly represented possibility distributions over the sets of the
>values which can be combined by logical connectives AND and OR
>interpreted conventionally as min and max.

Exactly like ALNs!

Rules describing problem
>domain laws are thought of as implications and written in the form of
>disjuncts. A set of disjuncts combined with the connective AND
>represents a knowledge base in the form of a possibility distribution
>over the universe.

When you bring an ALN into CNF or DNF, the number of terms may increase
astronomically. Usually, it is best to leave it in multilayer form.
Furthermore, in DNF or CNF, there are many duplications of variables
that result from representing what is natually a multiayer structure
in this way. You can constrain ALN functions too using fixed parts
of max-min tree structures on linear functions.

>The main operation for carrying out logical inference on such a
>knowledge base is an original resolution principle which generalizes
>classical resolution. This operation is applied to any two disjuncts on
>some variable and results in a third disjunct called resolvent. If the
>resolution is on kth attribute then kth (non-kth) proposition of the
>resolvent is equal to the conjunction (disjunction) of the two
>corresponding propositions from the premises. The correctness and some
>semantic properties of such rather general definition has been proven.
>The resolution was used in the expert system shell EDIP for DOS for
>precompiling its knowledge base into the form containing all prime
>disjuncts. Once the knowledge base has been compiled (i.e., all prime
>disjuncts are found), logical inference on any data in consultation time
>is carried out without any delay for one pass.

Compilation sounds like it would be a long process on non-toy problems.
The kind of problems I would like to deal with have maybe 50,000 variables
with values that are in domains like double floating point and subsets of that.

>Unfortunately, this process (i.e., compilation) does not work already
>for middle size knowledge bases, therefore in the first version for
>MS-Windows we used another method based on transformation form CNF into
>DNF (also in compilation time). This method also is not very effective
>(as well as, probably, all exact methods), so in the last versions of
>the EDIP approximate methods for logical inference have been used.

I like the idea of using (fuzzy) constraint networks on such
variables, grouped into subsets having local fuzzy constraints
represented by ALNs. ALNs are unlike other neural networks-- they are
relational, not functional. You can extract functions from them.
This is like the passage from AND and OR, which form a classification
into two classes (1-on and under the function graph 0-above the
function graph) to the computation of the function using max and min
of linear functions (accelerated by a decision tree).

In many cases, the ALN functions can be inverted, so I see an
inference rule that is based on getting information out of fuzzy
constraint networks. Even non-monotonic functions can be inverted by
binary search as long as one specifies the bounds on the values in the
branch one wants.

Being in Canada, I am not eligible for the US program you mentioned,
however I am trying to develop commercial products based on ALNs. It
would be interesting to try out your software to see if the fit with
ALNs is really as good as it looks. What we have are learning
algorithms that function very well, and a fuzzy integration paradigm
like yours could, with some further development, be just what is
needed. If it were commercially viable, there would be enough money
to finance much more joint activity than the US program can finance.
Please understand that I am not proposing a commercial link yet -- I want to
see if your technology fits ours first.

I hope you will be able to access educational software that shows how
the ALN approach works:

ftp.cs.ualberta.ca in pub/atree/atree3/atree3ek.exe.

That ~900K file also contains a 120-page User's Guide in HTML format
which you can view with Netscape or other WWW browser at your site.

If your computer is not registered on the net, you could have some
problems with the ftp. Then there is another way you can try: get the
uuencoded version via a link from my home page:

http://www.cs.ualberta.ca/~arms

Please let me know what you think of the idea of using ALNs in the
framework of a future version of your system after you have had a
chance to consider the question. If you have trouble getting our
educational software, let me know and I will send a floppy to you. It
is limited to 2 input variables, but illustrates the concepts well.
If we enter into collaboration, my company would provide you with more
powerful versions for your research.

Best wishes,

William W. Armstrong (nickname: "Bill")
President
Dendronic Decisions Limited
3624 - 108 Street
Edmonton, Alberta
Canada
T6J 1B4
Tel/Fax (403) 438 8285.

-- 
* William W. Armstrong, PhD
* U of A: (403) 492 2374  Fax:  (403) 492 1071
* arms@cs.ualberta.ca  http://www.cs.ualberta.ca/~arms
* Home: (403) 438 1103  Business: (403) 438 8285