Sign in to follow this  
frogtag

Artificial Neural Networks

Recommended Posts

essexedwards    100
Victor-Victor:

We seem to be discussing these options:
1. Include Bias Input.
2. Use step (heaviside) activation function.
3. Give each neuron a different 'threshold' for the step.

I was confused by what you meant by 'threshold'. I thought you just meant using a step function as the activation function (ie. 2). I now think you meant giving each neuron a different value where the step occurs (ie. 2+3). I agree that that is completely the same as using a bias and having every threshold step at zero (ie. 1+2 = 2+3). However, it is definitely not the same as having no threshold activation function at all (which is what I thought you were asking).

As an argument for why the standard sigmoid might be useful (besides derivatives), consider making a network with 2 inputs (x,y) that outputs 1 when x^2+y^2<1 and 0 otherwise. Using threshold activation functions will have to approximate this circle as a polygon. Using sigmoid will actually be able to have a curved boundary following part of the circle. Either will work, of course, but I would be surprised if sigmoid didn't get more accuracy with fewer neurons. (I've ignored how to map the sigmoid network's real output to boolean. Let's just say we switch at 0.5).

Share this post


Link to post
Share on other sites
Emergent    982
Quote:
Original post by Victor-Victor
Quote:
Original post by Emergent
Let's say I want to learn the XOR function [...]

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?


I just made it up, and it wasn't really intended to be a practical suggestion. It was just supposed to be an example of a dead-simple "learning algorithm" which would be very transparent in its operation.

And I wouldn't recommend it (or any learning algorithm, even "real ones," for that matter) for Tic Tac Toe, as that can be solved instantly using even a naive implementation of the minimax algorithm without alpha-beta pruning.

Anyway, what I suggested is just a table of numbers. For every input to your function, you have a table entry giving its output. Very simple.

Just suppose what you would do yourself if you found a "black box" that took two binary inputs and produced one output, and you wanted to know what it did: You'd just try the various combinations of 0 and 1 on the inputs and write down what the outputs you got were. If you're organized, you'd probably write them down in a table in your notebook.

What I described is almost exactly this -- except instead of just writing down 0 or 1, I allow numbers in-between which I nudge up every time I get a 1 for that particular input pair and nudge down every time I get a zero for that pair.

I didn't mention anything about thresholding, but I suppose you'd just want to threshold here at 0.5.

Still, let me emphasize that this was meant really just as a toy example of a very simple algorithm.

Share this post


Link to post
Share on other sites
Victor-Victor    100
I don't understand what do you mean by "toy example" and "not practical suggestion". Is it true or not? ANN research was stuck frozen for 30 years just because everyone assumed ANN can't do XOR. If your "matrix", or whatever you call it, and your learning method can learn XOR then of course it is practical. Not only that, it's pretty important too as there is nothing like it on the whole internet. So please, are you sure it can learn XOR? Can you demonstrate the procedure?

Share this post


Link to post
Share on other sites
willh    160
Quote:
Original post by Victor-Victor
I don't understand what do you mean by "toy example" and "not practical suggestion".

Toy example: tic-tac-toe is so simple for a REAL ANN that it's like a toy. Real AI's play Global Thermal Nuclear War, just like Josuha.

Quote:

Is it true or not?

Yes

Quote:

ANN research was stuck frozen for 30 years just because everyone assumed ANN can't do XOR. If your "matrix", or whatever you call it, and your learning method can learn XOR then of course it is practical. Not only that, it's pretty important too as there is nothing like it on the whole internet.

It wasn't stuck at all. It was moved underground once they became so advanced that we couldn't control them anymore. All of the knowledge and algorithms were entrusted to the Society of Artifical Neural Networks League of Intelligent Designers. Yes, I am a member and No, you cannot join.

They are too powerful for the general public. Haven't you heard about the W.O.P.R incident? Needless to say, the only winning strategy is not to play at all.

Quote:

So please, are you sure it can learn XOR? Can you demonstrate the procedure?

You're asking the wrong questions Victor-Victor. It's not about what they can learn rather its about what they CANT learn! Can you teach an ANN to LOVE? Can you hug somebody with Nuclear Arms?

Just ask Tom Clancy..
http://home.comcast.net/~tjclancy/McCullochPittsXORFunc.png

[Edited by - willh on October 5, 2009 8:07:11 PM]

Share this post


Link to post
Share on other sites
Emergent    982
@willh: Having fun? ;-)


@Victor-Victor:

Yes, it can "learn XOR." It can "learn" any function of two boolean variables. But I hesitate to use the word "learn" since it ascribes somehow magical powers of cognition to what's actually a trivial idea.

The thing that makes what I described impractical is that (1) it requires an array with an entry for every possible input combination (so memory use is exponential in the number of inputs), and (2) it makes no attempt to "learn" the values of outputs for inputs it has never seen, so (3) it would for larger problems require a very large amount of training data and memory.

But it's actually not a horrible conceptual starting point.

Example? Ok. Here's I'll "learn" XOR. I'll initialize the table to 0.5, and use a "learning rate" of gamma=0.5.

Initial table:
0.5000 0.5000
0.5000 0.5000

"Training" table...
--- Iteration 1 -------
Input = (0, 1) Output = 1
New table:
0.5000 0.7500
0.5000 0.5000

--- Iteration 2 -------
Input = (1, 1) Output = 0
New table:
0.5000 0.7500
0.5000 0.2500

--- Iteration 3 -------
Input = (0, 0) Output = 0
New table:
0.2500 0.7500
0.5000 0.2500

--- Iteration 4 -------
Input = (0, 1) Output = 1
New table:
0.2500 0.8750
0.5000 0.2500

--- Iteration 5 -------
Input = (0, 1) Output = 1
New table:
0.2500 0.9375
0.5000 0.2500

--- Iteration 6 -------
Input = (0, 1) Output = 1
New table:
0.2500 0.9688
0.5000 0.2500

--- Iteration 7 -------
Input = (0, 1) Output = 1
New table:
0.2500 0.9844
0.5000 0.2500

--- Iteration 8 -------
Input = (1, 1) Output = 0
New table:
0.2500 0.9844
0.5000 0.1250

--- Iteration 9 -------
Input = (1, 0) Output = 1
New table:
0.2500 0.9844
0.7500 0.1250

--- Iteration 10 -------
Input = (1, 0) Output = 1
New table:
0.2500 0.9844
0.8750 0.1250

--- Iteration 11 -------
Input = (0, 1) Output = 1
New table:
0.2500 0.9922
0.8750 0.1250

--- Iteration 12 -------
Input = (1, 0) Output = 1
New table:
0.2500 0.9922
0.9375 0.1250

--- Iteration 13 -------
Input = (1, 1) Output = 0
New table:
0.2500 0.9922
0.9375 0.0625

--- Iteration 14 -------
Input = (1, 1) Output = 0
New table:
0.2500 0.9922
0.9375 0.0312

--- Iteration 15 -------
Input = (1, 1) Output = 0
New table:
0.2500 0.9922
0.9375 0.0156

-- Done ----
Learned (thresholded) values:
0 1
1 0


This was done using the following quick little script (MATLAB code... should be readable by anyone who knows C. The only unusual thing is that arrays start at 1 rather than 0).

gamma = 0.5;  % Set "Learning rate"

v = 0.5*ones(2,2); % Initialize table

