MegaHAL

MegaHAL

Hutchens, Jason L

 

In 1996 the primary author entered the Loebner contest with an ELIZA variant named HeX, which was written during his spare time in under a month. Apart from the lure of the prize money, a major motivation for the entry was a desire to illustrate the shortcomings of the contest (Hutchens, 1996). A considerably more powerful program, SEPO, was entered the following year, where it was placed second. We believe this to be indicative of a gradual improvement in the quality of the contestants.

The program submitted to this year's contest, MegaHAL, uses a significantly different method of simulating conversation than either HeX or SEPO, and we dedicate the remainder of this paper to describing its workings.

1. Markov Modelling

MegaHAL is able to construct a model of language based on the evidence it encounters while conversing with the user. To begin with, the input received from the user is parsed into an alternating sequence of words and non-words, where a word is a series of alphanumeric characters and a non-word is a series of other characters. This is done to ensure not only that new words are learned, but that the separators between them are learned as well. If the user has a habit of putting a double space after a full stop, for instance, MegaHAL will do just the same.

The resulting string of symbols[2] is used to train two 4^th-order Markov models (Jelinek, 1986). One of these models can predict which symbol will following any sequence of four symbols, while the other can predict which symbol will precede any such sequence. Markov models express their predictions as a probability distribution over all known symbols, and are therefore capable of choosing likely words over unlikely ones. Models of order 4 were chosen to ensure that the prediction is based on two words; this has been found necessary to produce output resembling natural language (Hutchens, 1994).

2. Generating Candidate Replies

Using a Markov model to generate replies is easy; Shannon was doing much the same thing by flipping through books back in 1949 (Shannon, 1949). However, such replies will often be nonsensical, and will bear no relationship to the user's input.

MegaHAL therefore attempts to generate suitable replies by basing them on one or more keywords from the user's input. This explains why two Markov models are necessary; the first model generates a sentence from the keyword on, while the second model generates the remainder of the sentence, from the keyword back to the beginning.

Keywords are obtained from the users input. Frequently occurring words, such as "the", "and" and "what", are discarded, as their presence in the input does not mean they need to be present in the output. The remaining words are transformed if necessary---"my" becomes "your" and "why" becomes "because", for example. What remains is used to seed the output.

3. Selecting a Reply

MegaHAL is able to generate many hundreds of candidate replies per second, each of which contain at least one keyword. Once a small time period has elapsed, the program must display a reply to the user. A method is needed for selecting a suitable reply out of the hundreds of candidates.

I(w|s) = -log2P(w|s)

MegaHAL chooses the reply which assigns the keywords the highest information. The information of a word is defined in Equation~\ref{Information} as the surprise it causes the Markov model. Hence the most surprising reply is selected, which helps to guarantee its originality. Note that P(w|s) is the probability of word w following the symbol sequence s, according to the Markov model.

The algorithm for MegaHAL proceeds as follows:

1. Read the user's input, and segment it into an alternating sequence of words and non-words.
2. From this sequence, find an array of keywords and use it to generate many candidate replies.
3. Display the reply with the highest information to the user.
4. Use the user's input to update the Markov models, so that MegaHAL can learn from what the user types.

This sequence of steps is repeated indefinitely, which allows the program to learn new words, and sequences of words, as it converses with the user.

4. Training MegaHAL

When MegaHAL is started it has no knowledge of language, and is unable to give a reply at all---the program needs to be trained using a source of text to ensure that it does not reveal its identity prematurely. A large corpus of training data was created for this purpose.

The training data is made up of various texts:

• Hand-crafted sentences designed in order to create a personality for MegaHAL, including sentences containing a false name, age and occupation.
• Encyclopaedic information taken from the Web, on topics such as geography, music, sports, movies and history.
• A selection of sentences picked from transcripts of previous Loebner contests.
• Lines of dialogue taken from scripts for movies and television shows.
• Lists of popular quotations.
• A small amount of text in languages other than English.

When MegaHAL is trained using this data, it is able to respond to questions on a variety of topics. It is hoped that the program will also learn new topics from the judges, although this remains to be seen.

5. Online Experimentation

