Jump to content
  • Advertisement
  • Remove ads and support GameDev.net for only $3. Learn more: The New GDNet+: No Ads!

  • 09/07/99 02:50 PM
    Sign in to follow this  

    AI Uncertainty and Bayesian Networks - comp.ai.games Thread

    Artificial Intelligence

    GameDev.net
    <%Topic="AI Uncertainty"%> Newsgroups: comp.ai.games
    From: smt@cs.monash.edu.au (Scott M Thomson)
    Subject: Uncertainty in AI
    Summary: This posting will hopefully publicise Bayesian networks, which provide
    Keywords: AI
    Date: Fri, 31 Mar 1995 04:56:58 GMT

    Have you ever played peek-a-boo with a small child? Why is it that it works? What is it that engages the child's delight? Why doesn't it work with older people?

    The game of peek-a-boo takes advantage of the limited cognitive development of the child, when we hide ourselves behind an object the child's mind no longer registers our presence. When we pop out from hiding the child's mind is delirious at the magic of our rematerialization.

    A complicated challenge for artificial intelligence since its inception has been knowledge representation in problems with uncertain domains. What a system can't see is, nonetheless, of possible importance to its reasoning mechanisms. What is unknown is also often still vital to common sense reasoning. This posting will hopefully publicise Bayesian networks, which provide a formalism for modelling and an inference mechanism for reasoning under uncertainty and initiate discussion about uncertainty problems and probabilistic reasoning in game AI's.

    Sun Tzu was a Chinese general who lived approximately 2400 years ago. His work, "The Art of War", describes the relationships between warfare, politics, economics, diplomacy, geography and astronomy. Such modern generals as Mao Zedung have used his work as a strategic reference.

    Sun Tzu's philosophy on war can be summed up in this statement, "to win one hundred victories in one hundred battles is not the acme of skill. To subdue the enemy without fighting is the supreme excellence" [11]. In computer games utilising cheats for toughening computer AI there is no skill in a computer player's victory. If a computer player can beat a human on even terms then we may start to discuss the skill of the AI designer and any human victory is that much more appreciated.

    The difficulty in representing uncertainty in any game AI is in the vast numbers of combinations of actions, strategies and defences available to each player. What we are left with is virtually impossible to represent in tables or rules applicable to more than a few circumstances. Amongst the strategies expounded by Sun Tzu are enemy knowledge, concealment and position[11].

    Enemy knowledge is our most obvious resource. Another player's units or pieces inform us about possible future actions or weaknesses by location, numbers and present vectored movement. They suggest possibilities for defensive correction, offensive action and bluffing. Sun Tzu states that we should, ``Analyse the enemy's plans so that we will know his shortcomings as well as strong points. Agitate him in order to ascertain the pattern of his movement"[11].

    Concealment may be viewed as the art of both hiding one's own strategy and divining one's opponent's. By considering our opponent's past history and placing our current situation in that context we hope to discover something about what is hidden in their mind. Conversely, our actions must be designed to convey as little as possible about the true strength or weakness of our positions.

    The position of units refers to their terrain placement in the game. Those terrains that grant defensive or offensive bonuses to computer players units should be utilised to the best advantage. In addition computer units should strike where the enemy is weakest and where the most damage can be inflicted at the least loss. Impaling units on heavily fortified positions for nominal gain is best left to real generals in real war and is not a bench mark of intelligent behaviour.

    To combine everything we need to play a good game in the face of a deceptive and hostile opponent is not a trivial task. Sun Tzu believed, "as water has no constant form, there are no constant conditions in war. One able to win the victory by modifying his tactics in accordance with the enemy situation may be called a divine!" [11]. Our aim in designing game AI's is to obtain a mechanism for moderate strategic competence, not a program with a claim to god-hood.

    Debate on the mechanism for the representation of uncertainty has settled into two basic philosophies, extensional and intensional systems [19, p3]. Extensional systems deal with uncertainty in a context free manner, treating uncertainty as a truth value attached to logic rules. Being context free they do not consider interdependencies between their variables. Intensional systems deal with uncertainty in a context sensitive manner. They try to model the interdependencies and relevance relationships of the variables in the system.

    If an extensional system has the rule,

    if A then B with some certainty factor m.
    and observes A in its database it will infer something about the state of B regardless of any other knowledge available to it. Specifically, on seeing A it would update the uncertainty of B by some function of the rule strength 'm' [].

    If an intensional system were to consider the same rule, it would interpret it as a conditional probability expression P(B|A) = m []. What we believe about B in this system is dependent on our whole view of the problem and how relevant information interacts.

    The difference between these two systems boils down to a trade-off between semantic accuracy and computational feasibility. Extensional systems are computationally efficable but semantically clumsy. Intensional systems on the otherhand were thought by some to be computationally intractable even though they are semantically clear.

    Both MYCIN (1984) and PROSPECTOR (1978) are examples of extensional systems. MUNIN (1987) is an example of an intensional system.

    MYCIN is an expert system which diagnoses bacterial infections and recommends prescriptions for their cure. It uses certainty factor calculus to manipulate generalised truth values which represent the certainty of particular formulae. The certainty of a formula is calculated as some function of the certainty of it subformulae.

    MUNIN is an expert system which diagnoses neuromuscular disorders in the upper limbs of humans. It uses a causal probabilistic network to model the conditional probabilities for the pathophysiological features of a patient[1].

    Some of the stochastic infidelity of extensional systems arises in their failure to handle predictive or abductive inference. For instance, there is a saying, ``where there's smoke there's fire". We know that fire causes smoke but it is definitely not true that smoke causes fire. How then do we derive the second from the first? Quite simply, smoke is considered evidence for fire, therefore if we see smoke we may be led to believe that there is a fire nearby.

    In an extensional approach to uncertainty it would be necessary to state the rule that smoke causes fire in order to obtain this inferencing ability. This may cause cyclic updating which leads to an over confidence in the belief of both fire and smoke, from a simple cigarette. To avoid this dilemma most extensional systems do not allow predictive inferencing. An example of predictive inferencing in a strategic game is the consideration of a player's move in reasoning about their overall strategy.

    Even those authors that support extensional systems as a means for reasoning under uncertainty acknowledge their semantic failures. "There is unfortunately a fundamental conflict between the demands of computational tractability and semantic expressiveness. The modularity of simple rule-based systems aid efficient data update procedures. However, severe evidence independence assumptions have to be made for uncertainties to be combined and propagated using strictly local calculations"[5].

    Although computationally feasible these systems lack the stochastic reliability of plausible reasoning. THE PROBLEM WITH CERTAINTY FACTORS OR TRUTH VALUES BEING ATTACHED TO FORMULAE IS THAT CERTAINTY MEASURES VISIBLE FACTS WHEREAS UNCERTAINTY IS RELATED TO WHAT IS UNSEEN, THAT WHICH IS NOT COVERED BY THE FORMULAE[].

    The semantic merits of intensional systems is also the reason for their computational complexity. In the example,

    if P(A|B) = m,
    we cannot assert anything about B even if given complete knowledge about A. The rule says only that if A is true and is the only thing that is known to be relevant to B, then the probability of B is 'm'. When we discover new information relevant to B we must revoke our previous beliefs and calculate P(B|A,K), where K is the new knowledge. The stochastic fidelity of intensional systems leaves them impotent unless they can determine the relevance relationships between the variables in their domain. It is necessary to use a formalism for articulating the conditions under which variables are considered relevant to each other, given what is already known. Using rule-based systems we quickly get bogged in the unwieldy consideration of all possible probable interactions. This leads to complex and computationally infeasible solutions.

    Bayesian networks are a mechanism for accomplishing computational efficacy with a semantically accurate intensional system. They have been used for such purposes as, sensor validation [9], medical diagnoses[1, 2], forecasting [3], text understanding [6] and naval vessel classification [7].

    The challenge is to encode the knowledge in such a way as to make the ignorable quickly identifiable and readily accessible. Bayesian networks provide a mathematically sound formalism for encoding the dependencies and independencies in a set of domain variables. A full discussion is given in texts devoted to this topic [10].

    Bayesian networks are directed acyclic graphs in which the nodes represent stochastic variables. These variables can be considered as a set of exhaustive and mutually exclusive states. The directed arcs within the structure represent probabilistic relationships between the variables. That is, their conditional dependencies and by default their conditional independencies.

    We have then, a mechanism for encoding a full joint probability distribution, graphically, as an appropriate set of marginal and conditional distributions over the variables involved. When our graphical representation is sparsely connected we require a much smaller set of probabilities than would be required to store a full joint distribution.

    Each root node within a Bayesian network has a prior probability associated with each of its states. Each other node in the network has a conditional probability matrix representing probabilities, for that variable, conditioned on the values of its parents.

    After a network has been initialised according to the prior probabilities of its root nodes and the conditional probabilities of its other variables, it is possible to instantiate variables to certain states within the network. The network, following instantiation, already has posteriors associated with each node as a result of the propagation during initialisation. Instantiation leads to a propagation of probabilities through the network to give posterior beliefs about the states of the variables represented by the graph.

    In conclusion, I am not proposing that Bayesian networks are some god given solution to all of AI's problems. It is quite plain that quite a few problems push the bounds of computational feasibility even for Bayesian networks. It is my hope that by posting this I may play some game in the future that "reasons" in a remotely intelligent way about strategies for victory. Perhaps incorporating the concepts of probabilistic reasoning into a hybrid system is a feasible solution to a competent strategic AI.

    Here is a list of some references I used in my Honours thesis. Numbers 8 and 10 are texts devoted to Bayesian Networks.

    [1]
    Andreassen, S; et al.
    "MUNIN - an Expert EMG Assistant."
    {Computer-Aided Electromyography and Expert Systems}, 1989.

    [2]
    Berguini, C; Bellazi, R; Spiegelhalter, D.
    "Bayesian Networks Applied to Therapy Monitoring.",
    {Uncertainty in Artificial Intelligence},
    Proceedings of the Seventh Conference (1991) p35.

    [3]
    Dagum, P; Galpher, A; Horvitz, E.
    "Dynamic Network Models for Forcasting."
    {Uncertainty in Artificial Intelligence},
    Proceedings of the Eighth Conference (1992) p41.

    [4]
    Findler, N.
    "Studies in Machine Cognition using th Game of Poker."
    {Communications of the ACM}, v20, April 1977, p230.

    [5]
    Fox, J; Krause, P.
    "Symbolic Decision Theory and Autonomous Systems."
    {Uncertainty in Artificial Intelligence},
    Proceedings of the Seventh Conference (1991) p103.

    [6]
    Goldman, R; Charniak, E.
    "A Probabilistic Approach to Language Understanding."
    {Tech Rep CS-90-34}, Dept Comp Sci, Brown University 1990.

    [7]
    Musman, SA; Chang, LW.
    A Study of Scaling In Bayesian Networks for Ship Classification."
    {Uncertainty in Artificial Intelligence},
    Proceedings of the Ninth Conference (1993) p32.

    [8]
    Neapolitan, RE.
    {"Probabilistic Reasoning in Expert Systems, Theory and Algorithms."}
    John Wiley and Sons, 1989.

    [9]
    Nicholson, AE; Brady, JM.
    "Sensor Validation using Dynamic Belief Networks."
    {Uncertainty in Artificial Intelligence},
    Proceedings of the Eighth Conference (1992) p207.

    [10]
    Pearl, J.
    {"Probabilistic Reasoning in Intelligent Systems, Networks of Plausible Inference."}
    Morgan Kaufmann Publishers, Inc, 1988.

    [11]
    Wordsworth Reference.
    {"Sun Tzu, The Art of War."}
    Sterling Publishing Co Inc, 1990.

    I hope this has been helpful,

    Scott Thomson

    
    ###############################################################################
    Scott M Thomson                                 \|/  ^^^  \|/
    smt@bruce.cs.monash.edu.au                      -O-[/@ @\]-O-
                                                      \ | > | /
                                                      | |___| |
                                                      \ \ U / /
                                                         ---
    "Cognito cognito ergo cognito sum cognito"
    "I think I think therfore I think I am I think?"
    (pardon the grammar)
    ###############################################################################
    
    


      Report Article
    Sign in to follow this  


    User Feedback


    There are no comments to display.



    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

  • Advertisement
  • Advertisement
  • Latest Featured Articles

  • Featured Blogs

  • Popular Now

  • Similar Content

    • By Melodrive
      Over the last 1.5yrs, I've worked with my colleagues on Melodrive, an AI music engine that enables people with limited to no musical skills to easily create highly adaptive music. The music engine uses AI to generate music from scratch, in realtime. The music smoothly transitions between different emotional states. We're planning on releasing the engine for free to indies. This means that indies can quickly get a soundtrack, which is more dynamic than anything that exists today on the market - composers included! 
      We’ve just released four Melodrive tech demos. These showcase Melodrive's AI music potential across a range of experiences from VR to music branding. You can download the demos directly from our website here: http://melodrive.com You can also sign up to become an alpha tester.
      Hope this may be of interest to you!
       
    • By Packt
      Artificial Intelligence is one of the hottest technologies currently. From work colleagues to your boss, chances are that most (yourself included) wish to create the next big AI project.
      Machine Learning and Artificial Intelligence are revolutionizing the way game developers work.
      Packt wants to learn more about what Artificial Intelligence (AI) means for people who work in the tech industry and wants to help developers understand how AI will impact them today and tomorrow.
      Take the AI Now 2018 Survey  (shouldn’t take more than 2 minutes and all responses are anonymous).
      There's a huge discount for any Packt eBook or Video once you complete it!
    • By Camillelola
      Hi Folks,
      I am learning Artificial Intelligence  and trying out my first real-life AI application. What I am trying to do is taking as an input various sentences, and then classifying the sentences into one of X number of categories based on keywords, and 'action' in the sentence.
      The keywords are, for example, Merger, Acquisition, Award, product launch etc. so in essence I am trying to detect if the sentence in question talks about a merger between two organizations, or an acquisition by an organisation, a person or an organization winning an award, or launching of a new product etc.
      To do this, I have made custom models based on the basic NLTK package model, for each keyword, and trying to improve the classification by dynamically tagging/updating the models with related keywords, synonyms etc to improve the detection capability. Also, given a set of sentences, I am presenting the user with the detected categorization and asking whether its correct or wrong, and if wrong, what is the correct categorization, and also identify the entities.
      So the object is to first classify the sentence into a category, and additionally, detect the named entities in the sentence, based on the category.
      The idea is, to be able to automatically re-train the models based on this feedback to improve its performance over time and to be able to retrain with as less manual intervention as possible. For the sake of this project, we can assume that user feedback would be accurate.
      The problem I am facing is that NLK is allowing fixed length entities while training, so, for example, a two-word award is being detected as two awards.
      What should be my approach to solve this problem? Is there a better NLU (even a commercial one) which can address this problem? It seems to me that this would be a common AI problem, and I am missing something basic. Would love you guys to have an input on this.
      Thanks & Regards
      Camillelola
    • By bvincent
      Hello everyone,
      I am doing a survey to understand better what are the pain points in terms of music composition in video games, what are the game studios / developers expectations in the future and how the industry could be improve: https://docs.google.com/forms/d/1NycMla5fhQd1fMbLy3c28alxCbhIYvkD6Fv9lqhxEJ0
      It is not a promotion of any kind, I am just interested in getting feedbacks from game developers, studios and gamers (and composers as well). 
      The answers are completely confidential and no personal information will be published, or used for any other purpose.
      Thanks for your time and help  
      Vincent 
    • By GameDev.net
      Introduction
      Backpropagation
      The backpropagation algorithm is perhaps the most widely used training algorithm for multi-layered feedforward networks. However, many people find it quite difficult to construct multilayer feedforward networks and training algorithms from scratch, whether it be because of the difficulty of the math (which can seem misleading at first glance of all the derivations) or the difficulty involved with the actual coding of the network and training algorithm. Hopefully after you have read this guide you'll walk away knowing more about the backpropagation algorithm than you ever did before. Before continuing further on in this tutorial you might want to check out James' introductory essay on neural networks.

      The Perceptron  
      Summary
      The problem with the perceptron is that it cannot express non-linear decisions. The perceptron is basically a linear threshold device which returns a certain value, 1 for example, if the dot product of the input vector and the associated weight vector plus the bias surpasses the threshold, and another value, -1 for example, if the threshold is not reached.
      When the dot product of the input vector and the associated weight vector plus the bias f(x1,x2,..,xn)=w1x1+w2x2+...wnxn+wb=threshold, is graphed in the x1,x2,...,xn coordinate plane/space one will notice that it is obviously linear. More than that however, this function separates this space into two categories. All the input vectors that will give a (f(x1,x2,..,xn)=w1x1+w2x2+...wnxn+wb) value greater than the threshold are separated into one space, and those that will not will be separated into another (see figure).

      Left: a linearly separable decision surface. Right: a non-linearly separable decision surface. The obvious problem with this model then is, what if the decision cannot be linearly separated? The failure of the perceptron to learn the XOR network and to distinguish between even and odd almost led to the demise of faith in neural network research. The solution came however, with the development of neuron models that applied a sigmoid function to the weighted sum (w1x1+w2x2+...wnxn+wb) to make the activation of the neuron non-linear, scaled and differentiable (continuous). An example of a commonly used sigmoid function is the logistic function given by o(y)=1/(1+e^(-y)), where y=w1x1+w2x2+...wnxn+wb. When these "sigmoid units" are arranged layer by layer, with each layer downstream another layer acting as the input vector etc. the multilayer feedforward network is created.
      Multilayer feedforward networks normally consist of three or four layers, there is always one input layer and one output layer and usually one hidden layer, although in some classification problems two hidden layers may be necessary, this case is rare however. The term input layer neurons are a misnomer, no sigmoid unit is applied to the value of each of these neurons. Their raw values are fed into the layer downstream the input layer (the hidden layer). Once the neurons for the hidden layer are computed, their activations are then fed downstream to the next layer, until all the activations eventually reach the output layer, in which each output layer neuron is associated with a specific classification category. In a fully connected multilayer feedforward network, each neuron in one layer is connected by a weight to every neuron in the layer downstream it. A bias is also associated with each of these weighted sums. Thus in computing the value of each neuron in the hidden and output layers one must first take the sum of the weighted sums and the bias and then apply f(sum) (the sigmoid function) to calculate the neuron's activation.

      Graph of the logistic function. Notice it scales the output to a value ranging from 0 to 1 How then does the network learn the problem at hand? By modifying the all the weights of course. If you know calculus then you might have already guessed that by taking the partial derivative of the error of the network with respect to each weight we will learn a little about the direction the error of the network is moving. In fact, if we take negative this derivative (i.e. the rate change of the error as the value of the weight increases) and then proceed to add it to the weight, the error will decrease until it reaches a local minima. This makes sense because if the derivative is positive, this tells us that the error is increasing when the weight is increasing, the obvious thing to do then is to add a negative value to the weight and vice versa if the derivative is negative. The actual derivation will be covered later. Because the taking of these partial derivatives and then applying them to each of the weights takes place starting from the output layer to hidden layer weights, then the hidden layer to input layer weights, (as it turns out this is neccessary since changing these set of weights requires that we know the partial derivatives calculated in the layer downstream) this algorithm has been called the "back propagation algorithm".
       

      A 3-layer feedforward network. Notice that in this fully connected network every neuron in the hidden and output layer is connected to every neuron in the previous layer. How is the error of the network computed? In most classification networks the output neuron that achieves the highest activation is what the network classifies the input vector to be. For example if we wanted to train our network to recognize 7x7 binary images of the numbers 0 through 9, we would expect our network to have 10 output neurons, which each output neuron corresponding to one number. Thus if the first output neuron is most activated, the network classifies the image (which had been converted to a input vector and fed into the network) as "0". For the second neuron "1", etc. In calculating the error we create a target vector consisting of the expected outputs. For example, for the image of the number 7, we would want the eigth output neuron to have an activation of 1.0 (the maximum for a sigmoid unit) and for all other output neurons to achieve an activation of 0.0. Now starting from the first output neuron calculate the squared error by squaring the difference between the target value (expected value for the output neuron) and the actual output value and end at the tenth output neuron. Take the average of all these squared errors and you have the network error. The error is squared as to make the derivative easier.
      Once the error is computed, the weights can be updated one by one. This process continues from image to image until the network is finally able to recognize all the images in the training set.
       
      Training
      Recall that training basically involves feeding training samples as input vectors through a neural network, calculating the error of the output layer, and then adjusting the weights of the network to minimize the error. Each "training epoch" involves one exposure of the network to a training sample from the training set, and adjustment of each of the weights of the network once layer by layer. Selection of training samples from the training set may be random (I would recommend this method escpecially if the training set is particularly small), or selection can simply involve going through each training sample in order.
      Training can stop when the network error dips below a particular error threshold (Up to you, a threshold of .001 squared error is good. This varies from problem to problem, in some cases you may never even get .001 squared error or less). It is important to note however that excessive training can have damaging results in such problems as pattern recognition. The network may become too adapted in learning the samples from the training set, and thus may be unable to accurately classify samples outside of the training set. For example, if we over trained a network with a training set consisting of sound samples of the words "dog" and "cog", the network may become unable to recognize the word "dog" or "cog" said by a unusual voice unfamiliar to the sound samples in the training set. When this happens we can either include these samples in the training set and retrain, or we can set a more lenient error threshold.
      These "outside" samples make up the "validation" set. This is how we assess our network's performance. We can not expect to assess network performance based solely on the success of the network in learning an isolated training set. Tests must be done to confirm that the network is also capable of classifying samples outside of the training set.
       
      Backpropagation Algorithm
      The first step is to feed the input vector through the network and compute every unit in the network. Recall that this is done by computing the weighting sum coming into the unit and then applying the sigmoid function. The 'x' vector is the activation of the previous layer.
       

      The 'w' vector denotes the weights linking the neuron unit to the previous neuron layer. The second step is to compute the squared error of the network. Recall that this is done by taking the sum of the squared error of every unit in the output layer. The target vector involved is associated with the training sample (the input vector).
       

      't' denotes a target value in the target vector, and 'o' denotes the activation of a unit in the output layer. The third step is to calculate the error term of each output unit, indicated below as 'delta'.
       

      The error term is related to the partial derivative of each weight with respect to the network error. The fourth step is to calculate the error term of each of the hidden units.
       

      The hidden unit error term depends on the error terms calculated for the output units. The fifth step is to compute the weight deltas. 'Eta' here is the learning rate. A low learning rate can ensure more stable convergence. A high learning rate can speed up convergence in some cases.
       

      'x' denotes the unit that's connected to the unit downstream by the weight 'w' The final step is to add the weight deltas to each of the weights. I prefer adjusting the weights one layer at a time. This method involves recomputing the network error before the next weight layer error terms are computed.
       

      Once finished, proceed back to step 1.









  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!