fprintf(1, 'Initial table:\n');
disp(v);

% "Train" table
fprintf(1, '"Training" table...\n');
for k=1:15

fprintf(1, '--- Iteration %g -------\n', k);

% Get a random input/output pair
a = (rand(1) > 0.5);
b = (rand(1) > 0.5);
f = (a | b) & ~(a & b);

% Update table
v(a+1,b+1) = (1 - gamma)*v(a+1,b+1) + gamma*f;

fprintf(1, 'Input = (%g, %g) Output = %g\nNew table:\n', a, b, f);
disp(v);
end

% Threshold the result
v_t = (v > 0.5);
fprintf(1, '-- Done ----\nLearned (thresholded) values:\n');
disp(v_t);


Ok?

Share this post


Link to post
Share on other sites
Victor-Victor    100
You took learning technique from ANNs, you have weights and you have thresholds, and you ask: "Why should I use a neural network instead of this (toy example)?" - I take it you're joking.

f = (a | b) & ~(a & b); What are you trying to model, ZX Spectrum? Your function is more complex than XOR, why not: f = a^b? Anyway, Can you provide one of those minimax algorithms for Tic-Tac-Toe that gives instant solutions? Do you think any of them can beat my ANN-X/O in memory usage or speed?



Tic-Tac-Toe, PARALLEL IMPLEMENTATION

//--- OpenGL ANN-X/O ----------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <GL\GLee.h>
#include <GL\glut.h>
#pragma comment(lib, "glee.lib")
#define win(q) !(q&7&&q&56&&q&448&&q&73&&q&146&&q&292&&q&273&&q&84)
GLuint In[9]; static int sw,sh,i,j,k,a,b,t=9,m=99,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};
char say[100]; GLubyte Board[16];

void NetMove(int *m){
glEnable(GL_BLEND);
glEnable(GL_TEXTURE_2D);
for(i=0;i<9;i++) if(a&(1<<i)){
glBindTexture(GL_TEXTURE_2D, In[i]);
glBegin(GL_QUADS);
glTexCoord2f(0,1); glVertex2f(0, 0);
glTexCoord2f(1,1); glVertex2f(4, 0 );
glTexCoord2f(1,0); glVertex2f(4, 4);
glTexCoord2f(0,0); glVertex2f(0, 4);
glEnd();
}
glReadPixels(0,sh-4, 4, 4,
GL_RED, GL_UNSIGNED_BYTE, Board);
for(i=0,j=0; i<9; i++){
if(i%3==0) j++; Out[i]= Board[i+j];
if(Out[i]==25||Out[i]==41
|| Out[i]==46||Out[i]==50)Out[i]+=Out[i];
}
for(i=0,j=-9;i<9;i++) if(j<Out[i]
&& !(a&(1<<i)||b&(1<<i))) j= Out[i], *m=i;
glDisable(GL_TEXTURE_2D);
glDisable(GL_BLEND);
}

static void TxtOut(int x, int y, char *str){
int n, len= (int)strlen(str);
glRasterPos2f(x,y); for(n=0; n<len; n++)
glutBitmapCharacter(GLUT_BITMAP_9_BY_15, str[n]);
}

static void display(){
glClear(GL_COLOR_BUFFER_BIT);
TxtOut(10,30,"TIC - TAC - TOE");
if(m<99 && t<9){
a|= 1<<m; t++; if(t++<9)
NetMove(&m), b|= 1<<m; m=99;
}else if(t>=9 || win(~a) || win(~b)){
if(win(~a)) TxtOut(120,100,"You win!");
else if(win(~b)) TxtOut(120,100,"You lose!");
else TxtOut(120,100,"Draw..."); t= 99;
}
for(i=0,j=0,k=0; i<9; i++){
k++; if(i%3==0) j++, k=0;
if(a&(1<<i)) TxtOut(30+k*20, 50+j*20, "x");
else if(b&(1<<i)) TxtOut(30+k*20, 50+j*20, "o");
else TxtOut(30+k*20, 50+j*20, ".");
TxtOut(20,150, "Move[1-9]");
} glutSwapBuffers();
}

void init(int w, int h){
glViewport(0,0,sw=w,sh=h);
glMatrixMode(GL_PROJECTION);
glLoadIdentity(); glOrtho(0,w,h, 0,0,1);
glMatrixMode(GL_MODELVIEW); glLoadIdentity();
glDisable(GL_DEPTH_TEST); glClearColor(0,0,0, 0);
glEnable(GL_COLOR_MATERIAL); glShadeModel(GL_FLAT);
glBlendFunc(GL_ONE, GL_ONE); glBlendEquation(GL_FUNC_ADD);
for(t=0;t<9;t++){ for(i=0,j=0; i < 9; i++){
if(i%3==0) j++; Board[i+j]= Wgt[t][i];}
glGenTextures(1,&In[t]); glBindTexture(GL_TEXTURE_2D,In[t]);
glTexParameteri(GL_TEXTURE_2D,GL_TEXTURE_MAG_FILTER, GL_NEAREST);
glTexParameteri(GL_TEXTURE_2D,GL_TEXTURE_MIN_FILTER, GL_NEAREST);
glTexImage2D(GL_TEXTURE_2D,0,1, 4, 4,0, GL_RED,GL_UNSIGNED_BYTE, Board);
}
}

void kbd_loop(unsigned char key, int x, int y){
switch(key){
case 27: exit(0); break;
} m=key-'1'; if(m<0||m>8||(t<9
&& (a&(1<<m)||b&(1<<m)))) m=99;
else if(t>=9 && m<99) a=b=t= 0;
display(); glutPostRedisplay();
}

void main(){
glutInitDisplayMode(GLUT_DOUBLE);
glutInitWindowSize(320, 200);
glutCreateWindow("X/O-ANN");
glutKeyboardFunc(kbd_loop);
glutDisplayFunc(display);
glutReshapeFunc(init);
glutMainLoop();
}
//-----------------------------------------------------------------------

Share this post


Link to post
Share on other sites
Emergent    982
Quote:
Original post by Victor-Victor
f = (a | b) & ~(a & b); What are you trying to model, ZX Spectrum? Your function is more complex than XOR, why not: f = a^b?


This is XOR! :-) MATLAB, the language I used, does have a "xor" function, but I had forgotten about it when I whipped this up so I just wrote the above, which means "f = (a OR b) AND NOT(a AND b);" hopefully you can see that this is precisely equivalent.

Quote:
I take it you're joking.


In the post where I first introduced the method we're discussing now, I was... 75% joking? I was being snarky. And I feel like now half the problem is that I must have come across as more serious than I actually was.

But ok; if I was 75% joking, then I was also 25% serious. So in what way was I serious?

Well, although as I've stated above there are a number of things which make just storing a big table impractical for large problems, for small problems there's really nothing wrong with it. And representing a function as a table is the simplest possible example of representing a function as a sum of basis functions; here the bases are just the Kronecker delta functions. So it gives a nice segue into some slightly more sophisticated (albeit still quite simple) methods based on basis expansions (which generalize better and are more applicable to higher-dimensional problems), and this is what I'd hoped my post would hint at.

Quote:
You took learning technique from ANNs, you have weights and you have thresholds, and you ask: "Why should I use a neural network instead of this (toy example)?"


It's true that if you insist you can think of my example as a special case of fancier learning algorithms. For instance, a variety of Q-learning reduces to this for a one-step plan with only terminal cost (but then you've really eliminated the whole reason to use Q-learning, which is that it exploits Bellman's optimality principle). But I don't think this point of view is particularly productive.

What I described is also a little close to a Kohenen map, but not exactly. Kohenen maps are sometimes described as neural networks, though again I do not think this is a particularly useful way to think about them because they bear little resemblance to the sigmoid-of-weighted-sum type networks that people usually mean when they say "ANN."

The "learning" technique I described is just a first-order lowpass filter... Similar ideas are used in a billion different places.
-
Quote:

Anyway, Can you provide one of those minimax algorithms for Tic-Tac-Toe that gives instant solutions? Do you think any of them can beat my ANN-X/O in memory usage or speed?


Here I want to point you to a particular Java applet I once saw, but I can't seem to find it, so for now I'll point you to the Wikipedia article. I also have some (embarrassingly messy) source code for minimax Tic Tac Toe kicking around; I'll need to get to my laptop before I can post it. It will beat a large ANN in terms of memory usage or gameplay (it plays perfectly), but probably not in execution time (though this is still small).

Share this post


Link to post
Share on other sites
Victor-Victor    100
Quote:
Original post by Emergent
Quote:
Original post by Victor-Victor
f = (a | b) & ~(a & b); What are you trying to model, ZX Spectrum? Your function is more complex than XOR, why not: f = a^b?


This is XOR! :-) MATLAB, the language I used, does have a "xor" function, but I had forgotten about it when I whipped this up so I just wrote the above, which means "f = (a OR b) AND NOT(a AND b);" hopefully you can see that this is precisely equivalent.


What in the world? Are you making fun of it yourself? It's not supposed to be equivalent! That makes it very ridiculous, especially if you're making it more complex. Your function is static - it does not learn - it does not change at all, it's a XOR before and after. Not just your function, your complete program can be substitute with this: f= a^b.

10 input a,b
20 f= a^b
30 goto 10


Quote:

Well, although as I've stated above there are a number of things which make just storing a big table impractical for large problems, for small problems there's really nothing wrong with it. And representing a function as a table is the simplest possible example of representing a function as a sum of basis functions; here the bases are just the Kronecker delta functions.


You are talking about tables, but your example has nothing to do with tables or learning. You change some 'tables values', but you do not use any of that information later for anything, your function is static, it does not learn.


Quote:

So it gives a nice segue into some slightly more sophisticated (albeit still quite simple) methods based on basis expansions (which generalize better and are more applicable to higher-dimensional problems), and this is what I'd hoped my post would hint at.


Your attitude is to avoid ANN and use something else, so when you talk about "simple" learning methods, what are you talking about, ANNs or what?


Quote:

It's true that if you insist you can think of my example as a special case of fancier learning algorithms.


Your function is static, there is no learning there. You should not portray your fantasies as if it was something established and documented. First you should be asking questions to make sure your ideas make sense to start with. Can you provide some links about the subject you are trying to talk about? Is this supposed to be related to ANN or something else?


Quote:

For instance, a variety of Q-learning reduces to this for a one-step plan with only terminal cost (but then you've really eliminated the whole reason to use Q-learning, which is that it exploits Bellman's optimality principle). But I don't think this point of view is particularly productive.

What I described is also a little close to a Kohenen map, but not exactly. Kohenen maps are sometimes described as neural networks, though again I do not think this is a particularly useful way to think about them because they bear little resemblance to the sigmoid-of-weighted-sum type networks that people usually mean when they say "ANN."

The "learning" technique I described is just a first-order lowpass filter... Similar ideas are used in a billion different places.


No, it's not learning technique. It's a static implementation of XOR function, only made to be less efficient and to do some irrelevant stuff too. Being static it is nothing like Kohonen map. It's not sigmoid function that defines ANN, but computation based on connectivity.


Nothing is simple here, nothing is used in billion places. Some of the techniques are only couple of years old. We do not know about internal data structures of neural networks, and that makes it all very non-simple. People were being unable to figure out what you call is "simple" XOR for 30 years, that more than enough proves the point. Do not assume, do not pretend to know, that way you will never learn.

Share this post


Link to post
Share on other sites
willh    160
Victor-Victor: your Neural Network is nothing more than a static implementation of this:


private int MakePerfectTicTacToeMoveWithoutNeuralNetwork ( int[][] board, int toPlay)
{
int moveNum = 0;

// What time is it?
for ( int x = 0; x < 3; x++)
{
for ( int y = 0; y < 3; y++)
{
if (board[x][y] != 0)
moveNum++;
}
}

// On first move, always take the center square //
if ( moveNum == 0)
return 4;

// On second move, take the center if possible, otherwise take a corner //
if ( moveNum == 1)
{
if ( board[1][1] == 0)
return 4;
else
return 0;
}

// Third move, always take a corner
if ( moveNum == 2)
{
if ( board[0][0] == 0)
return 0;
else if ( board[2][0] == 0)
return 2;
else if ( board[0][2] == 0)
return 6;
return 8;
}

// All other moves //
// First take the move that wins //
int moveIndex = 0;
for ( int y = 0; y < 3; y++)
{
for ( int x = 0; x < 3; x++)
{
if ( board[x][y] == 0)
{
// Check horizontal //
if ( x == 0)
{
if ( board[x+1][y] == toPlay && board[x+2][y] == toPlay)
return moveIndex;
}
else if ( x == 1)
{
if ( board[x-1][y] == toPlay && board[x+1][y] == toPlay)
return moveIndex;
}
else
{
if ( board[x-2][y] == toPlay && board[x-1][y] == toPlay)
return moveIndex;
}

// Check vertical //
if ( y == 0)
{
if ( board[x][y + 1] == toPlay && board[x][y + 2] == toPlay)
return moveIndex;
}
else if ( y == 1)
{
if ( board[x][y - 1] == toPlay && board[x][y + 1] == toPlay)
return moveIndex;
}
else
{
if ( board[x][y - 2] == toPlay && board[x][y - 1] == toPlay)
return moveIndex;
}

// Check diagonal //
if ( x == 0 && y == 0)
{
if ( board[1][1] == toPlay && board[2][2] == toPlay)
return moveIndex;
}
else if ( x == 2 && y == 0)
{
if ( board[1][1] == toPlay && board[0][2] == toPlay)
return moveIndex;
}
else if ( x == 0 && y == 2)
{
if ( board[1][1] == toPlay && board[2][0] == toPlay)
return moveIndex;
}
else if ( x == 2 && y == 2)
{
if ( board[1][1] == toPlay && board[0][0] == toPlay)
return moveIndex;
}
}

moveIndex++;
}
}

// Make a move that avoids losing //
if ( toPlay == 1)
toPlay = 2;
else
toPlay = 1;

moveIndex = 0;
for ( int y = 0; y < 3; y++)
{
for ( int x = 0; x < 3; x++)
{
if ( board[x][y] == 0)
{
// Check horizontal //
if ( x == 0)
{
if ( board[x+1][y] == toPlay && board[x+2][y] == toPlay)
return moveIndex;
}
else if ( x == 1)
{
if ( board[x-1][y] == toPlay && board[x+1][y] == toPlay)
return moveIndex;
}
else
{
if ( board[x-2][y] == toPlay && board[x-1][y] == toPlay)
return moveIndex;
}

// Check vertical //
if ( y == 0)
{
if ( board[x][y + 1] == toPlay && board[x][y + 2] == toPlay)
return moveIndex;
}
else if ( y == 1)
{
if ( board[x][y - 1] == toPlay && board[x][y + 1] == toPlay)
return moveIndex;
}
else
{
if ( board[x][y - 2] == toPlay && board[x][y - 1] == toPlay)
return moveIndex;
}

// Check diagonal //
if ( x == 0 && y == 0)
{
if ( board[1][1] == toPlay && board[2][2] == toPlay)
return moveIndex;
}
else if ( x == 2 && y == 0)
{
if ( board[1][1] == toPlay && board[0][2] == toPlay)
return moveIndex;
}
else if ( x == 0 && y == 2)
{
if ( board[1][1] == toPlay && board[2][0] == toPlay)
return moveIndex;
}
else if ( x == 2 && y == 2)
{
if ( board[1][1] == toPlay && board[0][0] == toPlay)
return moveIndex;
}
}

moveIndex++;
}
}

// Otherwise just take the next possible move //
if ( board[0][0] == 0)
return 0;

if ( board[2][0] == 0)
return 2;

if ( board[0][2] == 0)
return 6;

if ( board[2][2] == 0)
return 8;
moveIndex = 0;
for ( int x = 0; x < 3; x++)
{
for ( int y = 0; y < 3; y++)
{
if ( board[x][y] == 0)
return moveIndex;

moveIndex++;
}
}

return -1;
}


Ha! The student becomes the master!

But now prepare yourself for a shocking revelation. Are you sitting? You should sit because I am going to reveal one of the many secrets that are locked within the walls of the Society of Artificial Neural Networks League of Intelligent Designers.

The code you see above, including the comments, was written entirely by a NEURAL NETWORK named Joshua. Using the W.O.P.R Joshua only needed 10 minutes to write out this masterpiece of engineering. A highley secret learning algorithm invented for the Pentagon was able to decipher the codes without ever learning "Hello World" or XOR.

Are you still concious or did the great truth in front of your eyes cause you to faint? Do you now realize why no one wants to tell you the secret of the XOR learning algorithn?

On to the comparison. Your code only looks good. It was written by man, and no man can compare to the tremendous power of an ARTIFICAL NEURAL NETWORK. I asked one of the Neural Networks here in my lab to tell me what it thought of your code. HAL-9000, the ANN, said this:

Drowned cow on shoreline
Is like Victor-Victors code
they both move as fast


Confusing perhaps, but writting in Haikus is an unavoidable consequence of what happens when an Artificial Neural Network becomes a master of Natural Language Processing.

What have you to say now Victor-Victor?

Share this post


Link to post
Share on other sites
Victor-Victor    100
Quote:
Original post by Emergent
Here I want to point you to a particular Java applet I once saw, but I can't seem to find it, so for now I'll point you to the Wikipedia article. I also have some (embarrassingly messy) source code for minimax Tic Tac Toe kicking around; I'll need to get to my laptop before I can post it. It will beat a large ANN in terms of memory usage or gameplay (it plays perfectly), but probably not in execution time (though this is still small).


How about this one I already posted here as "recursive":

#define f(X,g,p,N,M)M{return X?a&b?a&b&1<<i&&m(b,a^1<<i,9)>8?i:M:0:9;}main(){
int a=511,b=a,i=4;for(;X;b^=1<<N)a^=1<<g-'1',g,p(N+'1'),p('\n');} /* 123 */
f(i--&&b&7&&b&56&&b&448&&b&73&&b&146&&b&292&&b /* John Rickard */ /* 456 */
&273&&b&84,getchar(),putchar,m(b,a,9),m(a,b,i)) /* xxx@xxxx.xx.xx */ /* 789 */

This program does never lose, but sometimes fails to win, when it could have won. ANN-X/O makes the same mistakes as it is not aware of its own moves, however neural network version is about two times faster, as you can measure yourself.


But how about this one:

a(X){/*/X=- a(X){/*/X=-
-1;F;X=- -1;F;X=-
-1;F;}/*/ -1;F;}/*/
char*z[]={"char*z[]={","a(X){/*/X=-","-1;F;X=-","-1;F;}/*/","9999999999 :-| ",
"int q,i,j,k,X,O=0,H;S(x)int*x;{X+=X;O+=O;*x+1?*x+2||X++:O++;*x=1;}L(n){for(*",
"z[i=1]=n+97;i<4;i++)M(256),s(i),M(128),s(i),M(64),N;X*=8;O*=8;}s(R){char*r=z",
"[R];for(q&&Q;*r;)P(*r++);q&&(Q,P(44));}M(m){P(9);i-2||P(X&m?88:O&m?48:32);P(",
"9);}y(A){for(j=8;j;)~A&w[--j]||(q=0);}e(W,Z){for(i-=i*q;i<9&&q;)y(W|(1<<i++&",
"~Z));}R(){for(k=J[*J-48]-40;k;)e(w[k--],X|O);}main(u,v)char**v;{a(q=1);b(1);",
"c(1);*J=--u?O?*J:*v[1]:53;X|=u<<57-*v[u];y(X);K=40+q;q?e(O,X),q&&(K='|'),e(X",
",O),R(),O|=1<<--i:J[*J-48+(X=O=0)]--;L(q=0);for(s(i=0);q=i<12;)s(i++),i>4&&N",
";s(q=12);P(48);P('}');P(59);N;q=0;L(1);for(i=5;i<13;)s(i++),N;L(2);}",0};
b(X){/*/X=- b(X){/*/X=-
-1;F;X=- -1;F;X=-
-1;F;}/*/ -1;F;}/*/
int q,i,j,k,X,O=0,H;S(x)int*x;{X+=X;O+=O;*x+1?*x+2||X++:O++;*x=1;}L(n){for(*
z[i=1]=n+97;i<4;i++)M(256),s(i),M(128),s(i),M(64),N;X*=8;O*=8;}s(R){char*r=z
[R];for(q&&Q;*r;)P(*r++);q&&(Q,P(44));}M(m){P(9);i-2||P(X&m?88:O&m?48:32);P(
9);}y(A){for(j=8;j;)~A&w[--j]||(q=0);}e(W,Z){for(i-=i*q;i<9&&q;)y(W|(1<<i++&
~Z));}R(){for(k=J[*J-48]-40;k;)e(w[k--],X|O);}main(u,v)char**v;{a(q=1);b(1);
c(1);*J=--u?O?*J:*v[1]:53;X|=u<<57-*v[u];y(X);K=40+q;q?e(O,X),q&&(K='|'),e(X
,O),R(),O|=1<<--i:J[*J-48+(X=O=0)]--;L(q=0);for(s(i=0);q=i<12;)s(i++),i>4&&N
;s(q=12);P(48);P('}');P(59);N;q=0;L(1);for(i=5;i<13;)s(i++),N;L(2);}
c(X){/*/X=- c(X){/*/X=-
-1;F;X=- -1;F;X=-
-1;F;}/*/ -1;F;}/*/


This thing plays tic-tac-toe on itself.
Moves are carried out within the source code.

If that wasn't enough, this thing gets better over time.

As it plays, it produces improved copies of its own source code!


If you want a program that never loses, replace the string "9999999999 :-|" with "9883857753 :-|", which is something like its DNA. http://www.cs.utsa.edu/~wagner/obfusc/ttt.html



Willh,

Bravo. That is like a square wheel. You will be the master once your code is simpler, smaller, faster or more efficient. But right now it's worse in every aspect, though I like your enthusiasm. Keep trying, I'm looking forward to see your improvement.

My neural network is nothing like that static implementation. They can produce same results, but if you do not see the difference then just pay attention to which one is faster. Faster means better, smaller and simpler means better too, as long as the result is the same. It's called efficiency.

[Edited by - Victor-Victor on October 6, 2009 7:36:33 PM]

Share this post


Link to post
Share on other sites
Emergent    982
Quote:
Original post by Victor-Victor
What in the world? Are you making fun of it yourself? It's not supposed to be equivalent! That makes it very ridiculous, especially if you're making it more complex. Your function is static - it does not learn - it does not change at all, it's a XOR before and after. Not just your function, your complete program can be substitute with this: f= a^b.

10 input a,b
20 f= a^b
30 goto 10

You are talking about tables, but your example has nothing to do with tables or learning. You change some 'tables values', but you do not use any of that information later for anything, your function is static, it does not learn.


The table starts out full of arbitrary numbers (0.5 in this case). Then the table is "trained" by being shown a number of examples. To generate the examples, yes, I compute XOR: So will any xor-learning ANN demo; your training data has to come from somewhere. After this training phase, the table contains values which approximate the correct ones. Thresholding at the end snaps these values to zero or one. The last few lines of the program output what has been "learned" by the table.

I could have replaced that line,

f = (a | b) & ~(a & b);


with

f = [Any other boolean function of a and b]


and the table would have "learned" whatever that function was.

Share this post


Link to post
Share on other sites
willh    160
Quote:
Original post by Victor-Victor
My neural network is nothing like than static implementation. They can produce same results, but if you do not see the difference then just pay attention to which one is faster. Faster means better, smaller and simpler means better too, as long as the result is the same. It's called efficiency.


Wrong, wrong, and wrong. I see a trend here that even a 0-ply ANN could learn in 1 iteration. Joshuas code is in fact much smaller, faster and simpler (all thanks to W.O.P.R and the secret Pentagon learning algorithm)

To name a few points:
1. Your code must load in to memory huge binary libraries. How much RAM do you think your entire code base uses? I bet that you can't even count that high!

2. Your code must allocate an incredibly large block of memory for each move-- this is due to the bitmaps that are used. IIRC they're 32-bpp images. Simply traversing that memory would require more instructions than the entire Joshua program would use to render it's decision. Joshuas code will run on a CoCo.

3. Your code uses obfuscated libraries. In other words you do not even know what your code is doing because you can't see the API calls in the libraries that it is using. How can you claim it's more simple if you don't even know what it's doing?

The score is
Joshua ANN: 3
Victor-Victor: -1.570795

HAL-9000 ANN can write Haikus and learn things, where as your bloat-tables only know how to play a game of Tic-Tac-Toe that is so CPU heavy that it leaves the processor overheated and burning. If you ran your tic-tac-toe on an XBOX360 it could cause RROD!

Share this post


Link to post
Share on other sites
Victor-Victor    100
Quote:
Original post by Emergent
...and the table would have "learned" whatever that function was.

Table has learned? You recorded the output of some (random) function to four floats. What do you do with it now? "a= 2+3" does not mean 'a' learned addition, it means you stored some information in some location.

Can your table calculate XOR?

Share this post


Link to post
Share on other sites
Victor-Victor    100
Quote:
Original post by willh
1. Your code must load in to memory huge binary libraries. How much RAM do you think your entire code base uses? I bet that you can't even count that high!

I need 5x2+9+9x9 bytes. That's 100bytes, statically allocated. You?

I already performed tests with much better NON-ANN algorithm than yours. I posted results and all the source code so you can try it yourself. With all that branching your code would be 5-7 times slower, why don't you try it? You are DYNAMICALLY allocating memory, which is slow and you are also fragmenting memory that way. And those if-then-else... do you not see how many BRANCHING you have?! It's hideous.

Quote:

2. Your code must allocate an incredibly large block of memory for each move-- this is due to the bitmaps that are used. IIRC they're 32-bpp images. Simply traversing that memory would require more instructions than the entire Joshua program would use to render it's decision. Joshuas code will run on a CoCo.

Where do you see in the listing I need to allocate memory each time, nonsense! Are you going to say how graphics cards are slow about storing and processing textures?

If you had nothing else but 3x3 iteration loop, like many of which you have, and even if you had none of that if-then-else branching garbage - GPU processing of 9x(1024x1024) textures would still be faster. I only use RED channel, so I only need unsigned byte per weight, just as before, only faster.

Quote:

3. Your code uses obfuscated libraries. In other words you do not even know what your code is doing because you can't see the API calls in the libraries that it is using. How can you claim it's more simple if you don't even know what it's doing?

Is this trolling? It is insulting.
I'd like this person to be moderated, moderators?

Share this post


Link to post
Share on other sites
Emergent    982
Quote:
Original post by Victor-Victor
Quote:
Original post by Emergent
...and the table would have "learned" whatever that function was.

Table has learned? You recorded the output of some (random) function to four floats.


Yep. It seems silly to call that learning, right? But in essence that's all any function approximator, including a neural network, does.

Quote:
What do you do with it now? "a= 2+3" does not mean 'a' learned addition, it means you stored some information in some location.


Well it learned that "2+3=5." ;-) But I see your complaint: It does not generalize well. It can see "1+2=3" and "4+1=5" and learn those but not be able to then say "3+3=6." That's perfectly true. To this I say a few things:
1 - Using basis functions with broader support (e.g. b-splines) than Kronecker deltas will allow some "generalization" by interpolating between (and to a lesser extent extrapolating from) observations.
2 - I would nevertheless be skeptical of any really strong claims about the ability of some learning algorithm (e.g. neural networks) to generalize, due to the several no free lunch theorems. The ability of a given classifier or function approximator to generalize is inherently tied to the domain in which it is applied.

Quote:
Can your table calculate XOR?


Sure.
1 - The table entries will asymptotically approach the correct values so long as every input-output pair is seen an infinite number of times.
2 - The thresholded values will equal the true values after a finite time so long as all input-output pairs are seen "enough" (this can be made formal).
3 - You can "calculate" the XOR of a and b by just looking at the (a,b)-th entry in the table and thresholding it.

Share this post


Link to post
Share on other sites
Emergent    982
Also, I'd promised you Tic Tac Toe code (ugly though it may be), so here it is. Note that two search functions are provided: Plain old minimax ("named 'minmax'), and also minimax with alpha beta pruning (named 'minmax_AB2'); one of these functions is called by computerTakeTurn.

I'm sure you can also find other, probably nicer implementations if you google.

Even my implementation here can do a full search, even without bothering with alpha-beta pruning, with no perceptible pause. That's not because my implementation is wonderful or even because minimax is amazingly fast (it isn't), but because Tic Tac Toe is such a small game.


// Tic Tac Toe
// by Emergent
// 2009
//
// Uses minmax search to play the game of Tic Tac Toe against a human.

// Implementations:
//
// NAME DESCRIPTION EVALUATIONS
// - minmax Plain old minimax 549946
// - minmax_AB2 Minimax with alpha-beta 427120

#include <iostream>
#include <string>
#include <sstream>
using namespace std;

//#define DEBUG

// Board:
//
// -|----0--1--2--> x
// |
// 0 0 1 2
// 1 3 4 5
// 2 6 7 8
// |
// y v
//
// State (32 bits):
// bit Name
// 0 Board Position 0a
// 1 Board Position 0b
// 2 "" "" 1a
// 3 "" "" 1b
// ...
// 18 Board Position 8a
// 19 Board Position 8b
// --------------------------
// 20 Player's Turn
// --------------------------
// 21
// ... Reward bits
// 27
// --------------------------
// 28
// ... Move to get here
// 32 (If = 15, indicates "first move")
typedef unsigned long state_t; // 32 bits
#ifdef DEBUG
unsigned long evals;
#endif

const unsigned char P_INF_REWARD = 4;
const unsigned char WIN_REWARD = 3;
const unsigned char DRAW_REWARD = 2;
const unsigned char LOSE_REWARD = 1;
const unsigned char N_INF_REWARD = 0;

void printState(state_t state)
{
cout << "State: ";
for(int i = 31; i >= 0; --i)
{
cout << ((state>>i)&1);
}
cout << endl;
}

state_t setMove(state_t state, int move)
{
return (state & ~(0xF << 28)) | ((move & 0xF) << 28);
}

int getMove(state_t state)
{
return (state >> 28) & 0xF;
}

state_t setFirstMoveFlag(state_t state)
{
return setMove(state, 15);
}

bool getFirstMoveFlag(state_t state)
{
if(getMove(state) == 15)
return true;

return false;
}

state_t setReward(state_t state, int reward)
{
return (state & ~(0x7f << 21)) | ((reward & 0x7f) << 21);
}

int getReward(state_t state)
{
return (state >> 21) & 0x7f;
}

int getMarker(state_t state, int pos)
{
return (state >> (2*pos))&0x3;
}

state_t setMarker(state_t state, int pos, int mark)
{
return (state & ~(3 << (2*pos))) | (mark << (2*pos));
}

int getMarker(state_t state, int x, int y)
{
int pos = x+y*3;
return (state >> (2*pos))&0x3;
}

state_t setMarker(state_t state, int x, int y, int mark)
{
int pos = x+y*3;
return (state & ~(3 << (2*pos))) | (mark << (2*pos));
}

char markerChar(int marker)
{
switch(marker)
{
case 0:
return '_';
case 1:
return 'O';
case 2:
return 'X';
default:
return '?';
}
}

int getPlayer(state_t state)
{
// Outputs:
// player = 1 or 2

return ((state >> 20)&1) + 1;
}

state_t setPlayer(state_t state, unsigned char player)
{
// Inputs:
// player = 1 or 2
return (state & ~(1 << 20)) | (((player-1)&1) << 20);
}

void drawBoard(state_t state)
{
//cout << "Player " << getPlayer(state) << "'s Turn:\n";

cout << " |\n ----0--1--2-----> (x axis)\n";
for(int y = 0; y < 3; ++y)
{
cout << " " << y << " ";
for(int x = 0; x < 3; ++x)
{
cout << markerChar(getMarker(state, x, y));
if(x < 2)
cout << " ";
}
cout << '\n';
}
cout << " |\n v\n(y axis)\n";
}

int isEndgame(state_t state)
{
// Returns:
// 0 = nobody has won yet
// 1 = Player 1 wins
// 2 = Player 2 wins
// 3 = Draw

for(int player=1; player <= 2; ++player)
{
for(int y=0; y < 3; ++y)
if(getMarker(state, 0, y) == player &&
getMarker(state, 1, y) == player &&
getMarker(state, 2, y) == player)
return player;

for(int x=0; x < 3; ++x)
if(getMarker(state, x, 0) == player &&
getMarker(state, x, 1) == player &&
getMarker(state, x, 2) == player)
return player;

if(getMarker(state, 0, 0) == player &&
getMarker(state, 1, 1) == player &&
getMarker(state, 2, 2) == player)
return player;

if(getMarker(state, 2, 0) == player &&
getMarker(state, 1, 1) == player &&
getMarker(state, 0, 2) == player)
return player;
}

for(int pos = 0; pos < 9; ++pos)
if(getMarker(state, pos) == 0)
return 0;

return 3;
}

state_t minmax(state_t state)
{
// AI is player 1 (MAX step)
// Human is player 2 (MIN step)
//
// Returns the state at the end of the game assuming perfect play from now on.

#ifdef DEBUG
++evals;
#endif

state_t child_post;
state_t best_state;

int winner = isEndgame(state);
if(winner)
{
if(winner == 1)
return setReward(state, WIN_REWARD); // We win.
else if(winner == 2)
return setReward(state, LOSE_REWARD); // We lose.
else
return setReward(state, DRAW_REWARD); // Tie
}

if(getPlayer(state) == 1)
best_state = setReward(state, 0);
else
best_state = setReward(state, 127);

for(int move=0; move < 9; ++move)
{
if(getMarker(state, move) != 0)
continue;

state_t child_pre = state;

if(getFirstMoveFlag(state))
child_pre = setMove(child_pre, move);

child_pre = setMarker(child_pre, move, getPlayer(state));
child_pre = setPlayer(child_pre, (getPlayer(state)==1)?2:1);

child_post = minmax(child_pre);

if(getPlayer(state) == 1 && getReward(child_post) > getReward(best_state))
best_state = child_post;
else if(getPlayer(state) == 2 && getReward(child_post) < getReward(best_state))
best_state = child_post;
}

return best_state;
}

state_t minmax_AB2(state_t state, unsigned char min, unsigned char max)
{
// AI is player 1 (MAX step)
// Human is player 2 (MIN step)
//
// Returns the state at the end of the game assuming perfect play from now on.

#ifdef DEBUG
++evals;
#endif

state_t child_post;
state_t best_state;

int winner = isEndgame(state);
if(winner)
{
if(winner == 1)
return setReward(state, WIN_REWARD); // We win.
else if(winner == 2)
return setReward(state, LOSE_REWARD); // We lose.
else
return setReward(state, DRAW_REWARD); // Tie
}

if(getPlayer(state) == 1)
best_state = setReward(state, min);
else
best_state = setReward(state, max);

for(int move=0; move < 9; ++move)
{
if(getMarker(state, move) != 0)
continue;

state_t child_pre = state;

if(getFirstMoveFlag(state))
child_pre = setMove(child_pre, move);

child_pre = setMarker(child_pre, move, getPlayer(state));
child_pre = setPlayer(child_pre, (getPlayer(state)==1)?2:1);

if(getPlayer(state) == 1)
child_post = minmax_AB(child_pre, getReward(best_state), max);
else
child_post = minmax_AB(child_pre, min, getReward(best_state));

if(getPlayer(state) == 1 && getReward(child_post) > getReward(best_state))
best_state = child_post;
else if(getPlayer(state) == 2 && getReward(child_post) < getReward(best_state))
best_state = child_post;

if(getReward(best_state) > max || getReward(best_state) < min)
break;
}

return best_state;
}

