4

I want to be able to find sentences with the same meaning. I have a query sentence, and a long list of millions of other sentences. Sentences are words, or a special type of word called a symbol which is just a type of word symbolizing some object being talked about.

For example, my query sentence is:

Example: add (x) to (y) giving (z)

There may be a list of sentences already existing in my database such as: 1. the sum of (x) and (y) is (z) 2. (x) plus (y) equals (z) 3. (x) multiplied by (y) does not equal (z) 4. (z) is the sum of (x) and (y)

The example should match the sentences in my database 1, 2, 4 but not 3. Also there should be some weight for the sentence matching.

Its not just math sentences, its any sentence which can be compared to any other sentence based upon the meaning of the words. I need some way to have a comparison between a sentence and many other sentences to find the ones with the closes relative meaning. I.e. mapping between sentences based upon their meaning.

Thanks! (the tag is language-design as I couldn't create any new tag)

Phil
  • 46,436
  • 33
  • 110
  • 175

4 Answers4

7

First off: what you're trying to solve is a very hard problem. Depending on what's in your dataset, it may be AI-complete.

You'll need your program to know or learn that add, plus and sum refer to the same concept, while multiplies is a different concept. You may be able to do this by measuring distance between the words' synsets in WordNet/FrameNet, though your distance calculation will have to be quite refined if you don't want to find multiplies. Otherwise, you may want to manually establish some word-concept mappings (such as {'add' : 'addition', 'plus' : 'addition', 'sum' : 'addition', 'times' : 'multiplication'}).

If you want full sentence semantics, you will in addition have to parse the sentences and derive the meaning from the parse trees/dependency graphs. The Stanford parser is a popular choice for parsing.

You can also find inspiration for this problem in Question Answering research. There, a common approach is to parse sentences, then store fragments of the parse tree in an index and search for them by common search engines techniques (e.g. tf-idf, as implemented in Lucene). That will also give you a score for each sentence.

Fred Foo
  • 355,277
  • 75
  • 744
  • 836
  • I guess that starting out with a set of frame sentences and then trying to match the sentences to a set of frame sentences is the way to go then. Since addition can be a simple frame sentence, but there are many ways to express addition in the English language. I'm looking at the projects you referenced. – Phil May 07 '11 at 08:04
  • @Phil: be sure to look at the Question Answering literature. I think what these people are doing is most similar to what you want, although adapting their ideas will not be a free lunch. – Fred Foo May 09 '11 at 07:53
1

Not that easy ^^ You should use a stopword filter first, to get non-information-bearing words out of it. Here are some good ones

Then you wanna handle synonyms. Thats actually a really complex theme, cause you need some kind of word sense disambiguation to do it. And most state of the art methods are just a little bit better then the easiest solution. That would be, that you take the most used meaning of a word. That you can do with WordNet. You can get synsets for a word, where all synonyms are in it. Then you can generalize that word (its called a hyperonym) and take the most used meaning and replace the search term with it.

Just to say it, handling synonyms is pretty hard in NLP. If you just wanna handle different wordforms like add and adding for example, you could use a stemmer, but no stemmer would help you to get from add to sum (wsd is the only way there)

And then you have different word orderings in your sentences, which shouldnt be ignored aswell, if you want exact answers (x+y=z is different from x+z=y). So you need word dependencies aswell, so you can see which words depend on each other. The Stanford Parser is actually the best for that task if you wanna use english.

Perhaps you should just get nouns and verbs out of a sentence and make all the preprocessing on them and ask for the dependencies in your search index. A dependency would look like

x (sum, y)
y (sum, x)
sum (x, y)

which you could use for ur search

So you need to tokenize, generalize, get dependencies, filter unimportant words to get your result. And if you wanna do it in german, you need a word decompounder aswell.

Nicolas
  • 950
  • 1
  • 7
  • 15
1

You will need to stem the words in your sentences down to a common synonym, and then compare those stems and use the ratio of stem matches in a sentence (5 out of 10 words) to compare against some threshold that the sentence is a match. For example all sentences with a word match of over 80% (or what ever percentage you deem acurate). At least that is one way to do it.

Charles Lambert
  • 5,042
  • 26
  • 47
  • 1
    This may be useful as a crude baseline method. I would at least apply a tf-idf transformation to the text and use a lemmatizer rather than a stemmer. – Fred Foo May 10 '11 at 07:06
  • Would tf-idf apply to single sentences? From what I understand, that is better suited to texts much larger than a single sentence. – Charles Lambert May 10 '11 at 14:27
  • That's true, but there's bound to be some variant for small sentences. Besides, idf doesn't rely on the sentence length but on the number of sentences. – Fred Foo May 10 '11 at 16:27
1

Write a function which creates some kinda hash, or "expression" from a sentence, which can be easy compared with other sentences' hashes.

Cca:
1. "the sum of (x) and (y) is (z)" => x + y = z
4. "(z) is the sum of (x) and (y)" => z = x + y

Some tips for the transformation: omit "the" words, convert double-word terms to a single word "sum of" => "sumof", find operator word and replace "and" with it.

ern0
  • 3,074
  • 25
  • 40