MegaHAL has been available on the Web since early in 1997, and hundreds of users converse with it every day. It is an interesting fact that one never tires of reading transcripts of conversation, due to MegaHAL's ability to respond with original replies.

Many users are often offended by the things MegaHAL says, and some believe that they have been personally insulted. One user, named Forrest, was quite incensed when the program began quoting parts of the Forrest Gump screenplay back at him. That a computer program can cause such an emotional response in a human being is interesting, although it may say more about the human being than it does about the program.

Users are often impressed with MegaHAL's ability to learn. One user was annoyed that the program had learned more about his personal life than he would care it to know, while another stated that MegaHAL would eventually grow into a person of average intellect (he attributed this bold claim to the law of averages). One user, experienced working with people in psychotic crises, likened talking to MegaHAL with talking to a psychotic.

Users have succesfully taught the program to respond to sentences in French, Spanish, Greek, German, Italian, Latin, Jananese and Hebrew, amongst others. A clergyman spent hours teaching MegaHAL about the love of Jesus, only to constantly receive blasphemous responses.

The reaction of Web user's to the program has been surprising, and is pretty much what Weizenbaum experiences with ELIZA. MegaHAL generates gibberish mostly, but occasionally, by pure coincidence, it will come out with an appropriate response. It is these occasions that stick in the mind, and give cause for over-zealous claims of computational intelligence.

6. Example Interaction

As an example of MegaHAL at its best, we give here a few extracts from a conversation which took place, over a period of three hours in mid 1997, between MegaHAL and an anonymous Web user.

To begin with, the user was able to successfully teach the program some basic facts:

User: Roentgen discovered the X-rays. MegaHAL: THE NOBEL PRIZE FOR PHYSICS IN 1900 WAS WON BY ROENTGEN. User: Who discovered the X-rays? MegaHAL: ROENTGEN DISCOVERED THE X-RAYS.

He then discovered that the program is an expert an being nonsensical. Even so, MegaHAL was still able to give some appropriate responses, due to the keyword mechanism for generating replies:

MegaHAL: WHEN WE BEGIN TO RESOLVE SOME OF MY THUMBS, SOMETHING WICKED THIS WAY COMES User: what is the meaning of your last assertion ? MegaHAL: HAVE YOU LEARNED SINCE WE LAST SPOKE? User: I've learned I'm not experienced enough to modelize your brain system MegaHAL: YOU'VE FINALLY CONFUSED ME. User: I've learned nothing .MegaHAL: HAVE YOU LEARNED ANYTHING ABOUT INSANITY? User: are you stupid MegaHAL: I AM NOT STUPID! REALLY!

Finally, the user discovered that the program could respond in other languages:

User: Tu parles francais? MegaHAL: I GUESS SO. PARLEZ-VOUS FRANCAIS? User: L'amour est une passion humaine. MegaHAL: LA LANGIDOCE EST UNE PETITE JEUNNE FILLE

In general MegaHAL's conversations are not as successful as this. Most users are satisfied with typing in rude words to see how the program responds.

 

 

 

※ 마코프성질은 과거와 현재에 관한 정보가 주어질 때 미래에 관한 조건부 분포는 현재의 정보에만 의존하며 과거의 정보와는 무관하다.

마코프전개는 RBD(Reliability Block Diagram)를 사용하여 모형화시킬수 없는 잠재된 고장, 수리수단의 다양화, 여분(redundant)요소의 고장때 스트레스를 첨가하는 것같은 기술을 간과하는 몇몇 어려운 요소 등을 다룰수 있다는 장점이 있다.

 모형들의 가정이 많다면 당연히 수학적인 측면은 더 복잡해진다. 하지만 컴퓨터로 인해 이러한 문제는 해결이 되었다.

마코프전개에서 미래상황은 단지 과거가 아닌 현재 상태에 의해 결정된다.

마코프전개의 좋은 예는 날씨이다.

내일의 날씨는 어제의 날씨와는 독립적으로 대부분 오늘의 날씨와 비슷할 것이다. 또 이런 날씨가 얼마나 지속될 것인가?

마코프전개는 이산(discrete)이나 연속(continuous)이 있을 수 있다