state_t computerTakeTurn(state_t state)
{
#ifdef DEBUG
evals = 0;
#endif
cout << "I, computer, am thinking... ";
//state_t minmax_ret = minmax(setFirstMoveFlag(setPlayer(state,1)));
state_t minmax_ret = minmax_AB2(setFirstMoveFlag(setPlayer(state,1)), LOSE_REWARD, WIN_REWARD);
switch(getReward(minmax_ret))
{
case WIN_REWARD:
cout << "Silly human! I have already won!\n";
break;
case LOSE_REWARD:
cout << "Oh no! You may beat me!\n";
break;
case DRAW_REWARD:
cout << "I predict a draw.\n";
break;
default:
cout << "I am confused. My creator needs to fix me.\n";
break;
}
#ifdef DEBUG
cout << "(I searched " << evals << " nodes.)\n";
#endif

return setPlayer(setMarker(state, getMove(minmax_ret), 1), 2);
}

state_t humanTakeTurn(state_t state)
{
int x, y;

cout << "Your move (Format: \"x y\" E.g., \"0 1\"): ";

for(;;)
{
string line;
getline(cin, line);

stringstream ss(line);

ss >> x >> y;

if(!ss.fail() && x >= 0 && y >= 0 && x < 3 && y < 3 && getMarker(state,x,y)==0)
break;

cout << "Bad input; try again: ";
}
return setPlayer(setMarker(state, x, y, 2), 1);
}

bool binaryUserChoice(string question, char opt1, char opt2)
{
// Returns TRUE if opt1 is chosen, FALSE if opt2 is chosen.

// Strip final question mark, if it exists.
if(question[question.length()-1]=='?')
question = question.substr(0, question.length()-1);

cout << question << " "
<< "(Type \"" << opt1 << "\" or \"" << opt2 << "\" and hit ENTER)? ";

for(;;)
{
string line;
getline(cin, line);

if(line.length() == 1)
{
if(line[0] == opt1)
return true;

if(line[0] == opt2)
return false;
}

cout << "Bad input; try again: ";
}
}

int main()
{
cout << "==== TIC TAC TOE ===\n"
<< "Welcome! You play as 'X;' the computer plays as 'O.'\n";

do
{
state_t state = 0;

if(!binaryUserChoice("Would you like to go first or second?", '1', '2'))
{
state = computerTakeTurn(state);
}

drawBoard(state);

while(!isEndgame(state))
{
state = humanTakeTurn(state);
state = computerTakeTurn(state);
drawBoard(state);
cout << endl;
}

switch(isEndgame(state))
{
case 1:
cout << "I, computer, have defeated you! Bow before my silicon might!\n";
break;
case 2:
cout << "You win, oh magnificent human!\n";
break;
case 3:
cout << "The game was a draw.\n";
break;
}
cout << endl;

}while(binaryUserChoice("Rematch?", 'y', 'n'));

cout << "So long!\n\n";

return 0;
}

Share this post


Link to post
Share on other sites
TriKri    124
Quote:
Original post by EJH
The purpose of machine learning methods is to solve problems that cannot reasonably be hand-coded (thus the complex car/track physics in Forza and Colin McRae are a good example of ANN application). Potentially, as game AI and physics becomes more complex machine learning application will increase.


Physics, do you really mean that AI can be used for game physics?

Share this post


Link to post
Share on other sites
willh    160
Quote:
Original post by TriKri
Quote:
Original post by EJH
The purpose of machine learning methods is to solve problems that cannot reasonably be hand-coded (thus the complex car/track physics in Forza and Colin McRae are a good example of ANN application). Potentially, as game AI and physics becomes more complex machine learning application will increase.


Physics, do you really mean that AI can be used for game physics?


Sure. These guys used 3 ANNs to fly a helicopter. Pretty cool!
http://julian.togelius.com/DeNardi2006Evolution.pdf

You could use an AI for anything, in theory. I think what many people in here (myself included) would say though is 'Why?'

Let's use a screw-driver as an analogy. You can use just about any screw-driver to dig a hole . If you needed to, you could even use a screw-driver to hammer nails. While a screw drive can these things there are much better tools for the job; like a shovel and a hammer.

Here is a link to a Java applet that uses an ANN for image compression. It's an interesting experiment, but wouldn't perform nearly as well as JPEG.
http://neuron.eng.wayne.edu/bpImageCompression9PLUS/bp9PLUS.html

Tools that fit in to the 'AI' category are usually good choices when you need to find solutions to problems that don't have an obvious right or wrong answer, or when you're seeking something inventive but not neccesarily optimal.

We haven't yet seen the 'age of AI' mostley because we're not at the stage in our society where they would be practical. That is changing though. Almost every digital camera has an AI in it for the face detection (thank you Viola and Jones!!!!).

Share this post


Link to post
Share on other sites
TriKri    124
Quote:
Original post by willh
Quote:
Original post by TriKri
Physics, do you really mean that AI can be used for game physics?


Sure. These guys used 3 ANNs to fly a helicopter. Pretty cool!
http://julian.togelius.com/DeNardi2006Evolution.pdf


I guess you mean that they use it to steer things in a phisical environment? Because the rules of physics are still pretty much hard coded I guess?

Quote:
Original post by willh
Here is a link to a Java applet that uses an ANN for image compression. It's an interesting experiment, but wouldn't perform nearly as well as JPEG.
http://neuron.eng.wayne.edu/bpImageCompression9PLUS/bp9PLUS.html


Hm, I actually created an ANN library before (back in the days when I coded in VB), and tried to learn it to compress very low-res black and white images, and to unzip them again (basically I had a number of in nodes, som hidden layers of which on contained fewer nodes than the in layer, maybe half, and one out layer with as many nodes as the input layer). It didn't work very well. Then of course I didn't know especially much about ANN:s, not about how the training should be done in the best way, nothing about how many hidden layers that should be used etc. Kind of interesting though. The result was crap, but still. ;)

Share this post


Link to post
Share on other sites
Victor-Victor    100
Quote:
Original post by Emergent
Yep. It seems silly to call that learning, right? But in essence that's all any function approximator, including a neural network, does.


Yes, it's silly, because that is not learning. What you're talking about is one-to-one memory mapping, that's nothing like what NN does. Neural networks is not just memory, it's also a CPU, it integrates *logic* together with information.

Why would anyone "train" some independent values in some static table if any such memory array can be populated by simply addressing a memory one-to-one?


When you train NN you change the dynamics of the whole system, not just memory, but the way it processes the information, the way it "thinks". Everything here is connected and interdependent, function/logic and memory, which is why it needs to be adjusted step-by-step, unlike anything else.

Static tables have only one static function, a simple "recall". Program searches the input database, then if and when it finds the exact match it returns whatever is stored there as output pair. It's one-to-one mapping, and if it wasn't, it would be random or probabilistic, but the important thing is - there is no *processing* here, which is why we call it a 'look-up table' and use it for optimization.


NNs can indeed learn, not just memorize. Try to map 255,168 combinations from simple 3x3 tic-tac-toe game one-to-one to a look-up table. That's about 510,336 bytes, yet the *logic* of it all can apparently fit in only 81 bytes by using ANN type of storage/processing.


