?? article771.asp.htm
字號:
<!--<TABLE>
<TR>
<TD>
</TD>
<TD>
See Also:
</TD>
</TR>
<TR>
<TD COLSPAN=2>-->
<CENTER><SPAN CLASS="title">Neural Netware</SPAN>
<BR><SPAN CLASS="author">by <A HREF="mailto:necron@xgames3d.com">Andre' LaMothe</A> - <A HREF="javascript:if(confirm('http://www.xgames3d.com/ \n\n這個文件不能通過 Teleport Pro 取回, 因為 它被訪問于一個域或在它的起始地址邊界外部的路徑上. \n\n你想從服務(wù)器打開它嗎?'))window.location='http://www.xgames3d.com/'" tppabs="http://www.xgames3d.com/">Xtreme Games</A></SPAN></CENTER>
<H1>And There Was Light...</H1>
<P>The funny thing about high technology is that sometimes it's hundreds of years old! For example, Calculus was independently invented by both Newton and Leibniz over 300 years ago. What used to be magic, is now well known. And of course we all know that geometry was invented by Euclid a couple thousand years ago. The point is that many times it takes years for something to come into "vogue". <I>Neural Nets</I> are a prime example. We all have heard about neural nets, and about what their promises are, but we don't really see too many real world applications such as we do for <I>ActiveX</I> or the <I>Bubblesort.</I> The reason for this is that the true nature of neural nets is extremely mathematical and understanding and proving the theorems that govern them takes Calculus, Probability Theory, and Combinatorial Analysis not to mention Physiology and Neurology.
<P>The key to unlocking any technology is for a person or persons to create a Killer App for it. We all know how <I>DOOM</I> works by now, i.e. by using BSP trees. However, John Carmack didn't invent them, he read about them in a paper written in the 1960's. This paper described BSP technology. John took the next step an realized what BSP trees could be used for and <I>DOOM</I> was born. I suspect that Neural Nets may have the same revelation in the next few years. Computers are fast enough to simulate them, VLSI designers are building them right into the silicon, and there are hundreds of books that have been published about them. And since Neural Nets are more mathematical entities then anything else, they are not tied to any physical representation, we can create them with software or create actual physical models of them with silicon. The key is that neural nets are abstractions or models.
<P>In many ways the computational limits of digital computers have been realized. Sure we will keep making them faster, smaller and cheaper, but digital computers will always process digital information since they are based on deterministic binary models of computation. Neural nets on the other hand are based on different models of computation. They are based on highly parallel, distributed, probabilistic models that don't necessarily model a solution to a problem as does a computer program, but model a network of cells that can find, ascertain, or correlate possible solutions to a problem in a more biological way by solving the problem a in little pieces and putting the result together. This article is a whirlwind tour of what neural nets are, and how they work in as much detail as can be covered in a few pages. I know that a few pages doesn't do the topic justice, but maybe we can talk the management into a small series???
<BLOCKQUOTE>
<SPAN CLASS="maintext-2"><FONT COLOR="#000088"><I>Figure 1.0 - A Basic Biological Neuron.</I></FONT></SPAN>
<P ALIGN=CENTER><IMG SRC="xneuralnet/Image14.jpg" tppabs="http://www.gamedev.net/reference/articles/xneuralnet/Image14.jpg" width="619" height="302">
</BLOCKQUOTE>
<H1>Biological Analogs</H1>
<P>Neural Nets were inspired by our own brains. Literally, some brain in someone's head said, "I wonder how I work?" and then proceeded to create a simple model of itself. Weird huh? The model of the standard neurode is based on a simplified model of a human neuron invented over 50 years ago. Take a look at Figure 1.0. As you can see, there are 3 main parts to a neuron, they are:
<BLOCKQUOTE>
<FONT COLOR=RED>
<UL>
<LI><I>Dendrite(s)</I>........................Responsible for collecting incoming signals.
<LI><I>Soma</I>................................Responsible for the main processing and summation of signals.
<LI><I>Axon</I>.................................Responsible for transmitting signals to other dendrites.
</UL>
</FONT>
</BLOCKQUOTE>
<P>The average human brain has about 100,000,000,000 or 10<SUP>11</SUP> neurons and each neuron has up to 10,000 connections via the <I>dendrites</I>. The signals are passed via electro-chemical processes based on <I>NA</I> (sodium), <I>K</I> (potassium), and <I>CL</I> (chloride) ions. Signals are transferred by accumulation and potential differences caused by these ions, the chemistry is unimportant, but the signals can be thought of simple electrical impulses that travel from <I>axon </I>to<I> dendrite</I>. The connections from one dendrite to axon are called <I>synapses</I> and these are the basic signal transfer points.
<P>So how does a neuron work? Well, that doesn't have a simple answer, but for our purposes the following explanation will suffice. The dendrites collect the signals received from other neurons, then the soma performs a summation of sorts and based on the result causes the axon to fire and transmit the signal. The firing is contingent upon a number of factors, but we can model it as an transfer function that takes the summed inputs, processes them, and then creates an output if the properties of the transfer function are met. In addition, the output is non-linear in real neurons, that is, signals aren't digital, they are analog. In fact, neurons are constantly receiving and sending signals and the real model of them is frequency dependent and must be analyzed in the <I>S-domain</I> (the frequency domain). The real transfer function of a simple biological neuron has, in fact, been derived and it fills a number of chalkboards up.
<P>Now that we have some idea of what neurons are and what we are trying to model, let's digress for a moment and talk about what we can use neural nets for in video games.
<H1>Applications to Games</H1>
<P>Neural nets seem to be the answer that we all are looking for. If we could just give the characters in our games a little brains, imagine how cool a game would be! Well, this is possible in a sense. Neural nets model the structure of neurons in a crude way, but not the high level functionality of reason and deduction, at least in the classical sense of the words. It takes a bit of thought to come up with ways to apply neural net technology to game AI, but once you get the hang of it, then you can use it in conjunction with deterministic algorithms, fuzzy logic, and genetic algorithms to create very robust thinking models for your games. Without a doubt better than anything you can do with hundreds of <I>if-then</I> statements or scripted logic. Neural nets can be used for such things as:
<P><I>Environmental Scanning and Classification</I> - A neural net can be feed with information that could be interpreted as vision or auditory information. This information can then be used to select an output response or teach the net. These responses can be learned in real-time and updated to optimize the response.
<P><I>Memory</I> - A neural net can be used by game creatures as a form of memory. The neural net can learn through experience a set of responses, then when a new experience occurs, the net can respond with something that is the best guess at what should be done.
<P><I>Behavioral Control</I> - The output of a neural net can be used to control the actions of a game creature. The inputs can be various variables in the game engine. The net can then control the behavior of the creature.
<P><I>Response Mapping</I> - Neural nets are really good at "association" which is the mapping of one space to another. Association comes in two flavors: <I>autoassociation</I> which is the mapping of an input with itself and <I>heterassociation</I> which is the mapping of an input with something else. Response mapping uses a neural net at the back end or output to create another layer of indirection in the control or behavior of an object. Basically, we might have a number of control variables, but we only have crisp responses for a number of certain combinations that we can teach the net with. However, using a neural net on the output, we can obtain other responses that are in the same ballpark as our well defined ones.
<P>The above examples may seem a little fuzzy, and they are. The point is that neural nets are tools that we can use in whatever way we like. The key is to use them in cool ways that make our <I>AI</I> programming simpler and make game creatures respond more intelligently.
<H1>Neural Nets 101</H1>
<P>In this section we're going to cover the basic terminology and concepts used in neural net discussions. This isn't easy since neural nets are really the work of a number of different disciplines, and therefore, each discipline creates their own vocabulary. Alas, the vocabulary that we will learn is a good intersection of all the well know vocabularies and should suffice. In addition, neural network theory is replete with research that is redundant, meaning that many people re-invent the wheel. This has had the effect of creating a number of neural net architectures that have names. I will try to keep things as generic as possible, so that we don't get caught up in naming conventions. Later in the article we will cover some nets that are distinct enough that we will refer to them will their proper names. As you read don't be too alarmed if you don't make the "connections" with all of the concepts, just read them, we will cover most of them again in full context in the remainder of the article. Let's begin...
<BLOCKQUOTE>
<SPAN CLASS="maintext-2"><FONT COLOR="#000088"><I>Figure 2.0 - A Single Neurode with n Inputs.</I></FONT></SPAN>
<P ALIGN=CENTER><IMG SRC="xneuralnet/Image15.jpg" tppabs="http://www.gamedev.net/reference/articles/xneuralnet/Image15.jpg" width="553" height="339">
</BLOCKQUOTE>
<P>Now that we have seen the wetware version of a neuron, let's take a look at the basic artificial neuron to base our discussions on. Figure 2.0 is a graphic of a standard <I>"neurode"</I> or "<I>artificial neuron"</I>. As you can see, it has a number of inputs labeled <I>X<SUB>1</SUB> - X<SUB>n</SUB></I> and <I>B</I>. These inputs each have an associated weight <I>w<SUB>1</SUB> - w<SUB>n</SUB></I>, and <I>b</I> attached to them. In addition, there is a summing junction <I>Y</I> and a single output <I>y</I>. The output <I>y</I> of the neurode is based on a transfer or <I>"activation"</I> function which is a function of the net input to the neurode. The inputs come from the <I>X<SUB>i'</SUB>s</I> and from <I>B</I> which is a bias node. Think of <I>B</I> as a <I>"past history",</I> <I>"memory",</I> or <I>"inclination".</I> The basic operation of the neurode is as follows: the inputs <I>X<SUB>i</SUB></I> are each multiplied by their associated weights and summed. The output of the summing is referred to as the i<I>nput activation</I> <I>Y<SUB>a</SUB></I>. The activation is then fed to the activation function <I>f<SUB>a</SUB>(x)</I> and the final output is <I>y.</I> The equations for this is:
<BLOCKQUOTE>
<SPAN CLASS="maintext-2"><FONT COLOR="#000088"><I>Eq. 1.0</I></FONT></SPAN>
<FONT COLOR=RED>
<P><I> n<br>
Y</I><SUB>a</SUB> = <I>B</I>*<I>b</I> + <font size="2" face="Symbol">q</font> <I>X</I><SUB>i</SUB> * <I>w</I><SUB>i</SUB>
<br>
<I> i
</I>=1<br>
<P>AND
<P><I>y</I> = <I>f<SUB>a</SUB>(Y<SUB>a</SUB>)</I>
</FONT>
</BLOCKQUOTE>
<P>The various forms of <I>f<SUB>a</SUB>(x)</I> will be covered in a moment.
<P>Before we move on, we need to talk about the inputs <I>X<SUB>i</SUB></I>, the weights <I>w<SUB>i</SUB></I>, and their respective domains. In most cases, inputs consist of the positive and negative integers in the set ( -<font face="Symbol">q</font> , +inputs are <font face="Symbol">q</font> ). However, many neural nets use simpler <I>bivalent</I> values (meaning that they have only two values). The reason for using such a simple input scheme is that ultimately all <I>binary</I> as image or <I>bipolar</I> and complex inputs are converted to pure binary or bipolar representations anyway. In addition, many times we are trying to solve computer problems such or voice recognition which lend themselves to bivalent representations. Nevertheless, this is not etched in stone. In any case, the values used in bivalent systems are primarily 0 and 1 in a binary system or -1 and 1 in a bipolar system. Both systems are similar except that bipolar representations turn out to be mathematically better than binary ones. The weights <I>w<SUB>i</SUB></I> on each input are typically in the range bias ( -<font face="Symbol">q</font> , +<font face="Symbol">q</font> ). and are referred to as <I>excitatory</I>, and <I>inhibitory</I> for positive and negative values respectively. The extra input <I>B</I> which is called the is always 1.0 and is scaled or multiplied by <I>b</I>, that is, <I>b</I> is it's weight in a sense. This is illustrated in Eq.1.0 by the leading term.
<P>Continuing with our analysis, once the activation <I>Y<SUB>a</SUB></I> is found for a neurode then it is applied to the activation function and the output <I>y</I> can be computed. There are a number of activation functions and they have different uses. The basic activation functions <I>f<SUB>a</SUB>(x)</I> are:
<BLOCKQUOTE>
<CENTER>
<table border="1" cellpadding="8" cellspacing="8">
<tr>
<td><I>Step</I></td>
<td><I>Linear </I></td>
<td><I>Exponential</I></td>
</tr>
<tr>
<td><IMG SRC="xneuralnet/Image4.gif" tppabs="http://www.gamedev.net/reference/articles/xneuralnet/Image4.gif" align="left"
hspace="12" width="100" height="75"></td>
<td><IMG SRC="xneuralnet/Image3.gif" tppabs="http://www.gamedev.net/reference/articles/xneuralnet/Image3.gif" align="left"
hspace="12" width="104" height="78"></td>
<td><IMG SRC="xneuralnet/Image5.gif" tppabs="http://www.gamedev.net/reference/articles/xneuralnet/Image5.gif" align="left"
hspace="12" width="100" height="75"></td>
</tr>
<tr>
<td><I>F<SUB>s</SUB>(x)</I> =1, if <I>x</I>
<font size="2" face="Symbol">'</font><font face="Symbol">q</font></td>
<td><I>F<SUB>l</SUB>(x)</I> = <I>x</I>,
for all <I>x</I></td>
<td><I>F<SUB>e</SUB>(x)</I> =
1/(1+e<SUP>-</SUP><font face="Symbol"><SUP>s</SUP></font><SUP> <I>x</I></SUP>)</td>
</tr>
</table>
</CENTER>
</BLOCKQUOTE>
<P>The equations for each are fairly simple, but each are derived to model or fit various properties.
<P>The <I>step</I> function is used in a number of neural nets and models a neuron firing when a critical input signal is reached. This is the purpose of the factor <font face="Symbol">q</font>, it models the critical input level or threshold that the neurode should fire at. The <I>linear</I> <I>activation</I> function is used when we want the output of the neurode to more closely follow the input activation. This kind of activation function would be used in modeling <I>linear systems</I> such as basic motion with constant velocity. Finally, the <I>exponential</I> <I>activation function is</I> used to create a <I>non-linear response</I> which is the only possible way to create neural nets that have non-linear responses and model non-linear processes. The <I>exponential activation function</I> is key in advanced neural nets since the composition of linear and step activation functions will <I>always</I> be linear or step, we will never be able to create a net that has non-linear response, therefore, we need the exponential activation function to address the non-linear problems that we want to solve with neural nets. However, we are not locked into using the exponential function. <I>Hyperbolic</I>, <I>logarithmic</I>, and <I>transcendental</I> functions can be used as well depending on the desired properties of the net. Finally, we can scale and shift all the functions if we need to.
<BLOCKQUOTE>
<SPAN CLASS="maintext-2"><FONT COLOR="#000088"><I>Figure 3.0 - A 4 Input, 3 Neurode, SingleLayer Neural Net.</I></FONT></SPAN>
<P ALIGN=CENTER><IMG SRC="xneuralnet/Image16.jpg" tppabs="http://www.gamedev.net/reference/articles/xneuralnet/Image16.jpg" width="642" height="379">
<P><SPAN CLASS="maintext-2"><FONT COLOR="#000088"><I>Figure 4.0 - A 2 Layer Neural Network.</I></FONT></SPAN>
<p ALIGN=CENTER><IMG SRC="xneuralnet/Image17.jpg" tppabs="http://www.gamedev.net/reference/articles/xneuralnet/Image17.jpg" width="591" height="335">
</BLOCKQUOTE>
<P>As you can imagine, a single neurode isn't going to do alot for us, so we need to take a group of them and create a layer of neurodes, this is shown in Figure 3.0. The figure illustrates a single layer neural network. The neural net in Figure 3.0 has a number of inputs and a number of output nodes. By convention this is a single layer net since the input layer is not counted unless it is the only layer in the network. In this case, the input layer is also the output layer and hence there is one layer. Figure 4.0 shows a two layer neural net. Notice that the input layer is still not counted and the internal layer is referred to as <I>"hidden".</I> The output layer is referred to as the <I>output</I> or <I>response</I> layer. Theoretically, there is no limit to the number of layers a neural net can have, however, it may be difficult to derive the relationship of the various layers and come up with tractable training methods. The best way to create multilayer neural nets is to make each network one or two layers and then connect them as components or functional blocks.
<P>All right, now let's talk about <I>temporal</I> or time related topics. We all know that our brains are fairly slow compared to a digital computer. In fact, our brains have cycle times in the millisecond range whereas digital computers have cycle times in the nanosecond and soon sub-nanosecond times. This means that signals take time to travel from neuron to neuron. This is also modeled by artificial neurons in the sense that we perform the computations layer by layer and transmit the results sequentially. This helps to better model the time lag involved in the signal transmission in biological systems such as us.
<P>We are almost done with the preliminaries, let's talk about some high level concepts and then finish up with a couple more terms. The question that you should be asking is, "what the heck to neural nets do?" This is a good question, and it's a hard one to answer definitively. The question is more, "what do you want to try and make them do?" They are basically mapping devices that help map one space to another space. In essence, they are a type of memory. And like any memory we can use some familiar terms to describe them. Neural nets have both <I>STM</I> (<I>Short Term Memory</I>) and <I>LTM</I> (<I>Long Term Memory</I>). STM is the ability for a neural net to remember something it just learned, whereas, LTM is the ability of a neural net to remember something it learned some time ago amongst its new learning. This leads us to the concepts of <I>plasticity</I> or in other words how a neural net deals with new information or training. Can a neural net learn more information and still recall previously stored information correctly? If so, does the neural net become unstable since it is holding so much information that the data starts to overlapping or has common intersections. This is referred to as <I>stability.</I> The bottom line is we want a neural net to have a good LTM, a good STM, be plastic (in most cases) and exhibit stability. Of course, some neural nets have no analog to memory they are more for functional mapping, so these concepts don't apply as is, but you get the idea. Now that we know about the aforementioned concepts relating to memory, let's finish up by talking some of the mathematical factors that help measure and understand these properties.
<P>One of the main uses for neural nets are memories that can process input that is either incomplete or noisy and return a response. The response may be the input itself <I>(autoassociation) </I>or another output that is totally different from the input <I>(heteroassociation).</I> Also, the mapping may be from a <I>n</I>-dimensional space to a <I>m</I>-dimensional space and non-linear to boot. The bottom line is that we want to some how store information in the neural net so that inputs (perfect as well as noisy) can be processed in parallel. This means that a neural net is a kind of hyperdimensional memory unit since it can associate an input <I>n</I>-tuple with an output <I>m</I>-tupple where <I>m</I> can equal <I>n</I>, but doesn't have to.
<P>What neural nets do in essence is partition an <I>n</I>-dimensional space into regions that uniquely map the input to the output or classify the input into distinct classes like a funnel of sorts. Now, as the number of input values (vectors) in the input data set increase which we will refer to as <I>S</I>, it logically follows that the neural net is going to have harder time separating the information. And as a neural net is filled with information, the input values that are to be recalled will overlap since the input space can no longer keep everything partitioned in a finite number of dimensions. This overlap results in <I>crosstalk,</I> meaning that some inputs are not as distinct as they could be. This may or may not be desired. Although this problem isn't a concern in all cases, it is a concern in associative memory neural nets, so to illustrate the concept let's assume that we are trying to associate <I>n</I>-tuple input vectors with some output set. The output set isn't as much of a concern to proper functioning as is the input set <I>S</I> is.
<P>If a set of inputs <I>S</I> is straight binary then we are looking at sequences in the form 1101010...10110 let's say that our input bit vectors are only 3 bits each, therefore the entire input space consist of the vectors:
<BLOCKQUOTE>
<FONT COLOR=RED>
<P><I>v</I><SUB><I>0</I></SUB> = (0,0,0), <I>v</I><SUB><I>1</I></SUB>
= (0,0,1), <I>v</I><SUB><I>2</I></SUB> = (0,1,0), <I>v</I><SUB><I>3</I></SUB>
= (0,1,1), <I>v</I><SUB><I>4</I></SUB> = (1,0,0), <I>v</I><SUB><I>5</I></SUB>
= (1,0,1), <I>v</I><SUB><I>6</I></SUB> = (1,1,0),
<P><I>v</I><SUB><I>7</I> </SUB>= (1,1,1)
</FONT>
</BLOCKQUOTE>
<P>To be more precise the <I>Basis</I> for this set of vectors is:
<BLOCKQUOTE>
<FONT COLOR=RED>
<P><I>v</I> = (1,0,0) * <I>b</I><SUB><I>2</I></SUB>
+ (0,1,0) * <I>b</I><SUB><I>1</I></SUB> + (0,0,1) * <I>b</I><SUB><I>0</I></SUB>,
where <I>b</I><SUB><I>i</I></SUB> can take on the values 0 or 1.
</FONT>
</BLOCKQUOTE>
<P>For example if we let <I>b</I><SUB><I>2</I></SUB>=1, <I>b</I><SUB><I>1</I></SUB>=0, and <I>b</I><SUB><I>0</I></SUB>=1 then we get the vector:
<BLOCKQUOTE>
<FONT COLOR=RED>
<P><I>v</I> = (1,0,0) * 1 + (0,1,0) * 0 + (0,0,1)
* 1 = (1,0,0) + (0,0,0) + (0,0,1) = (1,0,1) which is <I>v</I><SUB><I>5</I></SUB>
in our possible input set.
</FONT>
</BLOCKQUOTE>
<P>A <I>basis</I> is a special vector summation that describes a set of vectors in a space. So <I>v</I> describes all the vector in our space. Now to make a long story short, the more <I>orthogonal</I> the vectors in the input set are the better they will distribute in a neural net and the better they can be recalled. Orthogonality refers to the independence of the vectors or in other words if two vector are orthogonal then their dot product is 0, their projection onto one another is 0, and they can't be written in terms of one another. In the set <I>v</I> there are a lot of orthogonal vectors, but they come in small groups, for example <I>v</I><SUB><I>0</I></SUB> is orthogonal to all the vectors, so we can always include it. But if we include <I>v</I><SUB>1</SUB> in our set <I>S</I> then the only other vectors that will fit and maintain orthogonality are <I>v</I><SUB><I>2</I></SUB> and <I>v</I><SUB><I>4</I></SUB> or the set:
<BLOCKQUOTE>
<FONT COLOR=RED>
<P><I>v</I><SUB><I>0</I></SUB> = (0,0,0), <I>v</I><SUB><I>1</I></SUB>
= (0,0,1), <I>v</I><SUB><I>2</I></SUB>= (0,1,0), <I>v</I><SUB><I>4</I></SUB>
= (1,0,0)
</FONT>
</BLOCKQUOTE>
<P>Why? Because <I>v</I><SUB>i</SUB> <font face="Symbol">.</font> <I>v</I><SUB>j</SUB> for all <I>i,j</I> from 0..3 is equal to 0. In other words, the dot product of all the pairs of vectors in 0, so they must all be orthogonal. Therefore, this set will do very well in a neural net as input vectors. However, the set:
<BLOCKQUOTE>
<FONT COLOR=RED>
<P><I>v</I><SUB><I>6</I></SUB> = (1,1,0), <I>v</I><SUB><I>7</I></SUB>
= (1,1,1)
</FONT>
</BLOCKQUOTE>
<P>will potentially do poorly as inputs since <I>v</I><SUB>6</SUB><font face="Symbol">.</font><I>v</I><SUB>7</SUB> is non-zero or in a binary system it is 1. The next question is, "can we measure this orthogonality?" The answer is yes. In the binary vector system there is a measure called hamming distance. It is used to measure the n-dimensional distance between binary bit vectors. It is simply, the number of bits that are different between two vectors. For example the vectors:
?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -