Jump to content

  • Log In with Google      Sign In   
  • Create Account

Artificial Neural Networks


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
72 replies to this topic

#21 Emergent   Members   -  Reputation: 971

Like
0Likes
Like

Posted 19 September 2009 - 10:45 AM

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?

;-)

Sponsor:

#22 Daerax   Members   -  Reputation: 1207

Like
0Likes
Like

Posted 19 September 2009 - 11:07 AM

@danmar

No they don't. They cant model intuition, creativity and hunches. Which is the core of human biological thinking. They dont solve equations* nor can they prove theorems.

If as Sneftel suggests that ANNs in games are mostly used as classifiers (and the nonlinear nature of ANNs is not the key) then for most games Bayesian Networks would perform better, especially since game entities are trying to make decisions. With the added benefit that its reasoning is clear and you can go back and easily tune algo, game play etc based on results. kNNs too are probably sufficient (although SVM I feel is also overkill and probably poor since the training dataset probably would not be sufficient to produce best results).

Myself I am looking at ANNs for a problem where their function approximation and ability to capture interdependecies is useful, the blackbox nature of ANNs is ok since the data itself has no inherent meaning and is complex enough that any attempt using splines results in nonsense. I have used regression (as noted a simplest type of ANN) but it has not performed ideally. Of course there is a simper statistical technique I also plan to implement and test against to see which is better.

*An ANN is nothing but a directed graph connecting a bunch of functions with weighted nodes. They are an alchemical and blind way to approximate functions. I suspect I could build a 2 input 1 layer 3 output neural network with biological entities.

Using a mouse. I would have it classify colours using a series of tubes. I would show it a colour and use different sized cheeses and slight to mild shocks :( to correctly set the weights and implicitly, activation functions. Then initial choice of tube will set subsequent choice which chooses output :). It would also be able to classify new colour combos i did not train it weight.

Thus i would have trained the mouse to think like a human.

#23 danmar   Banned   -  Reputation: 100

Like
0Likes
Like

Posted 19 September 2009 - 08:15 PM

Quote:
Original post by Daerax
@danmar

No they don't. They cant model intuition, creativity and hunches. Which is the core of human biological thinking. They dont solve equations* nor can they prove theorems.


I was talking about mechanics of it, the flow of information and the type of computation can be modeled after what is known about biological/chemical information processing of neurons inside the living brain. Many different "computations" can be simulated with the results closely matching biological measurements.

Blue Brain Project
http://bluebrain.epfl.ch/


I do actually agree with you, but I would phrase it differently. I'd say, intuition, creativity and such are indeed the core of human mind, which can not be simulated as it is not really understood, it's not defined properly nor it can be objectively examined or measured.

But intelligence and logic can, which I refer to as "thinking", so I would separate intelligence (thinking) from everything else as it is the only thing we _can actually judge and measure as an external observer - it is because intelligence/logic is deterministic, while everything else is chaotic, if not completely random.


Though, in some hypothetical theory ANN could simulate intuition and creativity too... if it could only spontaneously arise and evolve by itself, just like in the real world. But really, you would need to build and train fully talking AI to be able to ask about it. You can't just put partial artificial or biological network and hope to measure some numerical or voltage output to be identified as "intuition". This can only be done with logic circuits aka intelligence and deterministic algorithms.

Imagine we train some ANN to the point you can have conversation with it, and it tells you it has emotions and intuition, it can dream and it likes music, would you believe it?




Anyway, amazingly I was right about Quake bots, many of them do use neural networks, but the best part is that it's all perfectly documented and all the source code is available. Google "neural network quake bot".


Neural Bot, Quake 2:
http://homepages.paradise.net.nz/nickamy/neuralbot/nb_about.htm

The Quake III Arena Bot:
http://www.kbs.twi.tudelft.nl/docs/MSc/2001/Waveren_Jean-Paul_van/thesis.pdf

[Edited by - danmar on September 20, 2009 2:15:04 AM]

#24 EJH   Members   -  Reputation: 314

Like
0Likes
Like

Posted 20 September 2009 - 01:34 PM

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?

;-)


In the real world you wouldn't use either method for such a trivial problem. Learning XOR is an Intro to AI class exercise for beginners.

Machine learning (via ANNs or otherwise) is applied where you are solving or approximating solutions to problems so complex that hand-coding a solution is either extremely difficult or impossible.

Like every other solution in the problem-solution space mapping, ANNs are good for some things and bad for others. There's no free lunch right? =)

http://www.no-free-lunch.org/

#25 Daerax   Members   -  Reputation: 1207

Like
0Likes
Like

Posted 20 September 2009 - 04:29 PM

@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.

#26 Emergent   Members   -  Reputation: 971

Like
0Likes
Like

Posted 20 September 2009 - 04:55 PM

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.

#27 danmar   Banned   -  Reputation: 100

Like
0Likes
Like

Posted 20 September 2009 - 06:34 PM

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?

#28 Daerax   Members   -  Reputation: 1207

Like
0Likes
Like

Posted 20 September 2009 - 07:11 PM

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?

#29 danmar   Banned   -  Reputation: 100

Like
0Likes
Like

Posted 20 September 2009 - 09:43 PM

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.

#30 Victor-Victor   Banned   -  Reputation: 100

Like
0Likes
Like

Posted 21 September 2009 - 09:46 PM

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.

#31 Victor-Victor   Banned   -  Reputation: 100

Like
0Likes
Like

Posted 26 September 2009 - 09:44 AM

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]

#32 AlabamaCajun   Members   -  Reputation: 124

Like
0Likes
Like

Posted 29 September 2009 - 03:27 AM

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.

#33 Victor-Victor   Banned   -  Reputation: 100

Like
0Likes
Like

Posted 30 September 2009 - 10:06 AM

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]

#34 willh   Members   -  Reputation: 160

Like
0Likes
Like

Posted 01 October 2009 - 04:13 AM

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. :)

#35 Álvaro   Crossbones+   -  Reputation: 13914

Like
0Likes
Like

Posted 01 October 2009 - 04:50 AM

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).



#36 willh   Members   -  Reputation: 160

Like
0Likes
Like

Posted 01 October 2009 - 05:22 AM

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). :)



#37 Victor-Victor   Banned   -  Reputation: 100

Like
0Likes
Like

Posted 01 October 2009 - 03:21 PM

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]

#38 willh   Members   -  Reputation: 160

Like
0Likes
Like

Posted 02 October 2009 - 08:31 AM

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.



#39 willh   Members   -  Reputation: 160

Like
0Likes
Like

Posted 02 October 2009 - 09:02 AM

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. :)





#40 Victor-Victor   Banned   -  Reputation: 100

Like
0Likes
Like

Posted 02 October 2009 - 04:47 PM

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]




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS