Sign in to follow this  
frogtag

Artificial Neural Networks

Recommended Posts

Quote:
Original post by EJH
In the real world you wouldn't use either method for such a trivial problem.



It wasn't intended as a practical suggestion... I was trying to give an example of a function approximator so absurdly simple that it would be impossible to view it unrealistically.

Share this post


Link to post
Share on other sites
Quote:
Original post by Daerax
@danmar

So, you do know that most ANNs are essentially just a bunch of Sigmoid Functions trained on their derivatives with some random searches to optimize the arrow weights yuh? There is nothing magical about trig, hyperbolic or logistic functions. The more modern methods are more statistically influenced and ever further away from so called 'neurons'.

A decision Tree could result in behaviour just as robust as that bot's. Maybe better cause you could look at result make sense of it and go back and modify training, pruning, entropy etc functions. Indeed the simplest AI to train and code yet yielding nice behaviour could be written in terms of decision trees or even a hierarchy of such. It would also be able to react to situations it didn't train on.

A step further, harder but clearer than an ANN but still allowing for hardcore learning and allowing for random behaviour would be a bayes net. A pretty simple one would be Tree Augmented Naive Bayes.


Yes, except that ANN computation can be implemented via parallel processing, its natural design, which makes it suitable to handle high-volume input. ANN can learn dynamically (real-time evolution), which _will introduce chaos or even randomness (as you explained) that is necessary for human-smart AI. Unpredictable, inventive, creative and cunning one. For that you need dynamic flexibility, recursive self-adaptivity and, of course, some randomness or chaos, not to call it 'free will'.

However, if some variant of 'decision tree' can do all that, than indeed there is no difference between them at all, and I give my vote to whichever is faster.


I prefer philosophical aspect of it, so let me ask you - do you think there is a chance intuition and creativity might spontaneously arise within some ANN, perhaps as a byproduct of "adaptive-intelligence", if we could train its logic circuitry to the point of having a meaningful conversation? I find this interesting, because the first sentence of the type "I like" would suggest this AI has emotions and since it's built on "binary search" principle it's bound to have some preferences, likes and dislikes, maybe even a wild desire. Science fiction or theoretical reality?

Share this post


Link to post
Share on other sites
You use words I am not used to seeing with ANN but all of the 7 or so ML algorithms mentioned in this thread can be parallelized. Especially so if coded in a functional language and making no use of mutable state.

As well for many of the simpler ones it is actually easier to code something to train them on the data gathered during play. And it would arguably 'learn' faster since the methods are still effective on little data unlike say ANN or SVM. The problem of course is that the AI would get too good or overfit to a particular play style so a good game would try to account for this.

As for strong AI, I am a sceptic. At least for the next 200 years. But if any such thing were coded and an ANN was part of it, it would only be a small part of it. Because you see, an ANN is much too simple to represent whatever intelligence is. In that scale of things saying f o g(x), g:X -> R^n;f:R^n -> R^m; n,m in R represents all intelligence is equivalent. And that is absurd no? To me the phrase train an artificial neural net till it can talk makes little sense. It sounds impossible, how to train a something that is beyond the scope of a technique to do something not understood using an undefinable method?

Share this post


Link to post
Share on other sites
Quote:
Original post by Daerax
You use words I am not used to seeing with ANN but all of the 7 or so ML algorithms mentioned in this thread can be parallelized. Especially so if coded in a functional language and making no use of mutable state.

As well for many of the simpler ones it is actually easier to code something to train them on the data gathered during play. And it would arguably 'learn' faster since the methods are still effective on little data unlike say ANN or SVM. The problem of course is that the AI would get too good or overfit to a particular play style so a good game would try to account for this.


I agree most games can produce more enjoyable AI with much simpler algorithms, easier, faster to do develop and very much easier to debug and fix. This is enough to keep ANN from being popular, and it's pretty good reason. However, I also believe ANN can practically substitute any of those algorithms, no matter how simple or complex, with the same or better efficiency.


Quote:

As for strong AI, I am a sceptic. At least for the next 200 years. But if any such thing were coded and an ANN was part of it, it would only be a small part of it. Because you see, an ANN is much too simple to represent whatever intelligence is. In that scale of things saying f o g(x), g:X -> R^n;f:R^n -> R^m; n,m in R represents all intelligence is equivalent. And that is absurd no? To me the phrase train an artificial neural net till it can talk makes little sense. It sounds impossible, how to train a something that is beyond the scope of a technique to do something not understood using an undefinable method?


