Lựa chọn

 Danh mục

 Chi tiết tài nguyên
Simple Parrot Turing Algorithm in C#
   Đăng bởi: host | Ngày : 01:43 05/12/09 | Xem: 924 |        
Simple Parrot Turing Algorithm in C#
Introduction
I am extremely interested in machine learning. However, implementing neural nets and Bayesian graphs etc., can take a long time, and are subject to domain definition problems. While they are the cutting edge, sometimes it is nice to sit back, relax, and do something no rational computer scientist would do: implement a worthless algorithm.
Actually, the algorithm is not worthless. Designing the code and running through it reveals weaknesses in the approach that makes it easier to conceptualize more advanced methods and accurately define the domain.
This algorithm will break typed messages up into words, analyze the frequency of words, and then generate a random response based on the frequency of words, the minimum sentence size, and the maximum sentence size. Once implemented, it is a fun algorithm to play with (implement an IParticipant for human interaction) as it sometimes makes some interesting combinations of words.
A comment about the code:
I do not like attaching Zip files full of code unless absolutely necessary. Half of the fun of something like this is in the implementation. It also helps with the understanding. Besides, I hate having to download a Zip so I can find the answer I want. If I pose a question in this tutorial and give an answer, it is in the tutorial without the need for a download, unzip, and grep!
Background
If you are unfamiliar with a Turing test, please visit: The Turing Test. Other interesting Turing problems are CAPTCHA's which are fun to implement as well. In fact, my next tutorial may be on a captcha.
Using the code
Below is some unexplained code that should be obvious but are probably required for understanding the other aspects of this tutorial. For reasons I don't understand, I have IParticpant calling Conversation.addParticipant(IParticipant). There is probably a better design pattern implementation, I just wasn't spending time with design issues.
Collapse
publicstruct Message{
    public IParticipant speaker;
    public Conversation conversation;
    public DateTime timeStamp;
    publicstring message;
    /**
     * <summary>
     * Provides a tidy string rep of this object
     * </summary>
     */
    publicoverridestring ToString() {
        return timeStamp.ToShortTimeString() +
           " " + speaker.getName() + ": " + message;
    }//end ToString
    /**
     * <summary />
     */
    public Message(IParticipant speaker, Conversation
           conversation, string message){
        this.timeStamp = System.DateTime.Now;
        this.speaker = speaker;
        this.conversation = conversation ;
        this.message = message;
    }//end Message
}//end Class Message
 
publicinterface IParticipant{
    string getName();
    void newMessage(Message message);
    void joinConversation(Conversation conversation);
}//end IParticipant
 
publicclass Conversation{
    List<IParticipant> participants = new List<IParticipant>();
    //Allows the message log to be saved
    //List<Message> messages = new List<Message>();
    /**
     * <summary>
     * This method will allow a message to be "spoken"
     * </summary>
     */
    publicvoid speak(Message message){
        //messages.Add(message);
        foreach(IParticipant p in participants){
            //Notify all particpants
            //of a new message in this conversation
            p.newMessage(message);
        }//end foreach
    }//end speak
    /**
     * <summary>
     * This method will add a participant to the conversation
     * </summary>
     */
    publicvoid addParticipant(IParticipant participant){
        if(!participants.Contains(participant)){
            participants.Add(participant);
        }
    }//end addParticipant
}//end Conversation
Below is the class that implements the parroting logic. This code is easy and straightforward in most cases, so I will not burden the reader with silly things like a lot of explanations.
Collapse
/**
 * <summary>
 * This class holds word frequencies
 * </summary>
 */
publicclass Word : IComparer<Word>{
    privatestring word;
    privateint frequency = 0;
    publicevent Action<Word> FrequencyChanged;
    /**
    * <summary>
     * This method will return the word
     * </summary>
     */
    publicstring getWord(){
        return word;
    }//end getWord
    /**
     * <summary>
     * This method will return the frequency
     * </summary>
     */
    publicint getFrequency(){
        return frequency;
    }//end getFrequency
    /**
     * <summary>
     * This method will increment the frequency
     * </summary>
     */
    publicvoid incrementFrequency(){
        frequency++;
        onFrequencyChanged();
    }//end incrementFrequency
    /**
     * <summary>
     * This method is called when the frequency is changed
     * </summary>
     */
    protectedvoid onFrequencyChanged(){
        if(FrequencyChanged != null){
            FrequencyChanged(this);
        }//end if
    }//end OnFrequencyChanged
    /**
     * <summary>
     * Compares words by frequncy
     * </summary>
     */
    publicint Compare(Word x, Word y) {
        return x.getFrequency().CompareTo(y.getFrequency());
    }//end Compare
    /**
     * <summary />
     */
    public Word(string word){
        this.frequency = 1;
        this.word = word;
    }//end word
}//end word
/**
 * <summary>
 * The bob algorithm is a trivial turing test
 * </summary>
 */