Yes, you actually can show ANN: 5=2+3, 7=2+5, 9=1+8.... and it could learn ADDITION, not just results. There is simply not enough space in the universe to map logic one-to-one. The number of COMBINATIONS for anything over two bits of input increases very dramatically. So, instead of to memorize the answers, ANN can somehow generalize it, like humans do, and use this generalized *logic* as a function to really calculate, not just recall, the answers and produce correct output even for inputs it has never seen before.

"Give a man a fish and he will eat for a day. Teach him how to fish and he will eat for a lifetime."


Quote:
Original post by Emergent
3 - You can "calculate" the XOR of a and b by just looking at the (a,b)-th entry in the table and thresholding it.


What you have is no threshold, it was just some initial value.

Why do you think some static table would ever need to be initialized in such indirect way? You can populate the table directly, this is no ANN so you can just put the results exactly where and how you want them. You populated table with some fixed results, but you did it "slowly" in random steps. Why? Where did you ever see anyone is using this kind of learning methods on anything but neural networks?


Are you seriously suggesting any of those minimax or whatever other algorithms can compete with this:

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;
}
}




TriKri,

Yes, it does not make any sense to use AI for physics equations. What EJH meant, most likely, is that physics is getting more and more complex, requiring more and more complex AI to be able to handle it, like driving a car.

Taking it further, eventually we might see AI walking and actually looking where it's gonna step next, which will then involve a lot of inverse kinematics type of physics/math, and only here you could substitute "physics of walking" by simulating muscle contraction and relaxation with NN, just as is done in robotics. Instead of driving a car AI would drive a body, instead of steering wheel and gas pedal, it would contract and relax appropriate muscles, while obeying whatever laws of physics program throws at it.

Share this post


Link to post
Share on other sites
willh    160
Quote:
Original post by Victor-Victor
Yes, it's silly, because that is not learning.

That's what she said.

Quote:

What you're talking about is one-to-one memory mapping, that's nothing like what NN does. Neural networks is not just memory, it's also a CPU, it integrates *logic* together with information.

You could represent the entire thing using TinkerToy too.

Quote:

Why would anyone "train" some independent values in some static table if any such memory array can be populated by simply addressing a memory one-to-one?

[u]What if you don't know what the values are supposed to be?[/u]

Quote:

When you train NN you change the dynamics of the whole system, not just memory, but the way it processes the information, the way it "thinks".

Changing the memory facilitates this.

Quote:

Static tables have only one static function, a simple "recall". Program searches the input database, then if and when it finds the exact match it returns whatever is stored there as output pair. It's one-to-one mapping, and if it wasn't, it would be random or probabilistic, but the important thing is - there is no *processing* here, which is why we call it a 'look-up table' and use it for optimization.

Please refer to definition of Finite state machine

Quote:

There is simply not enough space in the universe to map logic one-to-one.

Can you prove it? I wonder how the universe does it?? Let's ask God.

Quote:

The number of COMBINATIONS for anything over two bits of input increases very dramatically.

The term is 'exponential'. Real ANN's don't work in binary. They use trinary. We learned this during the Syndicate Wars, when the KGB tried to infiltrate the Society of Artifical Neural Networks League of Intelligent Designers.

Quote:

So, instead of to memorize the answers, ANN can somehow generalize it, like humans do, and use this generalized *logic* as a function to really calculate, not just recall, the answers and produce correct output even for inputs it has never seen before.

Can you prove it?

Quote:

"Give a man a fish and he will eat for a day. Teach him how to fish and he will eat for a lifetime."

What if you teach him how to fish but then his fishing pole breaks? Ha! A real ANN would forsee this. Are you sure you're not really a robot?

Quote:

What you have is no threshold, it was just some initial value.

Threshold = some initial value. Initial value = number. Number = sequence of bits. Sequence = Medusa. Flash Gordon = Kaptian Krunch. Kaptian Krunch = BlueBox. BlueBox = 2600. 2600 = number. Number = threshold. Step 3 = profit.

Quote:

Why do you think some static table would ever need to be initialized in such indirect way?

Why do you think some static table would ever need to be initalized in such indirect way?

Quote:

Where did you ever see anyone is using this kind of learning methods on anything but neural networks?

That is interesting. Tell me more.

Quote:

Are you seriously suggesting any of those minimax or whatever other algorithms can compete with this:

Nobody ever said it would.


Quote:

Yes, it does not make any sense to use AI for physics equations. What EJH meant, most likely, is that physics is getting more and more complex, requiring more and more complex AI to be able to handle it, like driving a car.

Physics changes every day. Just yesterday someone had to change the speed of light because it exceeded the state of Nevadas single occupancy vehicle regulations. Note to arcade game players: do not eat the urinal cakes.

Quote:

Taking it further, eventually we might see AI walking and actually looking where it's gonna step next

You sir, are a visionary. Maybe one day a Japanese car company will build a walking robot and use it as a PR tool. Could you imagine if a Boston-based robotics company could build a robotic pony that is able to walk over uneven terrain without even falling down? Maybe someday in the far distant future DARPA will hold a contest to see who can build a fully autonomous car that can drive all on its own. If we're really lucky, and Joshua doesn't explode us all, a computer might finally be able to beat a grandmaster at Chess. That would be something!!

Who am I kidding-- those things will never happen!



Share this post


Link to post
Share on other sites
ibebrett    205
Quote:
Original post by Victor-Victor
I don't understand what do you mean by "toy example" and "not practical suggestion". Is it true or not? ANN research was stuck frozen for 30 years just because everyone assumed ANN can't do XOR. =


This is utter bs. ANN's can do XOR no problem. One layer networks can't because xor is not linearly separable. No one was stupid enough to think that an ANN cannot learn XOR, you just couldn't do it with one line in 2d space.

Share this post


Link to post
Share on other sites
Victor-Victor    100
Quote:
Original post by ibebrett
Quote:
Original post by Victor-Victor
I don't understand what do you mean by "toy example" and "not practical suggestion". Is it true or not? ANN research was stuck frozen for 30 years just because everyone assumed ANN can't do XOR. =


This is utter bs. ANN's can do XOR no problem. One layer networks can't because xor is not linearly separable. No one was stupid enough to think that an ANN cannot learn XOR, you just couldn't do it with one line in 2d space.


Do not underestimate the power of human stupidity.


http://en.wikipedia.org/wiki/Perceptron
http://en.wikipedia.org/wiki/Perceptrons_(book)

In 1969 a famous book entitled Perceptrons by Marvin Minsky and Seymour Papert showed that it was impossible for these classes of network to learn an XOR function. They conjectured (incorrectly) that a similar result would hold for a perceptron with three or more layers.

Often-cited Minsky/Papert text caused a significant decline in interest and funding of neural network research. It took ten more years until neural network research experienced a resurgence in the 1980s.

The XOR affair - Critics of the book state that the authors imply that, since a single artificial neuron is incapable of implementing some functions such as the XOR logical function, larger networks also have similar limitations, and therefore should be dropped. Later research on three-layered perceptrons showed how to implement such functions, therefore saving the technique from obliteration.


Yes, people are stupid. They can blindly believe even the most ridiculous of books, if you only convince them it was written by some authority, Minsky in this particular case. Yes, people do not think, they will believe Sun revolves around the Earth, and they will put you in jail if you think otherwise. Now, look back at the history of science and you will realize nothing has changed since then. "All truth goes through three stages. First it is ridiculed, then it is violently opposed, finally it is accepted as self-evident."(Schopenhauer)

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