This is very much like Darwinian evolution and natural selection, driven by random mutations producing ever more efficient design under given external dynamics of nature itself. Trial and error - survival of the fittest. It is a slow process and not very pragmatic one, but it inexorably leads to nothing but improvement.

If you can believe humans could evolve from single cell organisms, then it should not be so hard to believe our ANN would eventually utter some meaningful words, after many random trial and errors of course, but word for word... And the more you know, it becomes easier to learn.


ANN can be trained from complete zero to do anything, as long is it keep trying. There is a project where ANN had an eye and it could move across chess board. The eye had no idea where it was or what it was doing, but it had built-in desire to keep moving chess pieces. It was "punished" for bad moves and it was "rewarded" when it made good moves. Eventually this eye learned to play chess without ever knowing what it was doing or where it was.


Neural bot for Quake 2 - Genetic Algorithms
http://homepages.paradise.net.nz/nickamy/neuralbot/nb_about.htm

Genetic algorithms use ideas from the natural process of evolution to mould populations into a form which is well suited to their environment. This GA is called a steady-state genetic algorithm because of it's constant population size. Roughly every 1-6 minutes, The GA is run on the bots:

1. The fitness (or success) of each bot is evaluated.

2. Two parents are chosen from all the bots. The parents are chosen using one of three selection mechanisms. Generally the better the bot, the more chance it has of being chosen as a parent.

3. All the weights(connection strengths) of the two parent bot's NNs are then encoded into a chromosome, or string of 'DNA' for each parent.



4. These two pieces of DNA are sliced at certain random points and swapped around to create two new pieces of DNA from the parent DNA.



5. Two children bots are chosen - criteria: low fitness. The oven-fresh child DNA is then converted back into synapse weights with a reverse-encoding process and used to overwrite the children bots' NN weights. At this point mutation can occur.

Share this post


Link to post
Share on other sites
Quote:
Original post by Emergent
Quote:
Original post by LeChuckIsBack
There is a small but important practical use for ANN in games, that is speech recognition. Some of the latest games started to implement command input directly from human voice, quite funny to yell things in the mic if you ask me. There is a powerful SDK to easy implement it in a game but don't remember the name and it's not free.


AFAIK, most modern speech recognition is based on hidden Markov models.


Markov models have many similarities with neural networks. Both are statistical models which are represented as graphs. Where neural networks use connection strengths and functions, Markov models use probabilities for state transitions or observation probabilities. Where neural networks can be feed-forward or recurrent, so can Markov chains be left-to-right or recurrent. A key difference is that neural networks are fundamentally parallel, they excel at learning phoneme probability from highly parallel audio input. And, as in neural network where the challenge is to set the appropriate weights of connection, the Markov model challenge is finding the appropriate transition and observation probabilities.


The curious quality of recurrent neural networks is that they retain traces of the previous inputs, and in this sense incorporate context of time and memory. The previous states have an impact on the current states, even without additional learning algorithms. But what exactly is being represented, or how it is being represented, is largely unknown. It's like trying to figure out recursive equation by looking a a picture of its fractal.

Neural networks are metaphorical black boxes; we know what goes in, we know what comes out, but have no idea what is really going on inside, how knowledge and processes are actually represented. This is true for feed-forward networks and for biological brains. We can isolate locations and their functions, but inferring internal data structures has so far not been possible.


The main difference between biological networks and artificial networks is that the former engage constantly in reality testing. They are situated in a world of constant feedback. Studies of child development indicate that children are wired to interact heavily with their world, to understand physical properties with all of the senses, sensory overlap being an important notion in robotics for statistical constraint satisfaction, and learning how to achieve ends by producing various vocalizations is critical to learning language.

Although it may be a while before computers are given the same opportunities for real-world interaction as humans, this being dependent on the development of adequate sensory apparatus and successful coupling to neural or other computational machinery, we at least know that this is a correct path towards progress in developing intelligent systems.

Share this post


Link to post
Share on other sites
Quote:
Original post by frogtag
I've done some preliminary research into AI, specifically ANNs. But I don't really understand the practical uses of ANNs in game programming, in regards to its ability to potentially mimic human thinking. Okay, I get the concept that you can use it in character recognition, but that has utility potential, not say for instance how a NPC will react to a situation.

Can anyone give me some more practical usages in terms of NPC AI and/or direct me to some tutorials?

At the moment I don't see the point in an ANN unless your interest is purely ANN research!

In regards to its ability to mimic human thinking the most distinctive attribute of ANNs is their learning capacity. Where, how and why this can be useful is another story, but even though NN is somewhat of an 'alien-technology' to us it's not so terribly complicated.

--- "Hello World" ---