publicclass ParrotAlgorithm : IParticipant{
    privatestaticint instanceCount = 0;
    privatestring name =
            "Parrot #" + instanceCount.ToString();
    private Conversation conversation = null;
    private List<Word> list = new List<Word>();
    private Dictionary<string, Word> hash =
            new Dictionary<string,Word>();
 
    privateint minMessageSize = 3;
    privateint maxMessageSize = 10;
    private Random random = new Random();
    privatedouble chaos = .2d;
    privateint wordCount = 0;
    /**
     * <summary>
     * This method will return the name of the speaker
     * </summary>
     */
    publicstring getName(){
        return name;
    }//end getName
    /**
     * <summary>
     * This method will add a word
     * </summary>
     */
    privatevoid addWord(string wordString){
        wordCount++;
        Word word = null;
        if(!hash.ContainsKey(wordString)) {
            word = new Word(wordString);
            hash.Add(wordString, word);
            list.Add(word);
            word.FrequencyChanged +=
              new Action<Word>(word_FrequencyChanged);
        }//end if
        else{
            word = hash[wordString];
            word.incrementFrequency();
        }
    }//end add word
    /**
     * <summary>
     * This method is executed when the word frequency is updated
     * </summary>
     */
    publicvoid word_FrequencyChanged(Word obj){
        /*
         * Resort using quick sort
         * MSDN:
         * On average, this method is an O(n log n) operation,
         * where n is Count; in the worst case
         * it is an O(n ^ 2) operation.
         */
        list.Sort(obj);
    }//end word
    /**
     * <summary>
     * This method will generate a repsonse
     * </summary>
     */
    privatevoid respond(){
        //Only respond if necessary
        int wordLength = (int)(minMessageSize +
          (random.NextDouble() *
          (maxMessageSize - minMessageSize)));
        double runningTotal = 0.0d;
        string message = "";
        for(int i=0;i<wordLength;i++){
            if(random.NextDouble() < chaos){
                //Just pick a random word
                message += list[(int)(random.NextDouble()
                           * list.Count)].getWord() + " ";
            }
            else{
                double requiredOdds = random.NextDouble();
                //Pick a word based on frequency
                runningTotal = 0.0d;
                foreach(Word w in list){
                    runningTotal += ((double)w.getFrequency()/
                                     (double)wordCount);
                    if(runningTotal > requiredOdds){
                        message += w.getWord() + " ";
                        break;
                    }
                }//end foreach
            }
        }//end for
        if(message.Length > 0){
            Message mm = new Message(this,
                         this.conversation, message);
            conversation.speak(mm);
        }
    }//end respond
    /**
     * <summary>
     * This method receive a new message
     * </summary>
     * <remarks>
     * ParrotAlgorithm is a stupid parrot.
     * He repeats what he hears most often
     * </remarks>
     */
    publicvoid newMessage(Message message){
        //ignore own messages
        if(message.speaker != this){
            string[] tokens =
              message.message.Split(newchar[]{' '});
            if(tokens.Length > maxMessageSize)
                maxMessageSize = tokens.Length;
            foreach(string s in tokens){
                addWord(s);
            }//end foreach
            respond();
        }//end if
    }//end new Message
    /**
     * <summary>
     * This method will instruct this
     * class to join a conversation
     * </summary>
     */
    publicvoid joinConversation(Conversation conversation){
        this.conversation = conversation;
        conversation.addParticipant(this);
    }//end joinConversation
    /**
     * <summary />
     */
    public ParrotAlgorithm() {
        instanceCount++;
    }//end Constructor
}//end ParrotAlgorithm
The first bit of explanation is the Word class. What is it for, why did you do that? It wraps words or tokens in a message, and stores associated information such as frequency. The event FrequencyChanged is called whenever the frequency is updated, to allow the list to be resorted. This is probably not the most efficient method. Adding all of the new words and then sorting the list is, possibly, more efficient.
privatevoid addWord(string wordString){
    wordCount++;
    Word word = null;
    if(!hash.ContainsKey(wordString)) {
        word = new Word(wordString);
        hash.Add(wordString, word);
        list.Add(word);
        word.FrequencyChanged +=
          new Action<Word>(word_FrequencyChanged);
    }//end if
    else{
        word = hash[wordString];
        word.incrementFrequency();
    }
}//end add word
The above code will add a word to the memory banks. A dictionary object, which I call hash, is used to update the frequency for words that have already been used and stored. The list is a List<Word> object (.NET 2.0 Generics) that stores the words in sorted order. This is important for getting the random words later.
Collapse
/**
 * <summary>
 * This method will generate a repsonse
 * </summary>
 */
privatevoid respond(){
    //Only respond if necessary
    int wordLength = (int)(minMessageSize +
        (random.NextDouble() * (maxMessageSize - minMessageSize)));
    double runningTotal = 0.0d;
    string message = "";
    for(int i=0;i<wordLength;i++){
        if(random.NextDouble() < chaos){
            //Just pick a random word
            message += list[(int)(random.NextDouble() *
                       list.Count)].getWord() + " ";
        }
        else{
            double requiredOdds = random.NextDouble();
            //Pick a word based on frequency
            runningTotal = 0.0d;
            foreach(Word w in list){
                runningTotal += ((double)w.getFrequency()/
                                 (double)wordCount);
                if(runningTotal > requiredOdds){
                    message += w.getWord() + " ";
                    break;
                }
            }//end foreach
        }
    }//end for
    if(message.Length > 0){
        Message mm = new Message(this, this.conversation, message);
        conversation.speak(mm);
    }
}//end respond
This method contains all of the brains behind the parrot.
int wordLength = (int)(minMessageSize +
   (random.NextDouble() * (maxMessageSize - minMessageSize)));
Randomly select the length of the response. This code guarantees a minimum sentence size, and won't let the parrot respond with enormous sentences unless its peers do so as well.
if(random.NextDouble() < chaos){
Randomness is crucial. This is what really makes things interesting. There just has to be mutation. Eliminate this code or change the chaos value to see how it affects the results.
runningTotal += ((double)w.getFrequency()/(double)wordCount);
This function normalizes the value of the frequencies, making the sum of all frequencies == 1 (maybe). Therefore, you can loop, starting with the lowest frequency, and add up the normals to compare to the random number you desire. To be honest, I have not proved this statement, but it seems intuitively correct. Someone with a stats book and free-time is welcome to prove or disprove it for me. For the interim, it works for me.
 

 

Bình luận

Thêm nhận xét