AI and XForms

The author Steven Pemberton, CWI, Amsterdam

Contents

Why AI

We try to get a computer program to act like a human.

Or maybe even better

Knowledge

We build up knowledge by observation, identifying patterns, and learning.

Knowledge

Methods

There are at currently two streams for doing AI

Encoding knowledge

Let's take an example.

Encoding knowledge rules

Noughts and Crosses/Tic Tac Toe: I imagine everyone here can play it perfectly.

Exercise: encode for yourself the rules you use for playing the game.

Do this declaratively, not procedurally: given a particular state of the board, how would you respond?

Encoding states

Although there are nearly 20,000 possible combinations of X, O and blank on the board, surprisingly, there are only 765 unique possible (legal) board positions, because of symmetries.

For instance, these 4 are all the same:

X    
 
   
    X
 
   
   
 
X    
   
 
    X

Symmetries

These 8 are all the same:

X    O
 
   
   X
 
  O

 O  
 
 X  
   
 
 O   X

 O   X
 
   
    O
 
    X

 X  
 
O  
   
 
 X   O

Encoding knowledge

So we take each of the 765 boards, and then record which move we would do from that position.

Now we have an encoding of our knowledge of noughts and crosses, and the program can use that to play against an opponent.

Learning

Again enumerate all 765 boards

Link each board with its possible follow-on boards. For instance, for the empty board (the initial state) there are only three possible moves:

   
 
   

to

   
  X
   
X   X
 
X   X
  X
 X X
  X

Second move

From the centre position start move, there are only two possible responses:

   
  X
   

to

 O   O
  X
 O   O
  O
 O  X O
   O

Second move

From the corner position start move there are five responses:

X  
 
   

to

X  
  O
   
X  
 
    O

X  O
O
   
X   O
 
O  
X  
  O
  O

Second move

From the edge first move there are also five responses:

   
X
   

to

   
X O
   
   
X O
   

O  
X
O  
 
X
  O
    O
X
    O

And so on

So we have linked all possible board situations to all possible follow-on positions.

Give each of those links a weight of zero.

Learning program

Play the computer against itself:

Repeatedly make a randomly chosen move from the current board until one side wins, or it's a draw.

When one side has won, add 1 to the weight of each link the winner took, and subtract one from each link the loser took. (Do nothing for a draw)

Then repeat this, playing the game many, many times.

Use the program

Playing against a human, when it's the program's turn, from the current board position make the move with the highest weight.

Comparison

The two methods have different advantages and disadvantages.

Encoding

⊖ You can only encode what you know.
⊖ This may encode bias.
⊕ You can work out why a decision was made (or get the program to tell you why).

Learning

⊖ Only as good as the training material.
⊖ This can also encode hidden bias.
⊕ It may spot completely new things.

In both cases: it's not true intelligence.

It's not true intelligence

I wrote two versions of the noughts and crosses game:

They play differently!

For instance, for the first move, the first one always goes for the centre, and the second always goes for a corner.

In one we have encoded the intelligence that corners are equivalent. The learning program can't work that out for itself.

Pareidolia

Humans are inclined to interpret things from a personal point of view.

Faces

Sphex Wasp

A sphex Wasp

Seeing things that aren't there:

Swans feeding fish

Swans apparently feeding fish

Eliza

In the 60's Joseph Weizenbaum created a program that imitated a Rogerian psychotherapist.

In a classic example, a departmental secretary who was trying it out, asked Weizenbaum to leave the room, because she wanted to talk personally to it.

LaMDA

Recently a similar thing occurred with a Google employee claiming an AI chat program was sentient.

At least the program passed the Turing test.

Generalising

Rule based systems:

Generalised rules

Condition → Consequence
Condition → Consequence
Condition → Consequence

A consequence may have an effect on other conditions, making those true, and therefore generating more consequences, effectively chaining rules together.

Generalised learning

Current AI techniques try to emulate how brains work, by simulating neurons.

Neurons

Neuron

A Neuron

A neuron has a number of inputs (the dendrites) and a single output (the axon) which connects to other neurons via synapses.

BruceBlaus, CC BY 3.0, via Wikimedia Commons

Simulated neurons

In the simulation, a neuron has a number of (binary) inputs, each carrying a weight. The products of each input and its weight are summed to give a value. If this value exceeds a certain threshold, the neuron fires, setting its output to 1.

(We know that this is Turing complete, since you can model a computer using only NAND neurons with two inputs and one output).

Networks

There are two types of network that are used:

Feed forward

Feedforward network

Feed forward networks are static - they produce a consistent output for a set of inputs. They have no time-based memory: previous states have no effect.

Feedback

Feedback network

Feedback networks are dynamic. The network has time-based states.

Learning

Since we have binary inputs and binary outputs, the knowledge is in the weights assigned to the inputs.

Initially random weights are assigned.

There is a large set of training data giving the outputs you should get for particular data.

This data is put through the system, adjusting the weights in order to get the required outcomes.

There are many variants of algorithms for adjusting weights, and I am not going to present them here, and, frankly, there's a degree of wizardry involved.

Using

Once the weights have been calculated on the training data, then the network can be used for analysing new data.

Advantages

The advantage of learning systems vs encoded knowledge systems, is that the learning systems may spot things we weren't aware of.

The disadvantage is that we can no longer determine why it produces a result that it does. It becomes an unanalysable black box.

Advantages

The advantage of learning systems vs encoded knowledge systems, is that the learning systems may spot things we weren't aware of.

The disadvantage is that we can no longer determine why it produces a result that it does. It becomes an unanalysable black box.

An AI making a fool of itself

Dangers

A danger of both the encoded knowledge and the learning system is that they can both end up encoding bias.

A rule-based encoding system is going to end up encoding the encoder's bias.

A learning system is going to end up representing the bias implicit in the teaching data.

XForms

Invariants

Essential mechanism within XForms.

Relationships are specified between values: if a value changes, for whatever reason, its dependent values are changed to match.

This may then generate a chain of changes along dependent values.

Similar to spreadsheets, but: much more general.

Example: Map Application

Source

Map

About 90 lines of XForms.

Not a single while statement.

Dijkstra in his seminal book A Discipline of Programming first pointed out that the principle purpose of a while statement in programming is to maintain invariants.

It is then less surprising that if you have a mechanism that automatically maintains invariants, you have no need for while statements.

How it works

High-level abstraction: there is a two-dimensional position of a location in the world, and a value for the magnification or zoom value required; a map is maintained centred at that location.

It uses a service that delivers (square) map tiles for a region covering a set of locations at a particular zoom level:

http://<site>/<zoom>/<x>/<y>.png

Tiles

The coordinate system for the tiles is as a two-dimensional array.
At the outermost level, zoom 0, there is a single tile

Outermost tile

Tiles

At the next level of zoom, 2×2 tiles,

Zoom 1 Zoom 1
Zoom 1 Zoom 1

Tiles

At the next level 4×4, then 8×8, and so on, up to zoom level 19.

Zoom 2 Zoom 2 Zoom 2 Zoom 2
Zoom 2 Zoom 2 Zoom 2 Zoom 2
Zoom 2 Zoom 2 Zoom 2 Zoom 2
Zoom 2 Zoom 2 Zoom 2 Zoom 2

Calculation

For the tile for a location in world coordinates, calculate from the zoom how many locations are represented by each tile, and divide:

scale=226 - zoom
tilex=floor(worldx ÷ scale)
tiley=floor(worldy ÷ scale)

In XForms:

<bind ref="scale" calculate="power(2, 26 - ../zoom)"/>
<bind ref="tileX" calculate="floor(../worldX div ../scale)"/>
<bind ref="tileY" calculate="floor(../worldY div ../scale)"/>

These are not assignments, but invariants – statements of required equality: if zoom changes then scale will be updated. If scale or worldX changes, then tileX will be updated, and so on.

Tile

It is equally easy to calculate the URL of the tile:

<bind ref="tile"
      calculate="concat(../site, ../zoom, '/',
                        ../tileX, '/', ../tileY,
                        '.png')"/>

and displaying it is as simple as

<output ref="tile" mediatype="image/*"/>

For a larger map, it is easy to calculate the indexes of adjacent tiles.

So displaying the map is clearly easy, and uses simple invariants.

Panning

Making the map pannable uses the ability of keeping the mouse coordinates and state of the mouse buttons as values.

When the mouse button is down, the location of the centre of the map is the sum of the current location and the mouse coordinates.

As this value changes, so the map display is (automatically) updated to match.

Advantages

The advantages of the invariant approach:

Implementation

XForms uses a straightforward ordered-graph based dependency algorithm, ordered since circular dependencies are disallowed.

A dependency graph

Updates are triggered by changes to values, and updates are then ordered along the dependency chain and applied.

Networks

So guess what:

XForms already has the inherent mechanism for simulating neuron networks.

Although the XForms system uses a feed-forward network, it is possible to simulate a feed back network.

Feed forward

If I have a value n, and another value g that is some guess at the square root of n, then the expression

((n ÷ g) + g) ÷ 2

will give a better approximation of the square root.

I'm not going to prove this, you'll have to accept my word for it; Newton discovered it.

(Non-binary) neuron

So I can create an XForms neuron

<instance>
   <data xmlns="">
      <value>2</value>
      <result/>
   </data>
</instance>

<bind ref="result"
      calculate="((../value div preceding-sibling::*) + preceding-sibling::*) div 2"/>

Feed forward example

Each time you click on the arrow, it adds another neuron to the system, getting you closer to the square root

Source

All the arrow does is add another element to the instance. XForms does the rest:

 <trigger>
    <label>→</label>
    <action ev:event="DOMActivate">
       <insert ref="result"/>
    </action>
 </trigger>

Feedback version

Here the only change is that instead of adding a new element, when the button is clicked, the result is copied back to the approximation.

<trigger>
   <label>→</label>
   <action ev:event="DOMActivate">
      <setvalue ref="approx" value="../result"/>
   </action>
</trigger>

Source

Mechanism

So XForms has in-built the mechanism needed to implement neural networks.

<instance>
   <neuron value="" threshold="" xmlns="">
      <in value="" weight=""/>
      <in value="" weight=""/>
      <in value="" weight=""/>
      <out/>
   </neuron>
</instance>

<bind ref="neuron/in/@value"
      calculate=".. * ../weight"/>
<bind ref="neuron/value"
      calculate="sum(../in/@value)"/>
<bind ref="neuron/out"
      calculate="if(../value &gt; ../threshold, 1, 0)"/>

AI Workbench