4
$\begingroup$

I'm wondering how far along the natural language processing is in determining the semantic distance between two excerpts of text.

For instance, consider the following phrases

  1. Early this morning I got up and washed my car.
  2. I cleaned my truck up this morning.
  3. Bananas are an excellent source of potassium.

Clearly (to the human reader) the first two statements are much more similar to one another than they are to the third statement. Does there exist any theory that would allow a computer to draw the same conclusion? What about if we allow longer excerpts such as new articles?

Meta info: this is my first post here, so feel free to direct me to a better forum for asking such a question if this isn't where I should be. Also, feel free to retag my question with anything more appropriate.

Improve this question
$\endgroup$
5
  • $\begingroup$ This isn't in the scope of theoretical computer science since there's no rigorously specified question, and no plausible likelihood of getting such a question. Try asking an AI or NLP audience instead. $\endgroup$
    – Warren Schudy
    Oct 14, 2010 at 22:53
  • $\begingroup$ What Warren said. If you did come up with such a definition, then questions about the best algorithm to compute this distance might be in scope. $\endgroup$
    – Suresh Venkat
    Oct 15, 2010 at 2:09
  • 2
    $\begingroup$ NLP researchers routinely handle problems like this! The techniques they use (eg, LSA) obviously don't fully capture "meaning", but they are definitely simple and beautiful applications of linear algebra. A description of these algorithms is surely on topic here. $\endgroup$
    – Neel Krishnaswami
    Oct 15, 2010 at 10:30
  • $\begingroup$ @Neel Krishnaswami: I would agree with what you said if the problem specified a model, then the question would be about techniques. But this seems to be about how to model an informal problem not about techniques, so this seems to be out of our scope (more suitable for an AI/cognitive science/linguistics site). On the other hand, if OP specifies a model and asks for techniques, then that would be in the scope. $\endgroup$
    – Kaveh
    Oct 15, 2010 at 19:21
  • $\begingroup$ I opened a discussion on Meta about the how-to-model-this questions like this. $\endgroup$
    – Tsuyoshi Ito
    Oct 15, 2010 at 20:04

3 Answers 3

Reset to default
12
$\begingroup$

You are looking for "lexical cohesion". Try searching for this term and you will get tons of literature. After constructing the so-called "lexical chains", well-known graph partitioning and information retrieval algorithms can be used to group them into semantic classes. There is in fact a lot of theory and algorithms behind this "post-processing". Dictionary of synonyms and antonyms is often used to construct these chains. I worked on such extraction algorithms during my undergraduate days, about 10 years back. So this field must be more advanced now.

Improve this answer
$\endgroup$
2
  • $\begingroup$ This seems helpful, however I'm ultimately hoping to use this for comparing larger text excerpts (several sentences... perhaps paragraphs). At first glance, this appears to apply most easily to words or short phrases. Does it extend? $\endgroup$
    – John Berryman
    Oct 15, 2010 at 21:12
  • $\begingroup$ Yes. It extends well. These algorithms are often combined with text summarization techniques to compare large text excerpts. $\endgroup$
    – Shiva Kintali
    Oct 16, 2010 at 0:12
1
$\begingroup$

If you crawl Wikipedia from this page http://en.wikipedia.org/wiki/Vector_space_model you will learn a lot on similarity measures. Afterwards, you should consider reading the book of Manning, Raghavan and Schutze: Introduction to information retrieval.

Improve this answer
$\endgroup$
0
$\begingroup$

(Oh good, this question hasn't been closed yet!) On a practical level, I agree with the comments by Warren and Suresh that this question isn't answerable given the current state of the art in TCS, and it sounds more like an AI question. But I have to wonder, does it necessarily have to be that way? The question of how semantics arises from syntax has to be one of the most foundational questions there is, and I wouldn't want to rule out TCS having a role in answering it. I tend to think of AI of being more like engineering and TCS like theoretical physics--we ought to be supplying the equivalent of Newton's Laws that provides some overarching principles that the AI engineers can use to go and build their intelligent machines.

Now, so that this answer isn't totally without actual content, here is a paper that maybe touches a little bit on this question: Universal Semantic Communication I by Juba and Sudan. They make an attempt at modeling "meaningful communication" in terms of computational power. I'm not sure how successful their approach is, but I do think it's important in that they are using techniques from computational complexity to analyze these issues.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Kurt: your comment is well taken, and it might indeed be interesting to model semantics, maybe even along the lines of Juba and Sudan. But is this the right forum for that ? $\endgroup$
    – Suresh Venkat
    Oct 15, 2010 at 5:36
  • 1
    $\begingroup$ Downvoted. The post contains interesting information, but it is related more to whether the question is in scope or not than to the question itself. It really belongs to Meta. $\endgroup$
    – Tsuyoshi Ito
    Oct 15, 2010 at 14:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.