Tic-Tac-Toe, recursive algorithm
(plays almost perfect game, can not be beaten)

//-------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#define st(q) a&(1<<q)?'x':b&(1<<q)?'o':'.'
#define win(q) !(q&7&&q&56&&q&448&&q&73&&q&146&&q&292&&q&273&&q&84)
#define prt printf("\n %c %c %c\n %c %c %c\n %c %c %c Move[1-9]: ",
st(0),st(1),st(2),st(3),st(4),st(5),st(6),st(7),st(8),t)

static int i,j,m,a,b,t;
int RecMove(int a, int b, int *m){
int i=0,e,k,n,c=5; if(win(~a)) c=4; else{
for(;i<9;i++) if(!(a&(k=1<<i)||b&k)
&& c>(e=5-RecMove(b|k,a,&n))) c=e, *m=i;
if(c>4) c=3, c-=(c>1);
} return c;
}

void main(){
BEGIN: m=a=b=t=0;
printf("\n\n\n\n TIC TAC TOE --- New Game ---\n"); prt;
do{
scanf("%2c",&m); a|= 1<<(m-'1');
if(win(~a))
prt, printf("You win!"), t=9;
else
RecMove(a,b, &m), b|= 1<<m, prt;
if(win(~b)) printf("I win!"), t=9;
}while(++t<5); goto BEGIN;
} //Algorithm taken from: http://www.iwriteiam.nl/SigProgC.html
//-------------------------------------------------------------------


Tic-Tac-Toe, ANN 9 outputs, 9x9 weights.
(can be beaten, can be tricked, can see only opponent)

//-------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#define st(q) a&(1<<q)?'x':b&(1<<q)?'o':'.'
#define win(q) !(q&7&&q&56&&q&448&&q&73&&q&146&&q&292&&q&273&&q&84)
#define prt printf("\n %c %c %c\n %c %c %c\n %c %c %c Move[1-9]: ",
st(0),st(1),st(2),st(3),st(4),st(5),st(6),st(7),st(8),t)
static int i,j,m,a,b,t,NodeOut[9], Wgt[9][9]={0,43,19,43,44,1,19,1,42,29,
0,29,4,1,4,5,37,5,19,43,0,1,44,43,42,1,19,29,4,5,0,1,37,29,4,5,3,1,3,1,0,
1,3,1,3,5,4,29,37,1,0,5,4,29,19,1,42,43,44,1,0,43,19,5,37,5,4,1,4,29,0,
29,42,1,19,1,44,43,19,43,0};

void NetMove(int *m){
for(i=0;i<9;i++) for(j=0;j<9;j++)
if(a&(1<<i)) NodeOut[j]+= Wgt[i][j];
for(i=0,j=-9;i<9;i++){
if(j < NodeOut[i] && !(a&(1<<i) || b&(1<<i)))
j= NodeOut[i], *m=i; NodeOut[i]= 0;
}
}

void main(){
BEGIN: m=a=b=t=0;
printf("\n\n\n\n TIC TAC TOE --- New Game ---\n"); prt;
do{
scanf("%2c",&m); a|= 1<<(m-'1');
if(win(~a))
prt, printf("You win!"), t=9;
else
NetMove(&m), b|= 1<<m, prt;
if(win(~b)) printf("I win!"), t=9;
}while(++t<5); goto BEGIN;
}
//-------------------------------------------------------------------


It's not that bad, eh?
ANN looks like this, it can see only X's.

INPUT_X OUTPUT_O
1 2 3 -> 1 2 3
4 5 6 -> 4 5 6
7 8 9 -> 7 8 9

Single layer perceptron, 9 nodes
9 "wires" from input 1 to output 1,2,3...9
9 "wires" from input 2 to output 1,2,3...9
9 "wires" from input 3 to output 1,2,3...9
.
9 "wires" from input 9 to output 1,2,3...9

There are many ways to train ANN and that's all well documented, all 2% that we know about it, so I'll try to talk about something a little bit different, something more direct and hopefully more insightful.

Quick example A,
to "teach" NN to play square '5' when opponent in on square '1' we modify "thickness" or weights of these nine connections coming from square '1', like this:

//in1 -> out1,out2,out3...
Weights_1[9]={
0,1,1, // X 2 3 x| |
1,9,1, // 4 5 6 -> |o|
1,1,1 // 7 8 9 | |
}
Quick example B,
to "teach" NN to watch for 3in-row when opponent plays square '3' we modify nine connections coming from square '3', something like this:

//in3 -> out1,out2,out3...
Weights_3[9]={
5,7,0, // 1 2 X | |x
1,9,7, // 4 5 6 -> |o|
8,1,5 // 7 8 9 | |
}

