Advertisement

Artificial Neural Networks

Started by September 09, 2009 12:01 PM
71 comments, last by Victor-Victor 15 years, 1 month ago
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.
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!
Advertisement
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?
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?
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.
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 DEBUGunsigned long evals;#endifconst 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;}
Advertisement
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?

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!!!!).
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. ;)
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[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 && !(a&(1<<i)||b&(1<<i))) 			j= Out, *m=i; Out= 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.

This topic is closed to new replies.

Advertisement