I won’t have time to post any real work here until the end of March, unfortunately. This entry is purely speculative fun concerning functionality I haven’t yet worked on. In particular, I’ve been thinking lately about tree search algorithms and I wondered if anyone here had any good ideas/references.

In particular, I’ve been worrying about what I’ll call “the Kevin Bacon problem.” You’ve probably heard of it, or some variant: how many degrees of separation is some actor/actress/film from Kevin Bacon? The following example (since I’m no film buff myself) is taken from wikipedia:

Elvis Presley was in the film “Change of Habit” with Edward Asner.
Edward Asnder was in “JFK” with Kevin Bacon.
Therefore Elvis has two degrees of separation from Kevin Bacon.

I want to write a set of algorithms to search my knowledge base for how inter-connected two subjects or parse trees are. As I’ve described before, the knowledge base consists of parse trees where every noun is it’s own “node”. So the direct object of a sentence is labeled as an id pointing to a sentence in which the direct object is the subject. For example, the sentence “The dog ate a big bone.” would be stored as

subject: dog
verb: eat
confidence: #
object: id pointing to…

subject: bone
adjectives: big
verb: is
confidence: #

All phrases and clauses in the sentence also point to their own “nodes”. Starting from two id’s, I want to search for all the id chains that connect them. I think this type of search will be an important intermediary step in later logic operations. I’ve been doing some googling of tree searches and in particular depth-first search techniques.

The algorithm should recognize that searching id’s with low confidence values isn’t as useful as searching high confidence branches. And I’d like it to take advantage of the fact that the content of “wrong” id’s can indicate how close it is to the right one, using contextual clues. This can then influence “how deep” a branch is searched.

To do the latter, perhaps I need a database logging how closely id pairs (or subject pairs) are related. The database can be formed by randomly crawling the knowledge base during down time and recording connections. And added to whenever the search algorithm runs.

Anyway, before I ramble down any more tangents, I’ll throw it to you guys. Any advice for tree search algorithms? Especially for a knowledge base that has strongly connected components and trees with potentially many cross edges and back edges?

The tree search algorithms that I am using at the moment wont be of much use for you, I’m afraid, since I’ve implemented them all in the neural network, which is a bit different.
In a more traditional language, I would walk the tree nodes (probably from root till leaves since you wont have access to the leaves?), perhaps using an extra stack to go back to previous nodes when a sub branch is done. An extra list to keep track of which branches have already been proceed could also be useful.
I’d also split up the function in a general tree walk part and the comparison function (pretty logic I guess).
Other than that, It’s probably pretty code specific how you want to do this. I’m not certain how your tree is implemented, if it is your own flavor, that’s the end of the story, if you are using some that’s provided with python (was it?), perhaps they have implemented a search routine.

Everything is implemented as python dictionaries. But since I’m still in the “design” phase, I want to address how I search the knowledge base before committing to a format. Which is why I’m worrying about searching algorithms so early in the game.

In some ways what you describe reminds me of chess algorithms. The potential move list is pruned based on quality scores.

http://en.wikipedia.org/wiki/Alpha-beta_pruning

Excellent work CR.

One interesting way that your parse trees differ from mine is that you have links from nodes of one parse tree to other parse trees, where I have them altogether.

That is interesting because I remember pondering that one for a good while.  I decided to keep each tree together.  Linking is probably just as good of an idea though.

Question - for long term storage of facts that you teach your bot, will they be stored as NL statements, or converted and INSERT db statements, or perhaps both?  I think I have chosen to store as trees.  Perhaps (sometimes) depending on the information itself, it could also be sql INSERT-ed, but in ALL cases it will store both the exact user input string and the chosen parse tree.

At the moment the only way in which knowledge is stored is as linked parse trees. But since each parse tree is built from an NL sentence in the first place (including dependent clauses, which are first converted to independent sentences), it might be worthwhile to throw in the actual NL string as well. Perhaps both the independent sentence without “conditions” (phrases) attached and the sentence with conditions thrown in (the original sentence). Would likely speed up the process of NL output. Although I do want to build tools that go from the knowledge base structure to NL sentence structure. (I have one crude algorithm, but it’s just used to test the kb.)

The reason I decided on linking is so that whenever a topic comes up in conversation, everything the bot knows related to that topic will be located in one spot. Crawling along links from that topic can help steer the conversation or be used to deduce appropriate responses/questions.

Man, I can’t wait to get back to work on this stuff. Real life has an awful sense of timing. April can’t come soon enough!

Merlin, the question would be: how does the bot determine a quality score? Based on user feedback? How does it judge whether the feedback was positive? Maybe if the user continued with the subject or deviated from it. Responses like “huh?”, “where did that come from?”, “I don’t get it” etc. would deviate from the subject at hand and be taken as “negative” feedback. (Of course, if it was merely a natural transition in subject area, this shouldn’t count against the bot. Walking that line will be the “art” of it, I guess.)