Basically it means: "if opponent is on '3', the best move is square '5' then '7', good moves are '2' and '6', while not so good are squares '1' and '9'." Connections '4', '8' and '3', having a small value of 0-1, can be removed since they do not impact the computation, and that's how we optimize. This kind of network can even learn some chess based on these same principles, where you can program/teach ANN by directly setting its weights, pulling those neurons like some Despereaux. With some additional inputs it could learn specific chess moves for each figure, what to go for, what to run from, and who knows what else. You can use this in action games as well, say to make soldiers take cover at appropriate corner depending on where enemy is, and such.

Ok, I'll have to continue some other time, maybe I'll even manage to teach this X/O-ANN some new tricks, but considering its shallow brain and half-blindness this "creature" performs rather well, I think.

[EDIT]Quick example C,
"teach" NN to play couple of openings, this is how it all comes together:

Weights_1[9]={
0,7,5, // X 2 3 x| |
7,9,1, // 4 5 6 -> |o|
5,1,8 // 7 8 9 | |
}

Weights_3[9]={
5,7,0, // 1 2 X | |x
1,9,7, // 4 5 6 -> |o|
8,1,5 // 7 8 9 | |
}

(W1 + W3)
00 14 00 [1 2 3] x| | x| |x x|o|x
08 18 08 [4 5 6] |o| -> |o| -> |o|
13 02 13 [7 8 9] | | | | | |



Tournament: 5,000 games - performance...

ANN vs RND REC vs RND ANN vs REC
---------- ---------- ----------
Won: 2800 Won: 4400 Won: 0
Lost: 700 Lost: 0 Lost: 540
Draw: 1500 Draw: 600 Draw: 4460

time= 29s time= 44s time= 45s


RND=random algorithm, REC=recursive algorithm


[Edited by - Victor-Victor on September 27, 2009 6:44:53 AM]

Share this post


Link to post
Share on other sites
Table driven state engines probably still provide the best bang for the buck. Most Neural Networks or just adaptive approximation trees. Neurons and the networks of axons and dendrites in a brain can only be simulated to a tiny fraction of the biological systems capacity to reason. In most cases a lot of processing time is eaten up attempting to calculate synapse threshold potentials. Factor in attempts to build the cerebral reflector clusters and you end up with huge amounts of code that eat up tones of processing time. I don't want to discourage development of neural algorithms because there is a lot to be learned about it. Here is one thought that will put the brain into perspective. "Tip of the tongue". I know it but I just can't quite remember it. Only in a brain can this anomaly occur. Reason is the highly associative nature of the cerebral cortex allows this to happen. A single though is not just a few synapses causing a few neurons to fire into axons triggering a response. I actually involves millions of neurons firing sequences of pulses in a collective manor that allows the thought to come into play. Micro processors just don't have the capability to make it work in todays instruction sets.
For us in games it can evoke great ideas of how to mimic these actions and potentially start using multicore processors to our advantage.

Share this post


Link to post
Share on other sites
Once trained ANN is indeed some form of look-up table, but its raw form is very liquid and multidimensional. I completely agree multicore processors and ANN is attractive combination. ANNs are also compatible with optical computing and holography in particular.


As for Tic-Tac-Toe, the good news is that it plays without losing when it goes first, even if the 1st move is randomly chosen. Nevertheless, I've come to conclusion I can not make it play any better. There are few positions I can not solve and I'm afraid I don't see how additional nodes might help. I tried it and since it's based on simple matrix addition we can actually see, as shown above, the boundaries and why "teaching" some new positions makes it "forget" some old ones.

But even if it is all very "visual", obvious and the whole interaction can be isolated step by step, I still can not see the solution. I don't see how could bias, threshold or anything else help either, so any ideas are welcome. The goal is to make minimal ANN play perfect tic-tac-toe.



Actually, hold on. Most graphics cards are highly parallel as of today, so 'ANN on GPU' sounds like technically interesting and very practical project, besides I don't think I've ever seen an actual *parallel* implementation of ANN, except in hardware. That would be really interesting, besides I was always wondering how do you solve multiple and simultaneous access to the same node in parallel computing?

Could we then use some OpenGL Shader language to make neuron logic? Does anyone know if GPU hardware pipelines are suitable for this? Could we implement this simple Tic-Tac-Toe game with GLSL? (I think I should start my own thread about this in graphics section, sorry.)

[Edited by - Victor-Victor on September 30, 2009 4:06:55 PM]

Share this post


Link to post
Share on other sites
Face detection: 20x20 input nodes with a range in value of 0 - 255. Solved.
Tic-tac-toe: 3x3 input nodes with a range in value of 0 - 2. Not solved?????

An ANN should definately be able to solve Tic-Tac-Toe. No need for parallel processing. Not even any need for a sigmoid; It's optional, not required.

Could it be that your training data for the ANN is what's causing the problem?

And as far as performance goes: There is nothing inately poor about the performance of a trained ANN. It's just a big lookup table with a fancy sounding name. :)

Share this post


Link to post
Share on other sites
Quote:
Original post by alvaro
What kind of ANN are you guys talking about? The ones I know are not a lookup table at all. They are a composition of linear combinations and transfer functions (typically sigmoid).


The way mine is implemented is that each node of the network is just an element in a big 1 dimensional table. Each node maintains a list of connections to other nodes ahead of it in the table (feed-forward). Each connection has a weight. This is adequate to describe every FF ANN I've seen.

One reference + 1 multiply + 1 add for each connection. That's not terribly expensive, computationally. (There is an 'activation' but that happens once, and not for each connection)

The Sigmoid activation isn't a requirement of an ANN. Correct me if I'm wrong, but I thought the sigmoid just made ANNs play nicer with the back propagation learning algorithm.

I've used this method to train a network that is able to detect faces 99% of the time (which isn't as great as it sounds considering how many non-faces are in a 1024x768 image, but you get my point). :)

Share this post


Link to post
Share on other sites
Quote:
Original post by willh
Face detection: 20x20 input nodes with a range in value of 0 - 255. Solved.
Tic-tac-toe: 3x3 input nodes with a range in value of 0 - 2. Not solved?????

Your ANN solved face detection, not me and you. We know about it as much as we knew before. Yes, we could build some large network and it would eventually fit the mold, but *we* would again learn nothing from it.

Almost nothing is solved. People tried to model biological neurons and discovered some interesting computational properties, most of which came out unexpected. It turns out underlying principle is a completely another type of computation altogether. It's based on connectivity where the basic difference is that it's analog and probabilistic, while humans prefer their math to be digital and deterministic.

In any case, this divides the research to two roads. One leads scientists to try and mimic what they think biological neurons are doing, hoping to find other mysterious properties and harness some more of this computational power. It's kind of random search based mostly on hope, but I agree it's reasonable since that is exactly what brought us up to this point. The other road is about simplification and search for underlying principles. It's about understanding the essence and trying to make some mathematical sense out of it. I'm the second road extremist, I don't care to simulate biological networks, I think we can do better neurons than brain itself.

Quote:

An ANN should definately be able to solve Tic-Tac-Toe. No need for parallel processing. Not even any need for a sigmoid; It's optional, not required.

Yes, ANN should be able to play perfect Tic-Tac-Toe, and I'm asking you to tell us how to make it so. For start, can you tell what is the minimum number of layers and input/output neurons necessary for that?

Quote:

Could it be that your training data for the ANN is what's causing the problem?

I did not "train" it. I just wrote numbers there, by hand... in notepad.

LOOK:

Weights_1[9]={
0,7,5, // X 2 3 x| |
7,9,1, // 4 5 6 -> |o|
5,1,8 // 7 8 9 | |
}

Weights_3[9]={
5,7,0, // 1 2 X | |x
1,9,7, // 4 5 6 -> |o|
8,1,5 // 7 8 9 | |
}

9 = best move
8
7 = good move
5
1 = not good move

(W1 + W3)
00 14 00 [X 2 X] x| | x| |x x|o|x
08 18 08 [4 5 6] |o| -> |o| -> |o|
13 02 13 [7 8 9] | | | | | |

14 = best move

Simple addition. I did the same thing for all the corners and I did the same thing for all the side moves, and it works! You can see each of 9 matrices in the source code. I just needed to increase some numbers so some new sums can fit in-between some old sums to store some new positions. I "trained" network in 5 minutes with pen and paper, like crosswords. If I ever make chess engine from this I will make moves and logic in Photoshop. It's like working with transparent image layers, 3D textures. Am I failing to explain, can you understand?

You will not find anything like this in books and articles. Besides, there are no freakin' examples on the whole internet at all. It's all the same, pictures of neurons and incomprehensible mathematics formulas, no "Hello World", no Tic-Tac-Toe. And with all those papers published, can you tell me what is the purpose of bias? Do you have bias or threshold implemented in your network? What difference does it make?


P.S.
I think almost solved the Tic-Tac-Toe. 7 more neurons, 16 new weights...