Interesting stuff, guys. Thanks for your replies.

C R Hunt - Mar 8, 2011:

Man, I can’t wait to get back to work on this stuff. Real life has an awful sense of timing. April can’t come soon enough!

You said it !!  The next holidays I get is Easter weekend, I’m going to just hammer on the code during that time.

One major issue I am facing is lists of nouns in the subject (in the initial fact input) and also in the question tree.  Even something as simple as phone numbers is quite a challenge.

F: bob’s phone number is 111-2222
q: what’s bob’s number

here we omitted the modifying of ‘number’ with ‘phone’  But should say ‘Did you mean *phone* number?’

F: bob, george and sally’s number is 111-2222
Q: what’s george’s phone number

here more than one noun comprise the subject in the fact, but question has only one of them, and this time the ‘phone’ is modifying ‘number’ in question but not in original fact.  Here bot would have to say ‘Not sure if it is his *phone* number, but you told me his “number” was 111-222

F: bob’s phone number is 111-2222
Q: what’s sammy’s and bob’s phone numbers?

here we deal with plural form of number (simply with +‘s’ suffix, but in other cases may be different word (mice/mouse)
So here initial fact had one subject noun, but question had more than one.

F: bob’s work phone number is 111-2222, extension 5211
Q: what’s bob’s phone ?

here the question doesn’t have ‘number’ at all, just ‘phone’ (which was only the modifier in original fact).

Bottom line—even a bot that can handle store and retrieve of just phone numbers will be fairly sophisticated !!  That is, if it has extreme flexibly.    One could easy drop a bot from a Turing test within seconds , even if conversation is limited to telephone numbers!!

F: bob’s work phone is 111-2222
Q: what’s bob’s telephone # ?

F: jack & jill’s phone number is 111-222
Q: what is jack and ben’s number?

only 1 match, and it is ‘and’ .. bot response ‘not sure of ben’s, but jack’s *phone* number is 111-222”

F: bob’s phone number was 111-2222
Q: what’s bob’s phone number

F: bob’s phone number was the same as the one I had when I was in college
F: my number during my college years was 111-2222
Q: what was bob’s phone number?

ok, the last one is silly, but you get the idea.

talking about ‘true’ , ‘strong’ ai, I think we need to first master telephone numbers LOL

C R Hunt - Mar 8, 2011:

Merlin, the question would be: how does the bot determine a quality score? Based on user feedback? How does it judge whether the feedback was positive? Maybe if the user continued with the subject or deviated from it. Responses like “huh?”, “where did that come from?”, “I don’t get it” etc. would deviate from the subject at hand and be taken as “negative” feedback. (Of course, if it was merely a natural transition in subject area, this shouldn’t count against the bot. Walking that line will be the “art” of it, I guess.)

Interesting stuff, guys. Thanks for your replies.

The algorithm should recognize that searching id’s with low confidence values isn’t as useful as searching high confidence branches.

As a first pass I would use your confidence score as the “quality score”. In chess, every piece (word?) has a value. But the position on the board also has a value, as does the goals of the player (checkmating the opponent or building defenses for example). You might sacrifice a piece to accomplish your goal. The quality score might be modified by the current state, or even the reliability/trustworthiness of the input.

The trees used for games, like chess games, aren’t they balanced, that is, sorted upon weight, to provide fast searching? It doubt that this works on a non sorted parse tree.

Because of the possible diversity of moves, trees are not stored, they are created on the fly. The exception to this is the opening “book” or list of know openings which is easily stored. Also, the “end game” when there are possibly only a few pieces left on the board can also be stored.

In the middle part of the game, the number of possible positions and moves from those positions makes it impractical to save all the positions. (See the wheat and the chessboard problem: http://en.wikipedia.org/wiki/Wheat_and_chessboard_problem)

Each “ply” http://en.wikipedia.org/wiki/Ply_(game_theory) or move must account for the player’s move and the opponents best possible response. High level human and computer players plot strategy multiple move in advance. Since any piece could be moved, each creating different strengths and weaknesses, the ability for a program to discard unproductive lines of attack early in the calculation/analysis process greatly improves the “depth” that the computer can reach in a given amount of time.

Hello, CR,

Let me say right off that I am very impressed with the level of detail you are attempting. In the past, I attempted to write parsing programs along similar lines (assuming I am understanding you correctly), i.e., specifying the possible parts-of-speech of each word in a sentence and then applying grammar rules to reduce these possibilities. Of course, as you have no doubt learned, there are some constructions which simply can’t be resolved in this fashion. English is, unfortunately, fubar (which is what makes NLP so much “fun”).

This time around, I decided to focus more on the chat side of the equation with STU. To that end, my approach is to examine input for easily identifiable elements both semantically and grammatically. For example, at level 1, after dividing the input into sentences, I check whether each begins with a relative pronoun like “What”, “Where”, etc. (specific questions); a helping verb like “Do”, “Can”, etc. (general questions); or neither (statements). That way, even if I can’t get any more out of the input, STU can still appear to say something vaguely sensible such as “Interesting question.” (Obviously, I would go for something less lame than that!)

At level 2, I might look for common keywords, like whether a statement starts with “I” or “you” for example. Then, even if I get no further, I at least know the sentence was about STU or about the user.

In other words, I go as far with each sentence as possible in order to feel confident that STU won’t screw up grammatically or semantically in his response. For example, transforms like “i” to “you” switches are only applied to output if they can be generated by rules that I feel are ironclad. If such rules don’t apply, STU won’t use the transform to avoid the risk of garbage output.

Anyway, your idea of forming a database based on input is very interesting, CR. I also spent some time with this idea in the past, centered around the possibility of forming said database WITHOUT referencing any knowledge-base. In other words, developing concepts and definitions for words based entirely on how they are used vis-a-vis other words.

Eulalio

Eulalio Paul Cane - May 7, 2011:

Let me say right off that I am very impressed with the level of detail you are attempting.

Thanks

Eulalio Paul Cane - May 7, 2011:

In the past, I attempted to write parsing programs along similar lines (assuming I am understanding you correctly), i.e., specifying the possible parts-of-speech of each word in a sentence and then applying grammar rules to reduce these possibilities. Of course, as you have no doubt learned, there are some constructions which simply can’t be resolved in this fashion. English is, unfortunately, fubar (which is what makes NLP so much “fun”).

True. This is where “context” is critical. The hope is that by drawing from a knowledge base, the bot can distinguish between two grammatically correct parses.

Eulalio Paul Cane - May 7, 2011:

[...] my approach is to examine input for easily identifiable elements both semantically and grammatically. [...] That way, even if I can’t get any more out of the input, STU can still appear to say something vaguely sensible such as “Interesting question.”

Definitely a viable chatbot needs to be flexible and contribute to a conversation even if it fails to resolve a correct parse of the input. When ALEX gets to this stage (not in the immediate future), I hope to be able to incorporate the NLP tools as one of several resources the chatbot can draw on to formulate a reply. Sort of the “Watson approach”, if you will. Get many algorithms all attacking the same input in parallel and then let them fight it out to determine the best response.

Not an easy task. Still much NLP work to do before I worry about it.

Eulalio Paul Cane - May 7, 2011:

Anyway, your idea of forming a database based on input is very interesting, CR. I also spent some time with this idea in the past, centered around the possibility of forming said database WITHOUT referencing any knowledge-base. In other words, developing concepts and definitions for words based entirely on how they are used vis-a-vis other words.

When I first started this project, I was interested in the problem of using natural language input to facilitate dictionary building. What a nightmare. I tabled that (probably permanently) in favor of attacking contextual grammar. Enjoying the challenge so far.

C R Hunt - Feb 16, 2011:

Step 3: Complex sentence splitting.

I absolutely loathe conjunctions. I may build methods for handling them directly in the future, but for now, ALEX has a sophisticated way to use pattern matching to map any sentence containing conjunctions (what I call a “complex sentence”) to one or more simple sentences without conjunctions. Special characters are used to indicate the relationship that the simple sentences have with each other. I’ll go more into this later.

Hi, CR,

I’ve just been getting into the whole conjunction annoyance thing in the last few days and remembered you had talked about splitting sentences into simpler ones. I was wondering if you could comment on your approach to this task.

Thanks,

Eulalio

Eulalio Paul Cane - May 7, 2011:

In the past, I attempted to write parsing programs along similar lines (assuming I am understanding you correctly), i.e., specifying the possible parts-of-speech of each word in a sentence and then applying grammar rules to reduce these possibilities. Of course, as you have no doubt learned, there are some constructions which simply can’t be resolved in this fashion. English is, unfortunately, fubar (which is what makes NLP so much “fun”).

True. This is where “context” is critical. The hope is that by drawing from a knowledge base, the bot can distinguish between two grammatically correct parses.

Why the double quotes around the word context?  Not only context, but more importantly, knowledge of the world, common sense knowledge should have a high priority as well.  Think of the elephant wearing pajamas example.  For the most part, elephants don’t wear pajamas thus “I shot an elephant in my pajamas” probably means I was wearing pajamas when I shot the elephant, and not that I shot an elephant which was wearing pajamas.  But yes, context also does matter, perhaps the chatbot is talking to a child about some children TV show where an elephant is wearing pajamas, ok, then it should consider that.  But in the absence of that specific case, it should default to making the safe assumption that elephants don’t wear pajamas.  Humans reason, and use language in a for-the-most-part way (unless it is overridden by the context).