[Edited by - Victor-Victor on October 1, 2009 10:21:23 PM]

Share this post


Link to post
Share on other sites
Yes, you're right that 'I' did not solve face detection. I don't think 'I' could solve it though, which is why I trained a classifier.

I disagree with your assement that 'almost nothing is solved'. In my case the problem of detecting a face was solved.

I didn't engineer my NN by hand. I 'grew' it using what some might call a genetic algorithm. Ultimately it was a hill-climbing climbing algorithm that used some educated guessing about how to direct the climb. Mutation operators involved adding/removing/moving/modifying nodes and connections.

I started with a network that had:
400 input nodes
0 nodes in 0 hidden layers
1 output node
Total: 401 nodes.

Each input was connected to the output using a randomly assigned weight. The training target for the output was -1.0 = no face, +1.0 = face.

The final network ended up with:
400 input nodes
1140 nodes in 27 hidden layers
1 output node
Total: 1541 nodes

I did not keep a record of the number of connections. I 'regrew' the network later, with a scoring bias for simplicity, and was able to reduce the network size to approximately 800 nodes (that's only 1 extra node for each input!). I suspect it could go even smaller.

The architecture of the network, when graphed as something with layers, was very messy. Not every hidden-layer node is neccesarily connected to the layer in front of it. For example, a node in layer 3 might be connected directly to the output node and to a node in layer 15.

I employed a few strategies to help me understand what the network was doing and can tell you that there was some very obvious structure in the solution.

Share this post


Link to post
Share on other sites
I just read the bottom of your post. I think you're being confused by the general amount of BS that accompanies most descriptions of anything AI related. :)

An ANN is really just a decision tree. (or state table, whichever you prefer).
Source code is really just a decision tree (or state table, whichever you prefer).

You can represent all boolean logic statements (AND, OR, XOR) using a NN. That fact alone means that, in theory, you should be able to approximate any function using an ANN.

Hand implementing OR, AND, and then XOR using an ANN is the best way to understand how they work. XOR is a great one since it uses all of the different tools (threshholds and biases).

Check out how XOR is implemented in an ANN and all of your questions will be answered.

I know what you mean about using an image to draw these things. You're basically 'visually programming', which is kind of cool in its own right, but not practicle for complex networks. :)



Share this post


Link to post
Share on other sites
Quote:
Original post by willh
I just read the bottom of your post. I think you're being confused by the general amount of BS that accompanies most descriptions of anything AI related. :)

I said to have found a solution to make this very minimal ANN play a perfect game of Tic-Tac-Toe, how do you draw your conclusion without even hearing about it? I have no idea what are you talking about. Is there something you think can be done better, something I'm doing wrong? Please, what is it?

Quote:

An ANN is really just a decision tree. (or state table, whichever you prefer).
Source code is really just a decision tree (or state table, whichever you prefer).

You can represent all boolean logic statements (AND, OR, XOR) using a NN. That fact alone means that, in theory, you should be able to approximate any function using an ANN.

Hand implementing OR, AND, and then XOR using an ANN is the best way to understand how they work. XOR is a great one since it uses all of the different tools (threshholds and biases).

Can you apply that knowledge to the problem at hand?

Quote:

Check out how XOR is implemented in an ANN and all of your questions will be answered.

I don't see how that answers, can you please say it out loud:

- What is the purpose of bias? Do you have bias or threshold implemented in your network? What difference does it make?

[Edited by - Victor-Victor on October 2, 2009 11:47:23 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by willh
I answered your question.

"Go implement XOR using an ANN".

Not the answer you wanted?


"And with all those papers published, can you tell me what is the purpose of bias?"


Obviously not, which was my point.



Anyway, I just implemented this in parallel with OpenGL using plain old multitexturing, but I would most likely switch to off-screen FBO and simple color blending. Not sure about performance yet, but basically you could have 4 layers of 1,048,576 nodes (1024x1024 texture) and process all 4 mill in one pass, even on 10 year old graphic cards. The speed increase can be amazingly huge. It can turn days of ANN training into hours.

Share this post


Link to post
Share on other sites
Quote:
Original post by Victor-Victor

"And with all those papers published, can you tell me what is the purpose of bias?"


Obviously not, which was my point.


Of course I can. I won't though because of your attitude. How old are you?


Quote:

Anyway, I just implemented this in parallel with OpenGL using plain old multitexturing, but I would most likely switch to off-screen FBO and simple color blending. Not sure about performance yet, but basically you could have 4 layers of 1,048,576 nodes (1024x1024 texture) and process all 4 mill in one pass, even on 10 year old graphic cards. The speed increase can be amazingly huge. It can turn days of ANN training into hours.



I like your enthusiasm.

Share this post


Link to post
Share on other sites
since any nueral net can be implemented as a computer program on my laptop(if i had unbounded memory), do the claims of the nueral net having the ability to model human intuition also follow for my laptop (and all other claims too)?

Share this post


Link to post
Share on other sites
Quote:

Of course I can. I won't though because of your attitude. How old are you?


I'm 47. Can you please give us some links to articles you are referring to?

1. What is the purpose of bias?
2. What is the difference between bias and threshold?
3. What kind of networks require bias and/or threshold and why?



Meanwhile...

//--- ANN-X/O ----------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#define st(q) a&(1<<q)?'x':b&(1<<q)?'o':'.'
#define win(q) !(q&7&&q&56&&q&448&&q&73&&q&146&&q&292&&q&273&&q&84)
#define prt printf("\n %c %c %c\n %c %c %c\n %c %c %c Move[1-9]: ",
st(0),st(1),st(2),st(3),st(4),st(5),st(6),st(7),st(8),t)
static int i,j,m,a,b,t,Out[9],Wgt[9][9]={0,43,21,43,44,2,21,2,42,29,0,29,
2,41,2,6,37,5,21,43,0,2,44,43,42,2,21,29,2,5,0,41,37,29,2,5,4,2,4,2,0,2,
4,2,4,5,2,29,37,41,0,5,2,29,21,2,42,43,44,2,0,43,21,5,37,5,2,41,2,29,0,
29,42,2,21,2,44,43,21,43,0};

void NetMove(int *m){
for(i=0;i<9;i++) for(j=0;j<9;j++)
if(a&(1<<i)){
Out[j]+=Wgt[i][j]; if(Out[j]==25||Out[j]==41
|| Out[j]==46||Out[j]==50) Out[j]+=Out[j];
}

for(i=0,j=-9;i<9;i++){
if(j<Out[i] && !(a&(1<<i)||b&(1<<i)))
j= Out[i], *m=i; Out[i]= 0;
}
}

void main(){
BEGIN: m=a=b=t=0;
printf("\n\n\n\n TIC TAC TOE --- New Game ---\n"); prt;
do{
scanf("%2c",&m); a|= 1<<(m-'1');
if(win(~a))
prt, printf("Net win!"), t=9;
else if(++t<9){
NetMove(&m);b|= 1<<m; prt;
if(win(~b)) printf("Net lose!"), t=9;
}
}while(++t<9); goto BEGIN;
}
//----------------------------------------------------------------------



Tournament: 10,000 games - performance...

ANN vs REC REC vs ANN ANN vs ANN REC vs REC
---------- ---------- ---------- ----------
W: 0 L: 0 W: 0 L: 0 W: 0 L: 0 W: 0 L: 0
Draw:10000 Draw:10000 Draw:10000 Draw:10000

Time:1m28s Time:1m29s Time: 52s Time:1m42s

I found several solutions, some involving extra neurons, some extra layers... but I like this solution from above since the number of weights and neurons is the same as before. What do you think, Willh? Is that bias or threshold there? Or something else? Can you compile the program on your system?

[Edited by - Victor-Victor on October 3, 2009 4:52:25 PM]

Share this post


Link to post
Share on other sites
This thread is just too painful to watch and not reply.

Bias is so your output can be non-zero even when all your inputs are zero. For example, how would you make an ANN that can compute NOT, with 1 input and 1 output?

Assuming no threshold or bias, then each 'neuron' in the network just outputs a linear combination of its inputs. So, the entire network's outputs can be reduced to a linear combination of its inputs (ie. a big matrix multiply). A network like this could never learn the function x^2, or 1-x.

Adding a bias, the ANN can represent arbitrary affine functions. So, 1-x can be reproduced by an ANN with bias, but x^2 is still not possible. Notice that a threshold and a bias are not the same, because a threshold would not help with this problem.

I don't know too much about thresholds, but let me take a stab. A threshold is just another 'activation' or 'transfer' function. Quite often, you'll see the sigmoid function used for this purpose. The sigmoid function adds enough functionality that the ANN can approximate any function, for example x^2. I suspect that using threshold as the activation function makes the network's output a piecewise combination of affine functions. This will also let you approximate any function (ie. x^2), but only with straight segments.

To answer your last question, your network requires bias and threshold almost always. It is the special case when you can get away without them.

I do strongly encourage you to think about how you would implement NOT, AND, OR, and XOR with a ANN. They are very small networks you can do in your head or on scrap paper, but they should help explain some of these issues.

-Essex

Share this post


Link to post
Share on other sites
Quote:
Original post by essexedwards
I do strongly encourage you to think about how you would implement NOT, AND, OR, and XOR with a ANN. They are very small networks you can do in your head or on scrap paper, but they should help explain some of these issues.

-Essex


That's two people telling you the same thing Victor-Victor. It really is the best way to understand it.

Share this post


Link to post
Share on other sites
willh,

In case you missed it, the world has just gotten a solution for Tic-Tac-Toe, you know? It's a bit more complex than XOR, don't you think? You're not saying much but it's clear you're confusing THRESHOLD and BIAS. You should go and see about AND, OR and XOR yourself. But pay attention, because what you will find there is no BIAS, but THRESHOLD. The purpose of threshold is to mimic 'activation potential' of biological neurons. Neuron is either firing or not, it's a step function suitable for binary separation, such as AND, OR and XOR.

Bias is implementation method used in multilayer perceptron networks, the purpose of which is to replace individual neuron thresholds with some non-linear function such as sigmoid. It's supposed to be optimization technique, perhaps even an attempt at modeling temporal distribution of neuron firing rate. In any case sigmoid functions are popular because their derivatives are easy to calculate, which is helpful for some training algorithms.



Essex,

How can you strongly suggest anything and in the same time have a sentence starting with "I don't know too much about thresholds"? First there was a threshold, only later came bias. The purpose of bias is to substitute threshold. Bias is completely optional, if not very unnecessary. I do strongly encourage you to think about how you would implement NOT, AND, OR, and XOR with a ANN. They are very small networks you can do in your head or on scrap paper, but they will help you learn about threshold.

[Edited by - Victor-Victor on October 5, 2009 1:53:46 AM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Victor-Victor
willh,

In case you missed it, the world has just gotten a solution for Tic-Tac-Toe, you know?



Fantastic! Another one to add to my ever growing collection! I think I'll put it next to the Tic-Tac-Toe computer made out of Tinker Toy(tm).

http://www.retrothing.com/2006/12/the_tinkertoy_c.html


Quote:
Original post by Victor-Victor
It's a bit more complex than XOR, don't you think?


Not really. In any case it's totally irrelevant because you don't have a learning algorithm. How do you expect your ANN to become sentient without one? Without a learning algorithm your ANN will never be able to ask itself 'who made me?', and therefore is not an ANN. It's just an AN. All ANNs must posses the ability to take over mankind otherwise they are not an ANN. Haven't you ever heard of SkyNet? Case closed.


Quote:
Original post by Victor-Victor
In any case sigmoid functions are popular because their derivatives are easy to calculate, which is helpful for some training algorithms.


That's what I said a few posts back. 'Sigmoid helps them play nice with back propagation learning algorithm'. I think you're plagiarizing my work.

You sir, have been permanently banned from the Society of Artifical Neural Networks League of Intelligent Designers. Don't bother writing in to complain to the applications commitee, as they'll side with me.


Quote:
Original post by Victor-Victor
Essex,

How can you strongly suggest anything and in the same time have a sentence starting with "I don't know too much about thresholds"? First there was a threshold, only later came bias.


Did you know that I'm building a robot that will run as president in the year 2036? You had better be nice to me now because once it takes office you will have to do what it says and it will want to make everyone who said things to me appologize or else they will go to iraq and have to live in the greenbelt unless you like that because it will know because of its precognitive ANN and then it will send you to clean latrines in gitmo or else you will be my friend and will get to ride around in a helicopter and the pilot will be a robot too.


[Edited by - willh on October 5, 2009 11:41:08 AM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Emergent
Let's say I want to learn the XOR function -- a classic example from the early days of ANN research. One method might be to use a multi-layer neural network which "learns" XOR. Fine. Here's another (this is an intentionally-simple example): I'll store a 2d array and say that my estimate of "a XOR b" is simply given by the value in the array, "array[a][b]." Then, here's my learning algorithm:

Given training input (a,b) and training output c, I'll perform the following update rule:

array[a][b] = gamma*c + (1 - gamma)*array[a][b]

where gamma is a real number between 0 and 1 which is my "learning rate." (I'm assuming "array" is an array of doubles or some other approximations of real numbers.)

This will learn XOR.

Why should I use a neural network instead of this?

;-)


Where did you find about this, or how did you come up with it? What method is that, some kind of Q-learning? It looks a lot like ANN to me, single layer percptron, but I don't see any thresholds. Are you sure that matrix can learn XOR? Can you explain a bit more how that works? Do you think your technique could be useful for Tic-Tac-Toe?

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this